Frage

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

War es hilfreich?

Lösung

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.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top