Are NP proofs limited to polynomial length?

Question

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.

Answer 1

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.

Answer 2

A proof of "yes" instance means providing a solution. Providing a solution is providing a valid input. By definition, it can be verified in time and space polynomial relatively to the input, or else it is not a problem in NP.

It is unknown whether all proofs of "no" instances are verifiable in polynomial time and space (the difference between NP and Co-NP).

To answer the question precisely, the proof of a "yes" instance is the input value. You cannot say that the input has polynomial length because polynomial is used when comparing to the input size. Therefore the question is meaningless because of the word 'polynomial'. If you really want a polynomial somewhere, the size of the proof relatively to the input can be defined as a linear function f(x) = ax+b where a=1 and b=0, which can be simplified to f(x)=x because the size of the input is equal to itself.