3 ms·
No, that's what NP means. Given a witness to a solution of a problem, verifying that the solution is correct in polynomial time means the problem is in NP.
by popcorncolonel 9y ago
No, that's what NP means. Given a witness to a solution of a problem, verifying that the solution is correct in polynomial time means the problem is in NP.