Pergunta

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

Foi útil?

Solução

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.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top