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.