NP - verified in polynomial time NP-hard - all problems in NP can reduce to it but it doesn’t have to be verified in polynomial time NP-complete - NP and NP-hard
NP
Is decision problems (TSP, independent set) Typically operates with a threshold and attempts to answer a question
Any polynomial time language belongs to NP as well because they also can be verified in polynomial time
Decision Problems
Yes/No (binary 0, 1) problems where yes returns a certificate
Verification
Test if a certificate is correct in polynomial time for a problem e.g. given x integers, see if correct Uses certificate (evidence or hint or answer to problem used to verify - not the Y/N answer)
Turing Machines (TM)
If TM M returns 0, invalid answer else valid.
NP-complete key idea
P=NP if a polynomial time solution is found for any NP-complete problem
NP-hard reduction (prove NP-hard)
To prove B is NP-Hard (at least as hard as any in NP), you reduce A to B for any A in NP. But A is less hard, so a more accurate term would be increase
Problems (Language)
SAT
Is there some assignment of the n input variables such that the formula evaluates to True boolean satisfiability given some arbitrary CNF clauses (boolean OR expressions) in a CNF Formula (AND of CNF clauses)
3-SAT
SAT but clauses of length 3
Prove NP
Show algorithm is easily verifiable, like checking over a grid to get the binary 0/1 answer