MAX-3SAT

<h2 id="approximability">Approximability</h2>
The decision version of MAX-3SAT is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. Therefore, a <a href="/facts/Polynomial-time/77T62gmf">polynomial-time</a> solution can only be achieved if <a href="/facts/P_%253D_NP/xoC7Ruda">P = NP</a>. An approximation within a factor of 2 can be achieved with this simple algorithm, however:

<ul><li>Output the solution in which most clauses are satisfied, when either all variables = TRUE or all variables = FALSE.</li>
<li>Every clause is satisfied by one of the two solutions, therefore one solution satisfies at least half of the clauses.</li></ul>
The <a href="/facts/Karloff-Zwick_algorithm/yd6jMEE4">Karloff-Zwick algorithm</a> runs in <a href="/facts/Polynomial-time/77T62gmf">polynomial-time</a> and satisfies ≥ 7/8 of the clauses. While this algorithm is randomized, it can be derandomized using, e.g., the techniques from <a class="footnote-ref" id="fnref:1" href="#fn:1">1</a> to yield a deterministic (polynomial-time) algorithm with the same approximation guarantees.

<h2 id="theorem-1-inapproximability">Theorem 1 (inapproximability)</h2>
The <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a> implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>.
Proof:
Any <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problem ⁠
 
 
 
 L
 ∈
 
 
 P
 C
 P
 
 
 (
 O
 (
 log
 ⁡
 (
 n
 )
 )
 ,
 O
 (
 1
 )
 )
 
 
 {\displaystyle L\in {\mathsf {PCP}}(O(\log(n)),O(1))}
 
⁠ by the <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a>. For x ∈ L, a <a href="/facts/3-CNF/B3sY1lTW">3-CNF</a> formula Ψx is constructed so that

<ul><li>x ∈ L ⇒ Ψx is satisfiable</li>
<li>x ∉ L ⇒ no more than (1-ε)m clauses of Ψx are satisfiable.</li></ul>
The Verifier V reads all required bits at once i.e. makes non-adaptive queries. This is valid because the number of queries remains constant.

<ul><li>Let q be the number of queries.</li>
<li>Enumerating all random strings Ri ∈ V, we obtain poly(x) strings since the length of each string 
 
 
 
 r
 (
 x
 )
 =
 O
 (
 log
 ⁡
 
 |
 
 x
 
 |
 
 )
 
 
 {\displaystyle r(x)=O(\log |x|)}
 
.</li>
<li>For each Ri
<ul><li>V chooses q positions i1,...,iq and a Boolean function fR: {0,1}q->{0,1} and accepts if and only if fR(π(i1,...,iq)). Here π refers to the proof obtained from the Oracle.</li></ul></li></ul>
Next we try to find a <a href="/facts/Boolean_logic/VkCToAmg">Boolean</a> formula to simulate this. We introduce Boolean variables x1,...,xl, where l is the length of the proof. To demonstrate that the Verifier runs in <a href="/facts/Probabilistic/fgYvMhwb">Probabilistic</a> <a href="/facts/Polynomial-time/77T62gmf">polynomial-time</a>, we need a correspondence between the number of satisfiable clauses and the probability the Verifier accepts.

<ul><li>For every R, add clauses representing fR(xi1,...,xiq) using 2q <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">SAT</a> clauses. Clauses of length q are converted to length 3 by adding new (auxiliary) variables e.g. x2 ∨ x10 ∨ x11 ∨ x12 = ( x2 ∨ x10 ∨ yR) ∧ ( yR ∨ x11 ∨ x12). This requires a maximum of q2q <a href="/facts/3-SAT/wBVRjWoy">3-SAT</a> clauses.</li>
<li>If z ∈ L then
<ul><li>there is a proof π such that Vπ (z) accepts for every Ri.</li>
<li>All clauses are satisfied if xi = π(i) and the auxiliary variables are added correctly.</li></ul></li>
<li>If input z ∉ L then
<ul><li>For every assignment to x1,...,xl and yR's, the corresponding proof π(i) = xi causes the Verifier to reject for half of all R ∈ {0,1}r(|z|).
<ul><li>For each R, one clause representing fR fails.</li>
<li>Therefore, a fraction 
 
 
 
 
 
 1
 2
 
 
 
 
 1
 
 q
 
 2
 
 q
 
 
 
 
 
 
 
 {\displaystyle {\frac {1}{2}}{\frac {1}{q2^{q}}}}
 
 of clauses fails.</li></ul></li></ul></li></ul>
It can be concluded that if this holds for every <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problem then the <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a> must be true.

<h2 id="theorem-2">Theorem 2</h2>
Håstad <a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> demonstrates a tighter result than Theorem 1 i.e. the best known value for ε.
He constructs a PCP Verifier for <a href="/facts/3-SAT/wBVRjWoy">3-SAT</a> that reads only 3 bits from the Proof.

<blockquote>
For every ε > 0, there is a PCP-verifier M for <a href="/facts/3-SAT/wBVRjWoy">3-SAT</a> that reads a random string r of length ⁠
 
 
 
 O
 (
 log
 ⁡
 (
 n
 )
 )
 
 
 {\displaystyle O(\log(n))}
 
⁠ and computes query positions ir, jr, kr in the proof π and a bit br. It accepts if and only if π(ir) ⊕ π(jr) ⊕ π(kr) = br.

</blockquote>
The Verifier has completeness (1−ε) and soundness 1/2 + ε (refer to <a href="/facts/PCP_(complexity)/dbgntVpK">PCP (complexity)</a>). The Verifier satisfies

z
        ∈
        L
        
        ⟹
        
        ∃
        π
        P
        r
        [
        
          V
          
            π
          
        
        (
        z
        )
        =
        1
        ]
        ≥
        1
        −
        ϵ
      
    
    {\displaystyle z\in L\implies \exists \pi Pr[V^{\pi }(z)=1]\geq 1-\epsilon }

z
        ∉
        L
        
        ⟹
        
        ∀
        π
        P
        r
        [
        
          V
          
            π
          
        
        (
        z
        )
        =
        1
        ]
        ≤
        
          
            1
            2
          
        
        +
        ϵ
      
    
    {\displaystyle z\not \in L\implies \forall \pi Pr[V^{\pi }(z)=1]\leq {\frac {1}{2}}+\epsilon }

If the first of these two equations were equated to "=1" as usual, one could find a proof π by solving a <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a> (see <a href="/facts/MAX-3LIN-EQN/Ap6HfUTv">MAX-3LIN-EQN</a>) implying <a href="/facts/P_%253D_NP/xoC7Ruda">P = NP</a>.

<ul><li>If z ∈ L, a fraction ≥ (1 − ε) of clauses are satisfied.</li>
<li>If z ∉ L, then for a (1/2 − ε) fraction of R, 1/4 clauses are contradicted.</li></ul>
This is enough to prove the <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a> ratio

1
              −
              
                
                  1
                  4
                
              
              (
              
                
                  1
                  2
                
              
              −
              ϵ
              )
            
            
              1
              −
              ϵ
            
          
        
        =
        
          
            7
            8
          
        
        +
        
          ϵ
          ′
        
      
    
    {\displaystyle {\frac {1-{\frac {1}{4}}({\frac {1}{2}}-\epsilon )}{1-\epsilon }}={\frac {7}{8}}+\epsilon '}

<h2 id="related-problems">Related problems</h2>
MAX-3SAT(B) is the restricted special case of MAX-3SAT where every variable occurs in at most B clauses. Before the <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a> was proven, Papadimitriou and Yannakakis<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> showed that for some fixed constant B, this problem is MAX SNP-hard. Consequently, with the PCP theorem, it is also APX-hard. This is useful because MAX-3SAT(B) can often be used to obtain a PTAS-preserving reduction in a way that MAX-3SAT cannot. Proofs for explicit values of B include: all B ≥ 13,<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> and all B ≥ 3<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> (which is best possible).
Moreover, although the decision problem <a href="/facts/2SAT/cUMH5x2y">2SAT</a> is solvable in polynomial time, <a href="/facts/MAX-2SAT/cUMH5x2y">MAX-2SAT</a>(3) is also APX-hard.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>
The best possible approximation ratio for MAX-3SAT(B), as a function of B, is at least 
 
 
 
 7
 
 /
 
 8
 +
 Ω
 (
 1
 
 /
 
 B
 )
 
 
 {\displaystyle 7/8+\Omega (1/B)}
 
 and at most 
 
 
 
 7
 
 /
 
 8
 +
 O
 (
 1
 
 /
 
 
 
 B
 
 
 )
 
 
 {\displaystyle 7/8+O(1/{\sqrt {B}})}
 
,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> unless NP=RP. Some explicit bounds on the approximability constants for certain values of B are known.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> Berman, Karpinski and Scott proved that for the "critical" instances of MAX-3SAT in which each literal occurs exactly twice, and each clause is exactly of size 3, the problem is approximation hard for some constant factor.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
<a href="/facts/MAXEkSAT/DDbke5vf">MAX-EkSAT</a> is a parameterized version of MAX-3SAT where every clause has exactly k literals, for k ≥ 3. It can be efficiently approximated with approximation ratio 
 
 
 
 1
 −
 (
 1
 
 /
 
 2
 
 )
 
 k
 
 
 
 
 {\displaystyle 1-(1/2)^{k}}
 
 using ideas from <a href="/facts/Error_correcting_codes/cLUTUJrA">coding theory</a>.
It has been proved that random instances of MAX-3SAT can be approximated to within factor ⁠8/9⁠.<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a>

<a href="http://www.cs.berkeley.edu/~luca/notes/">Lecture Notes from University of California, Berkeley</a>
<a href="https://web.archive.org/web/20100702120650/http://www.cse.buffalo.edu/~atri/courses/coding-theory/">Coding theory notes at University at Buffalo</a>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sivakumar, D. (19 May 2002), "Algorithmic derandomization via complexity theory", Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 619–626, doi:10.1145/509907.509996, ISBN 1581134959, S2CID 94045 <a href="1581134959" target="_blank">1581134959</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Håstad, Johan (2001). "Some optimal inapproximability results". Journal of the ACM. 48 (4): 798–859. CiteSeerX 10.1.1.638.2808. doi:10.1145/502090.502098. S2CID 5120748. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Christos Papadimitriou and Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, May 02–04, 1988. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 0-8218-2872-X <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Sanjeev Arora, "Probabilistic Checking of Proofs and Hardness of Approximation Problems," Revised version of a dissertation submitted at CS Division, U C Berkeley, in August 1994. CS-TR-476-94. Section 7.2. <a href="http://www.cs.princeton.edu/~arora/pubs/thesis.pdf" target="_blank">http://www.cs.princeton.edu/~arora/pubs/thesis.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999), Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties, 
Springer-Verlag, Berlin. Section 8.4. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti Spaccamela, A., and Protasi, M. (1999), Complexity and Approximation. Combinatorial Optimization Problems and their Approximability Properties, 
Springer-Verlag, Berlin. Section 8.4. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Luca Trevisan. 2001. Non-approximability results for optimization problems on bounded degree instances. In Proceedings of the thirty-third annual ACM symposium on Theory of computing (STOC '01). ACM, New York, NY, USA, 453-461. DOI=10.1145/380752.380839 http://doi.acm.org/10.1145/380752.380839 <a href="http://doi.acm.org/10.1145/380752.380839" target="_blank">http://doi.acm.org/10.1145/380752.380839</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">On some tighter inapproximability results, Piotr Berman and Marek Karpinski, Proc. ICALP 1999, pages 200--209. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">P. Berman and M. Karpinski, Improved Approximation Lower Bounds on Small Occurrence Optimization, 
ECCC TR 03-008 (2003) <a href="http://eccc.hpi-web.de/report/2003/008/" target="_blank">http://eccc.hpi-web.de/report/2003/008/</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT,
ECCC TR 03-022 (2003). <a href="http://eccc.hpi-web.de/report/2003/022/" target="_blank">http://eccc.hpi-web.de/report/2003/022/</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">P. Berman, M. Karpinski and A. D. Scott, Approximation Hardness of Short Symmetric Instances of MAX-3SAT,
ECCC TR 03-049 (2003). <a href="http://eccc.hpi-web.de/report/2003/049/" target="_blank">http://eccc.hpi-web.de/report/2003/049/</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">W.F.de la Vega and M.Karpinski, 9/8-Approximation Algorithm for Random MAX-3SAT,
ECCC TR 02-070 (2002); RAIRO-Operations Research 41 (2007), pp.95-107] <a href="http://eccc.hpi-web.de/report/2002/070/" target="_blank">http://eccc.hpi-web.de/report/2002/070/</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
</ol>

MAX-3SAT open-in-new

MAX-3SAT