SU-CS154 Week 8

NP-Complete, Cook-Levin Theorem, and coNP
owo a chart! Properties of NP Completeness for NP complete A, B, is A\ \text{op}\ B np complete?
^ V R neg . * n n y ? n n Properties of P and NP for P or NP A, B, is A\ \text{op}\ B np complete?
Time ^ V R neg . * P y y y y y y NP y y y ? y y