Questions: Boolean Satisfiability and Standard NP-Complete Problems

Question 1

A researcher wants to prove that a new graph problem X is NP-complete. They show that X reduces to 3-SAT in polynomial time. Is this proof complete?

• A. Yes — showing X reduces to 3-SAT proves X is at least as hard as 3-SAT, establishing NP-hardness
• B. No — the reduction goes the wrong direction. To prove X is NP-hard, you must show 3-SAT reduces to X, not X to 3-SAT
• C. Yes — any polynomial-time reduction between two NP problems establishes that they are both NP-complete
• D. No — the researcher must also reduce X to the independent set problem, since reductions from 3-SAT alone are insufficient

Answer: (B)

This is the most common error in NP-completeness arguments. If X reduces to 3-SAT, then X is no harder than 3-SAT — a polynomial-time algorithm for 3-SAT would solve X. But this only shows X ∈ NP (or easier); it says nothing about X being hard. To prove X is NP-hard, you must show that 3-SAT (or another NP-complete problem) reduces to X — meaning X is at least as hard as 3-SAT. Hardness transfers in the direction of the reduction: A reduces to B means B is at least as hard as A.

Question 2

Suppose someone proves that CLIQUE (the problem of finding a complete subgraph of size k) can be solved in polynomial time. What is the immediate implication?

• A. SAT can be solved in polynomial time, because CLIQUE reduces to SAT via graph complement
• B. Every problem in NP can be solved in polynomial time, because CLIQUE is NP-complete and a polynomial algorithm for any NP-complete problem implies P = NP
• C. Only graph problems in NP can be solved in polynomial time; number-theoretic problems like factoring remain hard
• D. CLIQUE can be solved in polynomial time, but other NP-complete problems remain hard until independent proofs are given

Answer: (B)

CLIQUE is NP-complete. By definition of NP-completeness, every problem in NP reduces to CLIQUE in polynomial time. If CLIQUE has a polynomial-time algorithm, then every NP problem can be solved in polynomial time by first reducing to CLIQUE, then solving it. This would establish P = NP, meaning the entire class NP collapses to P. This includes factoring-based cryptography, RSA, and all other NP problems — a catastrophic consequence for cryptography.

Question 3

To prove a new problem X is NP-complete, it is sufficient to show that X is in NP and that some known NP-complete problem reduces to X in polynomial time.

• T. True
• F. False

Answer: True

This is the standard two-step method for NP-completeness proofs. Step 1: show X ∈ NP by exhibiting a polynomial-time verifier — a procedure that, given a candidate solution, checks its correctness in polynomial time. Step 2: show a known NP-complete problem (commonly 3-SAT) reduces to X in polynomial time, establishing that X is NP-hard. Together, X ∈ NP and X being NP-hard make X NP-complete. You need both: NP-hardness alone doesn't place X in NP (it could be harder than NP), and membership in NP alone doesn't establish hardness.

Question 4

If a new problem X reduces to 3-SAT in polynomial time, then X is expected to be NP-complete.

• T. True
• F. False

Answer: False

This is the direction error again, now stated as a true-false. X reducing to 3-SAT means X is no harder than 3-SAT — any polynomial solution for 3-SAT would also solve X. This shows X ∈ NP (assuming X is a decision problem), but it says nothing about whether X is NP-hard. Many problems in P reduce to 3-SAT (since every problem in P trivially reduces to any problem), yet P problems are definitely not NP-complete (assuming P ≠ NP). NP-completeness requires showing that 3-SAT (or another NP-complete problem) reduces TO X.

Question 5

Explain why the direction of a polynomial-time reduction matters when establishing NP-completeness, using an example.

Model answer: Reductions transfer hardness in one direction: if A reduces to B, then B is at least as hard as A. To prove problem X is NP-hard, you must show a known hard problem reduces TO X — meaning X can 'simulate' any NP-complete problem, so it must be at least as hard. For example, to prove INDEPENDENT SET is NP-complete, you reduce 3-SAT to INDEPENDENT SET (building a graph gadget from the 3-SAT formula). If INDEPENDENT SET could be solved in polynomial time, that solution would solve 3-SAT — proving the hardness transfer. Reducing INDEPENDENT SET to 3-SAT would only show INDEPENDENT SET is in NP, not that it is hard.

The intuition: 'A reduces to B' means 'solving B is enough to solve A.' So if A is known to be hard and A reduces to B, then B must also be hard — if B were easy, A would be easy too. The reduction must go from the known hard problem to the problem you want to prove hard. Getting the direction reversed is the single most common mistake in complexity theory proofs.