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 |