Ladner’s Theorem - Existence of NP-intermediate problems

One of the striking aspects of -completeness is that a surprisingly large number of  problems - including some that were studied for many decades- turned out to be -complete. This phenomenon suggests a bold conjecture: every problem in  is either in  or -complete. If  then the conjecture is trivially true but uninteresting.

We show that if (as widely believed) , then this conjecture is false - there is a language that is not  -complete.

An interesting feature of the proof is an interesting and Gödelian definition of a language  which "encodes" the difficulty of solving itself.

Theorem ('NP intermediate" languages [Lad75]) : Suppose that . Then there exists a language  that is not  -complete.

:

For every function  we define the language  to contain all length- satisfiable formulae that are padded with  1's.

We now define a function  as follows:

 is the smallest number  such that for every  with  outputs  within  steps.
Recall that  is the machine represented by the binary expansion of , and  is equal to 1 iff . If there is no such number  then 

 is well-defined since  determines membership in  of strings whose length is greater than , and the definition of  only relies upon checking the status of strings of length at most . In fact, the definition of  directly implies an  -time recursive algorithm that computes  from  . We defined  in this way to ensure the following claim:

 iff  (i.e., there's some  such that  for every  ). Moreover, if  then  tends to infinity with 

PROOF OF CLAIM:

•  Suppose there is a machine  solving  in at most  steps. Since  is represented by infinitely many strings, there is a number  such that  The definition of  implies that for  Thus 
•  If  then  can take only one of finitely many values, and hence there exists an  such that  for infinitely many  's. But this implies that the  solves  in  -time: for otherwise, if there was an input  on which  fails to output the right answer within this bound, then for every  we would have  Note that this holds even if we only assumed that there's some constant  such that  for infinitely many  's, hence proving the "moreover" part of the claim.

Using this claim we can show that if  then  is neither in  nor  complete:

• Suppose that . Then by the claim,  for some constant  implying that  is simply SAT padded with at most a polynomial (namely,  ) number of 1's. But then a polynomial-time algorithm for  can be used to solve SAT in polynomial time, implying that !

• Suppose that  is -complete. This means that there is a reduction  from  to  that runs in time  for some constant  Since we already concluded  is not in  the claim above implies that  tends to infinity. Since the reduction works in  time only, for large enough  it must map SAT instances of size  to  instances of size smaller than . Thus for large enough formulae  the reduction  must map it to a string of the type  where  is smaller by some fixed polynomial factor, say, smaller than . But the existence of such a reduction yields a simple polynomial-time recursive algorithm for SAT, contradicting the assumption !