3
$\begingroup$

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems are decision problems. So what type of problems are basically in the class NP ? And is it unnecessary to say that solutions to such problems have a polynomial length output(as decision problems necessarily output either 0 or 1) ?

$\endgroup$

migrated from cstheory.stackexchange.com Feb 11 '13 at 5:52

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ What does the textbook definition say? $\endgroup$ – Raphael Feb 11 '13 at 12:09
4
$\begingroup$

Indeed problems in NP are decision problems which output 0 or 1 for a given input string. Prof Roughgarden is referring to the fact that problems in NP have short polynomially bounded proof (in the input length) of membership that can be verified efficiently (by polynomial time algorithm).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.