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) ?
migrated from cstheory.stackexchange.com Feb 11 at 5:52
This question came from our site for theoretical computer scientists and researchers in related fields.
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).