Questions: Approximation Algorithms and Hardness of Approximation

Question 1

A researcher designs a polynomial-time algorithm for Max-3SAT that achieves an approximation ratio of 7/8 + ε for some small ε > 0. What does the PCP theorem imply about this result?

• A. The algorithm is valid but not practically useful since Max-3SAT is NP-hard
• B. The algorithm implies P = NP, since the PCP theorem shows no polynomial-time algorithm can exceed a 7/8-approximation unless P = NP
• C. The algorithm is likely incorrect because approximation ratios above 7/8 are computationally intractable by definition
• D. The algorithm is consistent with complexity theory as long as it runs in O(n^3) time

Answer: (B)

The PCP theorem establishes a tight inapproximability result: no polynomial-time algorithm can achieve a ratio better than 7/8 for Max-3SAT unless P = NP. A random assignment already achieves exactly 7/8. If an algorithm exceeded this bound, it would constitute a proof that P = NP, which would be the most significant result in theoretical computer science. The result is 'tight' in that the boundary is precisely 7/8 — not approximately that value.

Question 2

What does it mean for a problem to have a PTAS (polynomial-time approximation scheme)?

• A. It can be solved exactly in polynomial time for all instances
• B. For any fixed ε > 0, there is a polynomial-time algorithm achieving a (1+ε)-approximation, though the exponent in the polynomial may depend on ε
• C. It has a fixed polynomial-time algorithm that achieves any desired approximation ratio regardless of ε
• D. It belongs to neither P nor NP-complete — it occupies an intermediate complexity class

Answer: (B)

A PTAS guarantees that for any desired accuracy ε, you can get within (1+ε) of optimal in polynomial time — but 'polynomial' can mean O(n^{1/ε}) or worse, so the algorithm may be impractical for very small ε. The PTAS represents a strong approximability result: it says the problem can be solved arbitrarily accurately (though not exactly) in polynomial time. This is much stronger than a constant-factor approximation and distinguishes PTAS problems (like Euclidean TSP) from those that resist constant-factor approximation.

Question 3

Because most NP-hard optimization problems are equally hard to solve exactly, they are also equally hard to approximate.

• T. True
• F. False

Answer: False

NP-hardness is a binary property (hard or not), but approximability is a continuous landscape with fine structure. Many NP-hard problems — like Vertex Cover — admit constant-factor approximation algorithms (2-approximation). Some admit a PTAS (arbitrarily good approximation in polynomial time). Others, like the clique problem, resist any constant-factor approximation unless P = NP. Hardness of approximation reveals this rich hierarchy, showing that NP-hard problems differ drastically in how well they can be approximated.

Question 4

Hardness of approximation results, such as the inapproximability of Max-3SAT beyond 7/8, are unconditional theorems that hold regardless of whether P = NP.

• T. True
• F. False

Answer: False

Hardness of approximation results are conditional — they hold assuming P ≠ NP (or in some cases stronger complexity-theoretic assumptions). The statement is: 'If P ≠ NP, then no polynomial-time algorithm achieves better than 7/8 for Max-3SAT.' If someone proved P = NP, these inapproximability results would collapse. This conditional nature makes them different from impossibility results in mathematics. They are, however, the sharpest statements complexity theory can currently make about the limits of efficient approximation.

Question 5

How do gap-introducing reductions differ from standard NP-completeness reductions, and what do they establish that standard reductions cannot?

Model answer: Standard NP-completeness reductions show that deciding whether an optimal solution meets a threshold is NP-hard — they work with exact decision problems. Gap-introducing reductions transform instances so that YES instances have optimal value ≤ α·OPT and NO instances have optimal value ≥ β·OPT, creating a gap between the two regimes. The reduction shows that even distinguishing between these two regimes (i.e., approximating to within the ratio β/α) is NP-hard. This establishes that a polynomial-time algorithm achieving approximation ratio β/α would imply P = NP — something standard reductions cannot show.

The gap framing is essential because approximation asks for a quantitative guarantee, not just a yes/no answer. By amplifying the distance between YES and NO instances, gap reductions make the approximation task hard at the level of the gap. The PCP theorem is the foundational result enabling these reductions: it shows that NP languages have proofs verifiable with O(1) random bits and O(1) queries, which directly implies that distinguishing high-value from low-value Max-3SAT instances is NP-hard — the archetype of a gap reduction.