principleMinor
Is it necessary for NP problems to be decision problems?
Viewed 0 times
problemsnecessaryfordecision
Problem
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) ?
Solution
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).
Context
StackExchange Computer Science Q#9664, answer score: 4
Revisions (0)
No revisions yet.