8.3. P, NP and Computability


All problems in NP are computable

A polynomial-time nondeterministic algorithm can always be converted into a deterministic algorithm.

Select any problem Z in NP. Suppose that V(x, e) is a polynomial-time verifier that solves decision problem Z.

Remember, by definition, there must be a limit nk on the size of the evidence e. Here is a deterministic algorithm to solve the same problem Z

  solve(x)
  for all strings e of 
  length no more than nk
   if V(x,e) is true
     stop and answer yes
   end if
  end for
  answer no

That algorithm works, so Z is computable, but the algorithm takes a very long time.

If the alphabet has c symbols, and N = nk, then there are cN strings to try. Obviously, that is not polynomial time.


P ⊆ NP

It is easy to show that every problem in P is also in NP.

Suppose that Q is a problem in P. So there is a polynomial time (deterministic) algorithm that solves Q. Let that algorithm be q(x).

Here is a polynomial-time nondeterministic algorithm that solves Q

  Q-check(x, e)
  y = q(x)
  answer y

Nobody says that you are required to look at the evidence.


Is NP ⊆ P?

We know that P ⊆ NP.

We have also seen that converting a polynomial-time nondeterministic algorithm into a deterministic algorithm appears to require going to a non-polynomial-time algorithm.

Moreover, there are many problems in NP that have no known polynomial-time deterministic algorithm.

That suggests that NP contains some problems that are not in P.

But is that really true? Is P ≠ NP?

Nobody knows.

Our experience suggests that being able to look at the clue in the back of the puzzle book greatly speeds up solving the puzzle, even when you are required to check that the clue is correct. But that is nothing by intuition.

All we have right now is a conjecture.

Conjecture. P ≠ NP

There is a million dollar prize waiting for anybody who can find a correct proof or disproof of that conjecture.