What does calling an optimisation problem APX-hard rule out, given that it may still admit a 2-approximation?
answer
- a class defined by constant factors
- hardness transferred by reduction again
- the dial stops above one
- no scheme, but a constant survives
- a trivial algorithm meeting a proven ceiling
basics
~20 sAPX-hardness rules out an approximation scheme: unless P = NP there is a fixed threshold factor that no polynomial-time algorithm can beat, so accuracy cannot be dialled arbitrarily close to optimal. It does not rule out a constant factor, which such problems often have.
solid answer
~40 s**APX** is the class of optimisation problems that admit some polynomial-time constant-factor approximation. Calling a problem **APX-hard** means every problem in APX reduces to it by a reduction that preserves approximability, and the standard consequence is that it has **no PTAS unless P = NP** — there is a constant strictly better than which approximation becomes NP-hard. So the two statements sit together without contradiction: minimum vertex cover has a simple factor of 2 and is APX-hard, meaning the dial stops somewhere above 1. The sharpest illustration is satisfying the most clauses of a three-literal formula: a uniformly random assignment already satisfies 7/8 of the clauses in expectation, and beating 7/8 by any fixed margin is NP-hard, so that fraction is a genuine threshold rather than the best anyone has managed.
go deeper
Know only the headline: some problems can be approximated within a fixed factor, and for some of those the factor provably cannot be improved all the way to optimal.
Be able to define APX as the constant-factor class and state the consequence of APX-hardness as the absence of an approximation scheme, conditional on P differing from NP.
Separate the diagnoses cleanly: outside APX means the factor must grow with input size, APX-hard means a constant survives but no scheme does. Quote a threshold with the objective and the hypothesis attached.
Use it to stop a doomed programme early. When a team plans to iterate an approximation toward exactness, an APX-hardness result says the effort has a floor and the budget belongs elsewhere.
## The class and the hardness notion **APX** collects the optimisation problems for which some polynomial-time algorithm achieves a **constant** approximation factor — a factor that does not grow with the input. Metric tours are in it at 3/2; minimum vertex cover is in it at 2. **Set cover is not**, because its best achievable factor grows roughly like the natural logarithm of the number of elements, and that growth is itself essentially optimal unless P = NP. So membership in APX is already a meaningful statement: it says a scale-free promise exists. **APX-hardness** is the usual hardness-by-reduction move applied to this class. A problem is APX-hard when every problem in APX reduces to it by a reduction that carries approximation quality across — so a scheme for the hard problem would yield a scheme for all of them. The consequence quoted in interviews is short: > If a problem is APX-hard, it has **no PTAS unless P = NP**. Read that carefully in the direction it is stated. It forbids an arbitrarily tight *scheme*. It does not forbid a constant factor, and it does not say the problem is unapproximable. A problem can be APX-hard and still have a clean factor of two. ## The three statements that get conflated | Statement | What it forbids | Example shape | |---|---|---| | Not in APX (unless P = NP) | any constant factor at all | a factor that must grow with the input | | APX-hard | a PTAS, so accuracy cannot be dialled to optimal | a fixed constant factor survives | | NP-hard to approximate below a stated threshold | beating that specific number | a tight threshold, achievable above it | Candidates routinely collapse the first two, and the difference matters operationally: "no constant factor" means your promise degrades with scale, while "no PTAS" means your promise is bounded but cannot be refined. ## Where the thresholds come from These results are **gap** results. A reduction is built that maps a satisfiability question to instances whose optima are either high or low with a guaranteed gap between them, so any algorithm approximating better than the gap would decide the original question. The deep theorem making such gap-preserving reductions available is the **PCP theorem**, which characterises NP by proofs that can be checked by reading a constant number of randomly chosen positions. That characterisation is what converts an ordinary NP-hardness statement into a statement about approximation factors. The cleanest concrete threshold concerns satisfying the maximum number of clauses in a formula with three distinct literals per clause: 1. Assign every variable true or false uniformly at random. A given clause fails only when all three literals fall the wrong way, which happens with probability 1/8, so the expected fraction satisfied is **7/8** — and that expectation can be achieved deterministically. 2. For every fixed margin above 7/8, achieving that fraction in polynomial time is NP-hard. So 7/8 is not "the best factor found so far"; it is where the possible stops, with a trivial algorithm on one side and NP-hardness on the other. That pairing — an easy algorithm meeting a proven ceiling — is what makes it the standard example. ## Using the vocabulary honestly A few habits keep these claims straight: - **Say the hypothesis.** Almost every statement here is conditional on P being different from NP, and a few sharper ones rest on stronger conjectures. An unconditional "impossible" is wrong. - **Name the direction.** "No better than factor `c`" for minimisation means no algorithm achieving a ratio below `c`; for maximisation the same sentence means a fraction above some value. State the objective with the number. - **Separate the two failures.** Falling outside APX and being APX-hard are different diagnoses with different engineering consequences. - **Do not over-read a threshold.** A hardness threshold constrains worst-case instances. It says nothing about your inputs, which may be far easier — it only says you cannot *promise* better. In practice this vocabulary earns its keep at exactly one moment: when someone proposes to keep tightening an approximation until it is "close enough to exact". If the problem is APX-hard, that programme has a proven floor, and the honest plan is to accept the constant, change the problem, or exploit structure in the instances rather than chase an impossible scheme.
- How does a problem outside APX differ operationally from one that is APX-hard?Outside APX, no constant factor exists at all, so the promise you can make degrades as inputs grow — set cover's logarithmic factor is the standard shape. APX-hard problems keep a scale-free constant, such as two for vertex cover; what they lose is the ability to refine that constant arbitrarily close to one.
- Why is the 7/8 figure for three-literal clause satisfaction considered tight rather than provisional?Because both sides are proved. A uniformly random assignment satisfies 7/8 of the clauses in expectation, which gives an algorithm achieving it, and beating 7/8 by any fixed margin is NP-hard. The achievable and the impossible meet at the same number, so no future algorithm can move it unless P = NP.
saying these in an interview costs you the question
- Says APX-hard means no constant-factor approximation exists.
- States hardness thresholds as unconditional rather than assuming P differs from NP.
- Treats a published threshold as the best factor found so far.
- Thinks a hardness threshold predicts behaviour on typical inputs.
- Confuses being in APX with being easy to approximate well.