Search code examples
algorithmnp-completenp

NP class : Why polynomial length outputs?

For a problem to qualify for the NP class :

  1. The solution to the problem must have a polynomial output length ,and
  2. The solution must be verifiable in polynomial time .

What is the significance of the polynomial output length ?

PS : I think that polynomial output length is a necessary pre-condition for the output to be verifiable in polynomial time. (But then just saying that solutions can be verified in polynomial time will still be sufficient.)

Solution

  • The polynomial length imposition is because you are modeling the machine as a universal turing machine.

    In thi case, the output "tape" would have to be of polynomial length.

    It is not because you are using a modern language and expecting polynomial length results.