CODEWITHSUNDEEP
algorithmnp-completenp
Nikunj Banka
Nikunj Banka

Reputation: 11385

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.)

Upvotes: 2

Views: 393

Answers (1)

Srikant Krishna
Srikant Krishna

Reputation: 881

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.

Upvotes: 1

Related Questions