### Friday, March 28, 2003

**The Berman-Hartmanis Isomorphism Conjecture**

In 1976, Berman and Hartmanis considered whether all of the
NP-complete problems might be the same. We says sets A and B are
*polynomial-time isomorphic* if there exists a function f such
that
- x is in A if and only if f(x) is in B (f reduces A to B),
- f is a bijection, i.e., f is 1-1 and onto,
- f is polynomial-time computable, and
- f
^{-1} is polynomial-time computable.

**Conjecture (Berman-Hartmanis):** Every pair of NP-complete sets
are isomorphic.
The Isomorphic Relation between sets is an equivalence relation. The
Berman-Hartmanis conjecture is equivalent to saying that every
NP-complete set is isomorphic to SAT.

The conjecture is still open though it has generated a considerable
amount of research in computational complexity. But for now let me
just explain why this question is interesting.

Berman and Hartmanis showed that all of the natural NP-complete sets
at the time, for example all of the problems listed in Garey &
Johnson, are isomorphic. They established this fact by proving that
every paddable NP-complete set is isomorphic to SAT. A set A is
*paddable* if there is a polynomial-time computable length-increasing
function g such that for all strings x and y, x is in A if and only if
g(x,y) is in A.

Most NP-complete sets are easily seen to be paddable. Consider the
clique problem. Given a graph G and a string y, we can create a new
graph H that encodes y by adding disjoint edges to G while keeping the
clique size of H the same as the clique size of G.

The isomorphism conjecture implies P≠NP, since if P=NP then there
would be finite NP-complete sets which cannot not be isomorphic to the
infinite set SAT. There was a time when Hartmanis was pushing on the
idea of using the conjecture to prove P≠NP but most complexity
theorists now believe the isomorphism conjecture is false.

More on the isomorphism conjecture in future posts.

9:25 AM
#
Comments
[]

### Thursday, March 27, 2003

**Is P versus NP undecidable?**

Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?"
Short Answer: Until we have a proof that P≠NP or a proof that P=NP, we cannot rule out the possibility that the P versus NP question is not provable in one of the standard logical theories. However, I firmly believe
there exists a proof that P≠NP. To think that the question is not provable just because we are not smart enough to prove it is a cop-out.

You'll have to be patient for the long answer. The October 2003 BEATCS Complexity Column will be devoted to this topic.

6:23 AM
#
Comments
[]

### Monday, March 24, 2003

**Foundations of Complexity **

Lesson 16: Ladner's Theorem

Previous Lesson |
Next Lesson
In the 1950's, Friedberg and Muchnik independently showed that there
were sets that were computably enumerable, not computable and not
complete. Does a similar result hold for complexity theory?

Suppose P≠NP. We have problems that are in P and problems that are
NP-complete and we know these sets are disjoint. Is there anything
else in NP? In 1975, Ladner showed the answer is yes.

**Theorem (Ladner)** If P≠NP then there is a set A in NP such
that A is not in P and A is not NP-complete.

I wrote up two
proofs of this result, one based on Ladner's proof and one based
on a proof of Impagliazzo. The write-up is taken mostly from a paper
by Rod Downey and myself.

4:26 PM
#
Comments
[]