5 ms·
There's a lot of handwaving in practice over complexity classes. Strictly speaking, P and NP only consist of decision problems, that is, the expected output is
by jcranmer 5y ago
There's a lot of handwaving in practice over complexity classes. Strictly speaking, P and NP only consist of decision problems, that is, the expected output is solely "YES" or "NO". In practice, however, we mostly care about functional problems, ones that give a result. Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?"
The general process to convert a function problem of "find the best X for this input" to a decision problem is to recast it as "is there an X better than k for this input?" So the validation in these cases means finding that a) the claimed X is actually an X on the input (e.g., a sequence of nodes to visit is actually a valid path in the first place), and b) you can measure the property of X you're trying to optimize (e.g., what is the total cost of the path).
Another way to think of it--one which actually illuminates the underlying proofs a bit better--is that NP is a nondeterministic class. Basically, this means that any problem in NP [in the fuzzy sense] can be thought of as a polynomial-time algorithm, but every time we have to make a "choice" of some kind (which node to pick next, which color to assign it, etc.), we can ask a magic oracle which tells us the correct answer in O(1) time.
- lalaithion 5y agoand NP only cares about being able to verify YES answers. co-NP cares about verifying NO answers. It's unknown whether or not NP and co-NP are equal.
- Quekid5 5y ago> Your example of "what's the shortest path between two points" is such an example: the decision variant is "is there a path between two points less than k?" Just to add to this: This can obviously also be brought back to "find the shortest path", by just asking the question again and again for smaller and smaller k, by halving.