The class NP contains all problems taht may be difficult to solve, but where it is at least possible to efficiently check whether a proposed solution checks out.
P vs NP is one of the 7 Millenium Prize problems
Landscape of complexity classes
A) EXP
B) NP
C) P
NP : being able to convince others of the correctness of an argument
The problem class NP contains all langauges where membership can be efficiently verified
NP asks :
completeness
soudness
Completeness : if x in A, then there is a verification procedure and a short certificate y that allows to verify that x in A in reasonable time
soundess if x not in A there cannot be a certificate y that fools others to wrongfully believe x in A ("no false positives")
Complete and sound example
A) each
B) exists
C) certificate
D) N/M
E) N=<k
F) impossible
G) M
Input x and certificate y can always be represented by bitstrings
A verficiations procedure is a fixed TM M that can process inputs of arbitrary length and either accepts or rejects them.
verficiation efficient, if its running time scales (at most) polynomially in input size
