Verifiable in Polynomial Time
← Back to NP
A problem is in NP if given a proposed solution (certificate), its correctness can be checked in polynomial time. For example, verifying a Hamiltonian path is easy (check the path), but finding one may be hard. This asymmetry between finding and verifying is the essence of the P vs NP question.