Berman–Hartmanis conjecture

Last updated
Unsolved problem in computer science:

Is there a polynomial time isomorphism between every two NP-complete languages?

Contents

(more unsolved problems in computer science)

In structural complexity theory, the Berman–Hartmanis conjecture is an unsolved conjecture named after Leonard C. Berman and Juris Hartmanis. [1] Informally, it states that all NP-complete languages look alike, in the sense that they can be related to each other by polynomial time isomorphisms. [2] [3] [4] [5]

Statements

Statement using p-isomorphism

An isomorphism between formal languages L1 and L2 is a bijective map f from strings in the alphabet of L1 to strings in the alphabet of L2, with the property that a string x belongs to L1 if and only if f(x) belongs to L2.

A polynomial-time isomorphism, or p-isomorphism for short, is an isomorphism f where both f and its inverse function can be computed in an amount of time polynomial in the lengths of their arguments.

Berman and Hartmanis conjectured that all NP-complete languages are p-isomorphic to each other. [1]

Statement using paddable languages

A formal language L is paddable if there is a polynomial time function f(x,y), with a polynomial time inverse, such that for every x and every y, the string x belongs to L if and only if f(x,y) belongs to L. That is, it is possible to pad the input x with irrelevant information y, in an invertible way, without changing its membership in the language. Berman and Hartmanis proved that all pairs of paddable NP-complete languages are p-isomorphic. [1]

Since p-isomorphism preserves paddability, and there exist paddable NP-complete languages, an equivalent way of stating the Berman–Hartmanis conjecture is that all NP-complete languages are paddable.

Statement using equivalence relations

Polynomial time isomorphism is an equivalence relation, and it can be used to partition the formal languages into equivalence classes, so another way of stating the Berman–Hartmanis conjecture is that the NP-complete languages form a single equivalence class for this relation.

Implications

Non-existence of sparse NP-complete languages

A formal language is called sparse if the number of yes-instances of length n grows only polynomially as a function of n. The known NP-complete languages have a number of yes-instances that grows exponentially, and if L is a language with exponentially many yes-instances then it cannot be p-isomorphic to a sparse language, because its yes-instances would have to be mapped to strings that are more than polynomially long in order for the mapping to be one-to-one. Therefore, if the Berman–Hartmanis conjecture is true, an immediate consequence would be the nonexistence of sparse NP-complete languages.

P vs. NP

The nonexistence of sparse NP-complete languages in turn implies that P ≠ NP, because if P = NP then every nontrivial language in P (including some sparse ones, such as the language of binary strings all of whose bits are zero) would be NP-complete. In 1982, Steve Mahaney published his proof that the nonexistence of sparse NP-complete languages (with NP-completeness defined in the standard way using many-one reductions) is in fact equivalent to the statement that P ≠ NP; this is Mahaney's theorem. Even for a relaxed definition of NP-completeness using Turing reductions, the existence of a sparse NP-complete language would imply an unexpected collapse of the polynomial hierarchy. [6]

Evidence

As evidence towards the conjecture, Agrawal et al. (1997) showed that an analogous conjecture with a restricted type of reduction is true: every two languages that are complete for NP under AC0 many-one reductions have an AC0 isomorphism. [7] Agrawal & Watanabe (2009) showed that, if there exist one-way functions that cannot be inverted in polynomial time on all inputs, but if every such function has a small but dense subset of inputs on which it can be inverted in P/poly (as is true for known functions of this type) then every two NP-complete languages have a P/poly isomorphism. [8] And Fenner, Fortnow & Kurtz (1992) found an oracle machine model in which the analogue to the isomorphism conjecture is true. [9]

Evidence against the conjecture was provided by Joseph & Young (1985) and Kurtz, Mahaney & Royer (1995). Joseph and Young introduced a class of NP-complete problems, the k-creative sets, for which no p-isomorphism to the standard NP-complete problems is known. [10] Kurtz et al. showed that in oracle machine models given access to a random oracle, the analogue of the conjecture is not true: if A is a random oracle, then not all sets complete for NPA have isomorphisms in PA. [11] Random oracles are commonly used in the theory of cryptography to model cryptographic hash functions that are computationally indistinguishable from random, and the construction of Kurtz et al. can be carried out with such a function in place of the oracle. For this reason, among others, the Berman–Hartmanis isomorphism conjecture is believed false by many complexity theorists. [12]

See also

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

In computational complexity theory, a decision problem is P-complete if it is in P and every problem in P can be reduced to it by an appropriate reduction.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

<span class="mw-page-title-main">Juris Hartmanis</span> American computer scientist (1928–2022)

Juris Hartmanis was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

In computational complexity theory, a language B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

In computational complexity theory, the complexity class ⊕P is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. An example of a ⊕P problem is "does a given graph have an odd number of perfect matchings?" The class was defined by Papadimitriou and Zachos in 1983.

In computational complexity theory, a gadget is a subunit of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.

In computational complexity theory, a unary language or tally language is a formal language where all strings have the form 1k, where "1" can be any fixed symbol. For example, the language {1, 111, 1111} is unary, as is the language {1k | k is prime}. The complexity class of all such languages is sometimes called TALLY.

In computational complexity theory, a sparse language is a formal language such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE.

<span class="mw-page-title-main">Structural complexity theory</span>

In computational complexity theory of computer science, the structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms. It involves the research of both internal structures of various complexity classes and the relations between different complexity classes.

<span class="mw-page-title-main">NP-completeness</span> Complexity class

In computational complexity theory, a problem is NP-complete when:

  1. It is a decision problem, meaning that for any input to the problem, the output is either "yes" or "no".
  2. When the answer is "yes", this can be demonstrated through the existence of a short solution.
  3. The correctness of each solution can be verified quickly and a brute-force search algorithm can find a solution by trying all possible solutions.
  4. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.

Mahaney's theorem is a theorem in computational complexity theory proven by Stephen Mahaney that states that if any sparse language is NP-complete, then P = NP. Also, if any sparse language is NP-complete with respect to Turing reductions, then the polynomial-time hierarchy collapses to .

In computational complexity theory, polynomial creativity is a theory analogous to the theory of creative sets in recursion theory and mathematical logic. The -creative sets are a family of formal languages in the complexity class NP whose complements certifiably do not have -time nondeterministic recognition algorithms. It is generally believed that NP is unequal to co-NP, which would imply more strongly that the complements of all NP-complete languages do not have polynomial-time nondeterministic recognition algorithms. However, for the -creative sets, the lack of a recognition algorithm can be proven, whereas a proof that NP ≠ co-NP remains elusive.

In computational complexity theory, NP/poly is a complexity class, a non-uniform analogue of the class NP of problems solvable in polynomial time by a non-deterministic Turing machine. It is the non-deterministic complexity class corresponding to the deterministic class P/poly.

References

  1. 1 2 3 Berman, L.; Hartmanis, J. (1977), "On isomorphisms and density of NP and other complete sets" (PDF), SIAM Journal on Computing, 6 (2): 305–322, doi:10.1137/0206023, hdl: 1813/7101 , MR   0455536 .
  2. ↑ Rothe, Jörg (2005), "3.6.2 The Berman–Hartmanis Isomorphism Conjecture and One-Way Functions", Complexity Theory and Cryptology: An Introduction to Cryptocomplexity, Birkhäuser, pp. 108–114, ISBN   978-3-540-22147-0 .
  3. ↑ Schöning, Uwe; Pruim, Randall J. (1998), "15. The Berman–Hartmanis Conjecture and Sparse Sets", Gems of Theoretical Computer Science, Springer, pp. 123–129, ISBN   978-3-540-64425-5 .
  4. ↑ Kurtz, Stuart; Mahaney, Steve; Royer, Jim (1990), "The structure of complete degrees", Complexity Retrospective, Springer, pp. 108–146
  5. ↑ Agrawal, Manindra (2011), "The Isomorphism Conjecture for NP", in Cooper, S. Barry; Sorbi, Andrea (eds.), Computability in Context: Computation and Logic in the Real World (PDF), World Scientific, pp. 19–48, ISBN   978-1-84816-245-7 .
  6. ↑ Mahaney, Stephen R. (1982), "Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis", Journal of Computer and System Sciences , 25 (2): 130–143, doi:10.1016/0022-0000(82)90002-2, hdl: 1813/6257 , MR   0680515 .
  7. ↑ Agrawal, Manindra; Allender, Eric; Impagliazzo, Russell; Pitassi, Toniann; Rudich, Steven (1997), "Reducing the complexity of reductions", Proceedings of the 29th ACM Symposium on Theory of Computing (STOC '97) , pp. 730–738, doi: 10.1145/258533.258671 , S2CID   14739803 . Agrawal, Manindra; Allender, Eric; Rudich, Steven (1998), "Reductions in circuit complexity: an isomorphism theorem and a gap theorem", Journal of Computer and System Sciences , 57 (2): 127–143, doi: 10.1006/jcss.1998.1583 .
  8. ↑ Agrawal, M.; Watanabe, O. (2009), "One-way functions and the Berman–Hartmanis conjecture", 24th Annual IEEE Conference on Computational Complexity (PDF), pp. 194–202, doi:10.1109/CCC.2009.17, S2CID   15244907 .
  9. ↑ Fenner, S.; Fortnow, L.; Kurtz, S.A. (1992), "The isomorphism conjecture holds relative to an oracle", Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, pp. 30–39, CiteSeerX   10.1.1.42.6130 , doi:10.1109/SFCS.1992.267821, S2CID   36512284 .
  10. ↑ Joseph, Deborah; Young, Paul (1985), "Some remarks on witness functions for nonpolynomial and noncomplete sets in NP", Theoretical Computer Science , 39 (2–3): 225–237, doi: 10.1016/0304-3975(85)90140-9 , MR   0821203 .
  11. ↑ Kurtz, Stuart A.; Mahaney, Stephen R.; Royer, James S. (1995), "The isomorphism conjecture fails relative to a random oracle", Journal of the ACM , 42 (2): 401–420, doi: 10.1145/201019.201030 , MR   1409741, S2CID   52152959 .
  12. ↑ Fortnow, Lance (March 28, 2003), The Berman-Hartmanis Isomorphism Conjecture .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.