Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question

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.

1  
+1 for the nice MOOC. –  Mohammad Al-Turkistany Feb 11 '13 at 6:14
    
What does the textbook definition say? –  Raphael Feb 11 '13 at 12:09
add comment

1 Answer 1

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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