Questions: 3-SAT and Reduction-Based Hardness Proofs

Question 1

You want to prove that INDEPENDENT SET is NP-hard. You design a polynomial-time function f that converts any 3-SAT formula φ into a graph G such that φ is satisfiable if and only if G has an independent set of size k. What does this reduction establish?

• A. INDEPENDENT SET is in NP
• B. INDEPENDENT SET is NP-hard, because if you could solve it efficiently you could solve 3-SAT efficiently
• C. 3-SAT is NP-hard — the reduction proves its own source is hard
• D. 3-SAT reduces to INDEPENDENT SET, proving 3-SAT is at least as hard as INDEPENDENT SET

Answer: (B)

A reduction FROM 3-SAT TO X means: given any 3-SAT instance, you can produce an X-instance in polynomial time that is a yes-instance iff the formula is satisfiable. If you could solve X efficiently, you could solve 3-SAT efficiently — but 3-SAT is NP-hard, so X must be too. Option D reverses the implication: 3-SAT reduces *to* INDEPENDENT SET, which means INDEPENDENT SET is at least as hard as 3-SAT, not the other way around. The direction of a reduction is what determines which problem is being proved hard.

Question 2

A classmate argues: 'Since 3-SAT restricts SAT to clauses with exactly 3 literals, it must be an easier problem than general SAT.' What is the correct response?

• A. The classmate is right — fewer possible formulas means a smaller search space
• B. 3-SAT is actually harder than general SAT because the rigid structure adds constraints
• C. 3-SAT and general SAT are both NP-complete and therefore computationally equivalent
• D. 3-SAT is in P because the fixed clause size enables dynamic programming

Answer: (C)

3-SAT and general SAT are both NP-complete, making them equivalent in computational hardness. Every SAT instance can be converted to 3-SAT in polynomial time by splitting large clauses (introducing auxiliary variables) and padding short ones. So if you could solve 3-SAT efficiently, you could solve all of SAT. The restriction to exactly 3 literals changes the syntax but preserves the full computational difficulty — it does not make the problem easier.

Question 3

To prove a new problem X is NP-hard, you is expected to construct a polynomial-time reduction FROM X TO 3-SAT.

• T. True
• F. False

Answer: False

The direction is exactly reversed. To prove X is NP-hard, you reduce FROM 3-SAT TO X — you show that any 3-SAT instance can be transformed into an instance of X in polynomial time, preserving satisfiability in both directions. This means 'if you could solve X efficiently, you could solve 3-SAT efficiently,' establishing X as at least as hard as 3-SAT. A reduction from X to 3-SAT would prove 3-SAT is at least as hard as X — not useful, since 3-SAT's hardness is already known.

Question 4

In the standard 3-SAT-to-INDEPENDENT-SET reduction, selecting one node from each clause's triangle (and avoiding edges between contradictory literals) is equivalent to choosing a satisfying assignment for the formula.

• T. True
• F. False

Answer: True

This is exactly the gadget design. Each clause gets a triangle of 3 nodes (one per literal occurrence); intra-triangle edges prevent selecting two literals from the same clause. Edges between nodes labeled x and ¬x prevent contradictory assignments. Choosing an independent set of size k — one node per clause — means selecting one satisfied literal per clause while keeping assignments consistent. The independent set *is* the satisfying assignment, encoded spatially. The encoding preserves satisfiability in both directions.

Question 5

Why is 3-SAT the preferred source problem for hardness reductions, rather than general SAT or some other NP-complete problem?

Model answer: 3-SAT's rigid three-literal clause structure is rich enough to simulate arbitrary Boolean constraints yet regular enough that gadgets are small and explicit. The fixed clause size creates a predictable template — variable gadgets and clause gadgets are manageable — while the three-literal structure can encode any satisfiability constraint through known transformations. General SAT's variable clause lengths make gadget design messier. Other NP-complete problems may require more complex translations back to 3-SAT. The combination of universality (via Cook-Levin) and structural regularity makes 3-SAT the ideal reduction source.

The key is the balance between expressive power and structural uniformity. 3-SAT clauses are just constrained enough to build clean gadgets (you always know exactly what to connect) and just expressive enough that any NP problem's constraints can be mirrored. This is why 3-SAT sits at the center of NP-completeness theory as the canonical starting point.