문제

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

도움이 되었습니까?

해결책

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.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top