Domanda

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

È stato utile?

Soluzione

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.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top