Suppose a polynomial time algorithm is discovered that correctly computes the…
2014
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?
Attempted by 17 students.
Show answer & explanation
Key idea: CLIQUE is an NP-Complete problem.
If there exists a polynomial-time algorithm for an NP-Complete problem, then every problem in NP can be solved in polynomial time (because every NP problem reduces in polynomial time to any NP-Complete problem).
Therefore P = NP: the class of problems solvable in polynomial time equals the class verifiable in polynomial time.
When P = NP, NP-Complete problems are also in P, so NP-Complete, NP, and P all collapse to the same set.
Conclusion: The correct Venn diagram is a single circle representing P = NP = NP-Complete.
A video solution is available for this question — log in and enroll to watch it.