P NP

Question 1

NP (problems easy to check but no known polynomial time solution)

Answer 1

• traveling sales person
• 0-1knapsack
• integer factoring
• min vertex cover
• max independent set
• max clique

Question 2

CNF Satisfiability Problem - also NP bc 2^n

Answer 2

( X1 V |X2 V X3 ) ^ ( |X1 V X2 V |X3 )