SAT boolean satisfication , first np complete problem
Set cover
in G=(V,E)
minimum vertex cover, a special case of set cover
maximum clique,
maximum indepedent set
what is the defnination of NP? NPC? NP-hard? whtat is the meaning of NP!=P or NP=P?
How to prove a problem is NPC?
oracle machine? or Turing machine? Deterministic Turing Machine? Non-Denterministic Turing Machine?