LN9 Graphs, Coloring and Bipartiteness Flashcards
What is the first known NP-complete problem and why is it significant?
The SAT (Satisfiability) problem is the first known NP-complete problem. Its significance lies in its use as the basis for proving other problems NP-complete through reductions.
Explain the difference between P and NP in terms of SAT.
SAT is in NP because a solution (satisfying assignment) can be verified in polynomial time, but it is believed not to be in P as no polynomial-time solution is known.
What is Cook’s theorem, and why is it essential?
Cook’s theorem states that SAT is NP-complete. It provides a foundation for proving other problems NP-complete through polynomial-time reductions.
Why is 3SAT important in the context of NP-completeness?
3SAT is a specific form of SAT limited to three literals per clause and is still NP-complete, providing a simpler problem for proving the NP-completeness of other problems.
Describe the concept of a “gadget construction” in NP-completeness proofs.
Gadget constructions are used in reductions to represent components of one problem within another problem, helping prove NP-completeness by transforming instances from one problem into another.
What is the significance of the Exponential Time Hypothesis (ETH)?
ETH suggests that 3SAT cannot be solved in sub-exponential time, implying that NP-complete problems likely require exponential time, thus supporting the conjecture that P ≠ NP.
What is the difference between NP problems and NP-complete problems?
NP problems can be verified in polynomial time, while NP-complete problems are the hardest in NP, meaning every problem in NP can be reduced to them in polynomial time.
How does the reduction process work in proving NP-completeness?
To prove a problem Y is NP-complete, we must reduce a known NP-complete problem X to Y in polynomial time, showing that if we could solve Y quickly, we could also solve X quickly.
What does it mean if a problem X is polynomial-time reducible to another problem Y?
It means that instances of X can be transformed into instances of Y in polynomial time, indicating that Y is at least as hard as X.
True or False: If the Clique problem is polynomial-time reducible to Knapsack, then Knapsack is at least as hard as Clique.
True. A polynomial-time reduction indicates that the complexity of Knapsack is at least as high as that of Clique.
Why might it be a misconception to think NP-complete means “not polynomial”?
NP-complete does not mean “not polynomial”; it means the problem can be verified in polynomial time, but it’s unknown if a polynomial-time solution exists.
Explain the purpose of Garey and Johnson’s book on NP-completeness.
The book “Computers and Intractability” is a comprehensive resource on NP-complete problems, often referenced to identify known NP-complete problems and guide complexity analysis.
Why can’t the reduction from 3SAT to 2SAT produce a 2CNF formula that is equivalent?
The reduction technique does not work for 2SAT, as 2SAT is actually solvable in polynomial time, unlike 3SAT, which remains NP-complete.
What is the Independent Set problem, and why is it NP-complete?
The Independent Set problem seeks the largest set of non-adjacent vertices in a graph. It’s NP-complete due to its reduction from 3SAT, making it computationally challenging for arbitrary graphs.
Why is it incorrect to say that an efficient heuristic for an NP-complete problem proves it is not NP-complete?
Heuristics provide solutions for typical instances but do not guarantee polynomial-time solutions for all cases, so they do not affect the problem’s NP-completeness.
