P = NP Starts with a Missing Arrow

There is a slightly misleading way to tell the story of versus . It sounds as if someone observed that all efficiently verifiable problems can be solved efficiently and then proposed an explanation.

That is not what happened. The equality began as a missing arrow between two naturally defined classes.

The known direction

A deterministic computation has only one successor at each step. It is therefore a special case of a nondeterministic computation. Consequently,

The inclusion is not a conjecture. A deterministic polynomial-time machine already provides the kind of polynomial-time nondeterministic computation that NP permits.

The missing arrow

The open question is whether the reverse inclusion also holds:

In the certificate–verifier view, it asks whether

can always be decided in polynomial time whenever is polynomial-time and has polynomial length. In plain language: does the ability to check a successful certificate give us the ability to find one, or at least to decide that one exists?

This is a question about the power of a computational model. It is not a claim that an NTM’s branches can literally be run in parallel on one deterministic machine.

Why ask the question?

The question is still motivated by real structure:

• deterministic models such as Turing machines, RAM machines, and circuits often simulate one another with only polynomial overhead;
• some problems with enormous apparent search spaces, such as 2-SAT, have polynomial algorithms;
• verification and search are closely related for several important problems.

These facts make it reasonable to ask whether nondeterministic guessing adds genuine power. They do not show that it does not.

For other problems, the obvious simulation enumerates exponentially many paths. As the path-stacking picture shows, changing the order of that enumeration does not make it polynomial. A proof of would need a general way to avoid the enumeration, not merely a better way to organise it.

A question before a prediction

The equality is therefore a natural possibility, not an observation extracted from data. The prevailing conjecture is the opposite, , but that conjecture is also not a theorem.

The first conceptual step was simply to notice that deterministic computation sits inside nondeterministic computation and ask whether the extra branching is real power or only a different description of the same power. The missing arrow is the whole mystery.