structural complexity theory 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 t ...

, the Berman–Hartmanis conjecture is an unsolved

conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...

named after Leonard C. Berman and

Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) 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 establis ...

that states that all

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

languages look alike, in the sense that they can be related to each other by

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

isomorphism In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

Statement

An isomorphism between

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

s ''L''₁ and ''L''₂ is a

bijective In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

map ''f'' from

string String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

s in the alphabet of ''L''₁ to strings in the alphabet of ''L''₂, with the property that a string ''x'' belongs to ''L''₁ if and only if ''f''(''x'') belongs to ''L''₂. It is a polynomial time isomorphism (or ''p''-isomorphism for short) if both ''f'' and its

inverse function In mathematics, the inverse function of a function (also called the inverse of ) is a function that undoes the operation of . The inverse of exists if and only if is bijective, and if it exists, is denoted by f^ . For a function f\colon X\t ...

can be computed in an amount of time polynomial in the lengths of their arguments. observed that all languages known at that time to be NP-complete were ''p''-isomorphic. More strongly, they observed that all then-known NP-complete languages were ''paddable'', and they proved (analogously to the

Myhill isomorphism theorem In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set. Myhill isomorphism theorem Sets ''A'' and ''B'' of natural nu ...

) that all pairs of paddable NP-complete languages are ''p''-isomorphic. A language ''L'' is paddable if there is a polynomial time function ''f''(''x'',''y'') with a polynomial time inverse and with the property that, for all ''x'' and ''y'', ''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. Based on these results, Berman and Hartmanis conjectured that all NP-complete languages are ''p''-isomorphic. 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. Polynomial time isomorphism is an

equivalence relation In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation. Each equivalence relation ...

, and it can be used to partition the formal languages into

equivalence class In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...

es, so another way of stating the Berman–Hartmanis conjecture is that the NP-complete languages form a single equivalence class for this relation.

Implications

If the Berman–Hartmanis conjecture is true, an immediate consequence would be the nonexistence of sparse NP-complete languages, namely languages in which 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. The nonexistence of sparse NP-complete languages in turn implies that

P ≠ NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...

, 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 reduction In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...

s) is in fact equivalent to the statement that P ≠ NP; this is

Mahaney's theorem 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 reduction In computa ...

. Even for a relaxed definition of NP-completeness using

Turing reduction In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...

s, the existence of a sparse NP-complete language would imply an unexpected collapse of the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. T ...

Evidence

As evidence towards the conjecture, showed that an analogous conjecture with a restricted type of reduction is true: every two languages that are complete for NP under AC⁰ many-one reductions have an AC⁰ isomorphism. showed that, if there exist

one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, spe ...

s 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 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 equiva ...

(as is true for known functions of this type) then every two NP-complete languages have a P/poly isomorphism. And found an

oracle machine In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to solve certain problems in a s ...

model in which the analogue to the isomorphism conjecture is true. Evidence against the conjecture was provided by and . 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. Kurtz et al. showed that in oracle machine models given access to a

random oracle In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every ''unique query'' with a (truly) random response chosen uniformly from its output domain. If a query is repeated, it responds the same way every time th ...

, the analogue of the conjecture is not true: if ''A'' is a random oracle, then not all sets complete for NP^''A'' have isomorphisms in P^''A''. Random oracles are commonly used in the theory of cryptography to model

cryptographic hash function A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with fixed size of n bits) that has special properties desirable for cryptography: * the probability of a particular n-bit output re ...

s 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..

References

{{DEFAULTSORT:Berman-Hartmanis conjecture Structural complexity theory Conjectures Unsolved problems in computer science Unsolved problems in mathematics