TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passaudited 2026-10-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Max-3SAT has no PTAS unless P=NP

Statement

Assume the Axiom of Choice for the currently published PCP supplier proof route. If Max-3SAT has a polynomial-time approximation scheme, then $P = N P$ . More precisely, fix the preceding reduction for the NP-complete language $3$ -SAT and its gap $δ > 0$ . Any polynomial-time algorithm with maximization factor $ρ > 1 - δ$ would decide every language in NP.

Facts & Assumptions

Given: Fix $L : = 3$ -SAT and its gap $δ$ from the preceding reduction. Assume either a PTAS $A = (A_{ϵ})$ for Max-3SAT or a polynomial-time algorithm $A$ with value guarantee $val \geq ρ OPT$ for a fixed rational $ρ > 1 - δ$ .

[F1]

Under the Axiom of Choice for its published proof route, the constant-query PCP verifier gives a deterministic polynomial-time map $x \mapsto F_{x}$ to a 3-CNF formula with $M \geq 1$ clauses and a fixed $δ > 0$ such that $x \in L$ implies ${OPT}_{M a x 3 S A T} (F_{x}) = M$ and $x \notin L$ implies ${OPT}_{M a x 3 S A T} (F_{x}) \leq (1 - δ) M$ . (A constant-query PCP verifier yields constant-gap Max-3SAT)

[F2]

A PTAS for an optimization problem is a family $(A_{ϵ})_{0 < ϵ < 1}$ such that for each fixed $ϵ$ the algorithm runs in polynomial time in the input length and, for maximization, returns a feasible solution of value at least $(1 - ϵ) OPT$ in the value-inequality sense. (PTAS, FPTAS and APX)

[F3]

For Max-3SAT the scale is the number of clauses and ${OPT}_{M a x 3 S A T}$ is the maximum number of simultaneously satisfied clauses, so any particular assignment satisfies at most ${OPT}_{M a x 3 S A T}$ clauses. (Gap promise problems and gap-preserving reductions)

[F4]

$C$ is NP-hard when for every language $L \in N P$ one has $L \leq_{p} C$ , and NP-complete when $C$ is NP-hard and $C \in N P$ . (NP-hard and NP-complete languages)

[F5]

$P$ is the class of languages decided by some deterministic Turing machine in time polynomial in the input length. (The class P)

[F6]

Every language in $P$ belongs to $N P$ , so $P \subseteq N P$ . ( $P \subseteq N P \cap c o N P$ , The class NP via polynomial-time verifiers)

[F7]

The Axiom of Choice states that every family of nonempty sets has a choice function; it is assumed here solely through the published PCP supplier route used by [F1]. (The Axiom of Choice)

[F8]

The language $3$ -SAT is NP-complete. (3-SAT is NP-complete)

[F9]

A polynomial-time many-one reduction from $B$ to $C$ is a total polynomial-time computable function $f$ with $x \in B$ if and only if $f (x) \in C$ . (Polynomial-time many-one reductions)

Proof

technique · direct

1.1F1F2F7F8givenconstruct

By [F8], $L : = 3$ -SAT belongs to NP. Fix its gap reduction from [F1], under the Axiom of Choice hypothesis of [F7]. The construction in that supplier's proof supplies a rational $δ = (1 - s) / K$ with $0 < δ < 1$ , because its rational soundness bound satisfies $0 < s < 1$ and its integer $K \geq 4$ . In the PTAS case fix $ϵ : = δ / 2$ , so $0 < ϵ < δ < 1$ , and use $A_{ϵ}$ from [F2]; in the factor- $ρ$ case use the given $A$ . All these constants and algorithms are fixed for $3$ -SAT, independently of any later source language.

2.1F1F2step 1.1construct

Define the decision procedure: on input $x$ , compute $F_{x}$ , run the fixed algorithm ( $A_{ϵ}$ or $A$ ) on $F_{x}$ to obtain an assignment, evaluate that assignment clause by clause to count the number $s (x)$ of satisfied clauses, and accept $x$ exactly when $s (x) > (1 - δ) M$ . The formula is polynomial size in $n = ∣ x ∣$ , the fixed algorithm runs in polynomial time, and the exact comparison of the integer $s (x)$ with the rational threshold $(1 - δ) M$ is polynomial.

3.1F1F2step 2.1algebra

If $x \in L$ , then ${OPT}_{M a x 3 S A T} (F_{x}) = M$ by [F1], so in the PTAS case $s (x) \geq (1 - ϵ) M > (1 - δ) M$ and in the factor- $ρ$ case $s (x) \geq ρ M > (1 - δ) M$ , because $ϵ < δ$ and $ρ > 1 - δ$ ; in both cases $s (x) > (1 - δ) M$ and the procedure accepts $x$ .

3.2F1F3step 2.1algebra

If $x \notin L$ , then ${OPT}_{M a x 3 S A T} (F_{x}) \leq (1 - δ) M$ by [F1], and the counted assignment satisfies $s (x) \leq {OPT}_{M a x 3 S A T} (F_{x})$ by [F3], so $s (x) \leq (1 - δ) M$ and the procedure rejects $x$ .

4.1F4F5F6F8F9step 2.1step 3.1step 3.2construct

Steps 2.1, 3.1 and 3.2 give a deterministic polynomial-time decider for $3$ -SAT in either case. For any language $B \in N P$ , [F4] and [F8] give a polynomial-time many-one reduction $f_{B}$ to $3$ -SAT. On input $x$ , compute $f_{B} (x)$ and run this decider; [F9] gives the correct answer for $B$ . The output length of $f_{B}$ is polynomially bounded by its running time, so this composition is polynomial-time. Thus $N P \subseteq P$ by [F5], while $P \subseteq N P$ by [F6].

5.1step 4.1algebra∎

Hence a PTAS, or a polynomial-time maximization factor $ρ > 1 - δ$ for this fixed $3$ -SAT gap, forces $P = N P$ under the stated Axiom of Choice hypothesis.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Arora and Barak, Computational Complexity: A Modern Approach, §18.2.5 and the inapproximability discussion, printed pp. 359–361 (standard reference, not scraped)
Williamson and Shmoys, The Design of Approximation Algorithms, §1.5 and §16.2, printed pp. 21–25 and 413–414 (standard reference, not scraped)