Question

9. If any np-complete problem is polynomial-time solvable, then p = np. Equivalently, if any problem in np is not polynomial-time solvable, then no np-complete problem is polynomial-time solvable. Prove it.

Answer 1

Answer:

Step-by-step explanation:

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. Since they can be solved in polynomial time, they can also be verified in polynomial time. Therefore P is a subset of NP.