3 ms·
An NP complete problem is not any generalization but a problem where all solutions can be solved using brute force in polynomial time, also representing other p
by IncRnd 5y ago
An NP complete problem is not any generalization but a problem where all solutions can be solved using brute force in polynomial time, also representing other problems in the same space. In actuality, an NP complete problem is defined as easy to find a single solution, not that it is difficult to find a solution.
- tsimionescu 5y agoNo. If you want an intuitive but also theoretically correct definition of NP, it is the set of problems where it is easy to verify that a given solution is correct. NP - P then is the set of all problems for which it is easy to verify that a solution is correct, but hard to find any solution (this set may be empty, but we haven't proved either way). Here 'easy' means 'in polynomial time', and the property of all NP problems is that they are solvable in polynomial time given an oracle which generates the solutions, and then verifying that each solution is correct. Equivalently, they are solvable in polynomial time given an infinite number of execution threads that each takes one candidate solution and verifies whether it is correct or not (in polynomial time). I don't think there is any known class of problems in complexity theory where it is easy to find 1 solution but hard to find all solutions.
- deleted 5y ago[deleted]