If $P = NP$, which of the following statements would be TRUE?
If $P = NP$, then deterministic polynomial-time algorithms exist for all problems in NP, including all NP-Complete problems.
Which of the following reductions proves that 3-SAT is NP-Complete?
To prove 3-SAT is NP-Complete, we show 3-SAT is in NP, and reduce known NP-Complete problem SAT to 3-SAT in polynomial time (SAT <=_p 3-SAT).
In a graph $G = (V$, E) with n vertices, a set S subset of V is a CLIQUE of size k if:
A Clique is a complete subgraph where every distinct pair of vertices in set S has an edge between them.
The RELATIONSHIP between Vertex Cover (VC) and Independent Set (IS) in a graph $G = (V$, E) is:
Duality Theorem: S is an independent set in $G=(V,E)$ if and only if V \ S is a vertex cover of G.
Which of the following problems is IN CLASS P?
2-SAT can be solved in linear time O(V + E) by constructing an implication graph and finding strongly connected components (x and NOT x in same SCC implies unsatisfiable).