Are NP proofs limited to polynomial length? In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine.


The proofs for an NP decision problem are verified in polynomial time.

Does this imply the proofs are at most polynomial length?

"Well you have to read the whole input. If the input is longer than polynomial, then the time is greater than polynomial."

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.

Therefore, perhaps some NP problem has candidate proofs that are longer than polynomial length but checked in polynomial time.
The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input.


Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time.

While you could define proofs to exceed a polynomial length, only a polynomial prefix of the proof could be read in polynomial time, assuming the head starts at cell 0 and can move at max one cell to the right in one time unit.