P-isomorphisms.

Complexity theory is the mathematical study of the resources used by an algorithm when run on a Turing Machine (a standard model for a simple computer). For an introduction to the subject the reader is refered to Codes and Cryptography by D. Welsh (OUP) and Introduction to the theory of complexity by Bozet and Crescenzi (Prentice Hall).

Definition Two languages L1 and L2 are p-isomorphic if there exits an invertible computable function p(x) such that p and p-1 are calculatable in polynomial time, p(x) is a polynomial reduction of L1 to L2 and p-1(x) is a polynomial reduction of L2 to L1.

The class of NP-complete languages is conjectured to be a single p-isomorphism class (Berman + Hartmanis, 1978). All of the well known NP-complete languages are p-isomorphic. It has been shown that if there exists a sparse NP-complete language then NP=P. The proof works by showing that co-SAT (the complement of the language SAT) is reducible to an instance of the NP-complete sparse languages S and then showing SAT lies in P by building certificates for co-SAT. Very little seems to be known about the class NPI as has few definable properties (unlike P and NP-complete). It has been shown that, provided NP is not equal to P, there exists at least one member of NPI and hence there would exist at least one p-isomorphism class in NPI. The class P many p-isomorphism classes:

TRUE and FALSE. TRUE is the problem that accepts all possible inputs and FALSE is the problem that accepts no possible input. TRUE and FALSE are at the bottom of the complexity tree as they reduce to any other language but no other language reduces to them. n P-finite. The set of languages that contain exactly n acceptable inputs. n co-P-finite. The set of all languages that contain all but n acceptable inputs. sparse P-infinite. The set of all infinite sparse languages in P. It has not yet been proven that this is a single p-isomorphism class. co-sparse P-infinite. The set of all languages in P whose complement is sparse and infinite. Any result proven about sparse P-finite will be mirrored by an analgous result in this class. non-sparse P-inifinite. The class of remaining languages in P. Formally it is the class of languages who are infinite and non-sparse and whose complement is infinite and non-sparse as well. It seems quite likely that any further p-isomorphism classes found in P will be members of this class.

If the Berman and Hartmanis conjecture is true than NP is not equal to P because P contains a countably infinite number of p-isomorphism classes whilst NP-complete would contain only one.          The study of p-isomorphism hasn't, sad to say, advanced a huge amount in the twenty years it has been studied. There seem to be only two major results published along with a few interesting ideas and lots of unproven conjectures. The two major papers are that of Berman and Hartmanis, and Joseph and Young. The results of Berman and Hartmanis        The results of Berman and Hartmanis show that if a NP-complete language will admit functions with certain properties (length increasing functions that cause it to be a polynomial cylinder) then it is p-isomorhpic to the NP-complete language SAT. This led to the conjecture that has already been mentioned, that every NP-complete language is p-isomorphic. The results of Joseph and Young        This idea is strongly refuted by Joseph and Young who, using k-creative sets, suggest that a k-creative set with a one-way productive function need not be a polynomial cylinder, and hence will not be p-ismorphic to SAT. Sadly k-creativity isn't closed under p-isomorphisms or, in other words, if U is p-isomorphic to V and U is k-creative this does not mean that V is always k-creative. Consequently an easy candidate for a countably infinite number of NP-complete p-isomorhpism classes is destroyed. Joesph and Young conjecture that if one-way functions exist then the Berman and Hartmanis conjecture fails.        Another interesting idea about one-way functions and p-isomorphisms was mooted by Watanabe, who pointed out that if f is a one-way function than it seems intuitively unlikely that SAT is p-isomorphic to f(SAT). Sadly however he had better luck proving his results for super-polynomial classes than for NP and P.