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 *n*^{k} 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 n^{k}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* = *n*^{k},
then there are *c*^{N} strings to try.
Obviously, that is not polynomial time.

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.

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.