MAX-3SAT

MAX-3SAT

MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as:

"Given a 3-CNF formula Φ (i.e. with at most 3 variables per clause), Find an assignment that satisfies the largest number of clauses."

MAX-3SAT is a canonical complete problem for the complexity class MAXSNP (shown complete in Papadimitriou pg. 314).

Approximability

An exact solution of MAX-3SAT is NP-hard. Therefore, a polynomial-time solution can only be achieved if P = NP. An approximation within a factor of 2 can be achieved with this simple algorithm, however:

* Output the solution in which most clauses are satisfied, when either all variables = TRUE or all variables = FALSE.
* Every clause is satisfied by one of the two solutions, therefore one solution satisfies at least half of the clauses.

The Karloff-Zwick algorithm runs in polynomial-time and satisfies ≥ 7/8 of the clauses.

Theorem 1 (Inapproximability)

The PCP theorem implies that there exists an ε > 0 such that (1-ε)-approximation of MAX-3SAT is NP-hard.

Proof:

Any NP-complete problem "L" ∈ "PCP(O(log (n)), O(1))" by the PCP theorem. For x ∈ "L", a 3-CNF formula Ψx is constructed so that

* "x" ∈ "L" ⇒ Ψx is satisfiable
* "x" ∉ "L" ⇒ no more than (1-ε)m clauses of Ψx are satisfiable.

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.

* Let "q" be the number of queries.
* Enumerating all random strings "R"i ∈ "V", we obtain "poly(x)" strings since the length of each string "r(x) = O(log |x|)".
* For each "R"i
** "V" chooses "q" positions "i"1,...,"i"q and a Boolean function "f"R: {0,1}q and accepts if and only if "f"R(π(i1,...,iq)). Here π refers to the proof obtained from the Oracle.

Next we try to find a Boolean formula to simulate this. We introduce Boolean variables "x"1,...,"x"l, where "l" is the length of the proof. To demonstrate that the Verifier runs in Probabilistic polynomial-time, we need a correspondence between the number of satisfiable clauses and the probability the Verifier accepts.

* For every "R", add clauses representing "f"R("x"i1,...,"x"iq) using 2q SAT clauses. Clauses of length "q" are converted to length 3 by adding new (auxiliary) variables e.g. "x"2 ∨ "x"10 ∨ "x"11 ∨ "x"12 = ( "x"2 ∨ "x"10 ∨ "y"R) ∧ ( ar{y_R} ∨ "x"11 ∨ "x"12). This requires a maximum of "q"2q 3-SAT clauses.
* If "z" ∈ "L" then
** there is a proof π such that "V"π ("z") accepts for every "R"i.
** All clauses are satisfied if "x""i" = π("i") and the auxiliary variables are added correctly.
* If input "z" ∉ "L" then
** For every assignment to "x"1,...,"x"l and "y"R's, the corresponding proof π("i") = "x"i causes the Verifier to reject for half of all "R" ∈ {0,1}"r"(|"z"|).
*** For each "R", one clause representing "f"R fails.
*** Therefore a fraction frac{1}{2} frac{1}{q^{2^q of clauses fails.

It can be concluded that if this holds for every NP-complete problem then the PCP theorem must be true.

Related problems

MAX-3SAT(13) is a restricted version of MAX-3SAT where every variable occurs in at most 13 clauses.

Theorem 2

Håstad demonstrates a tighter result than Theorem 1 i.e. the best known value for ε.

He constructs a PCP Verifier for 3-SAT that reads only 3 bits from the Proof.

"For every ε > 0, there is a PCP-verifier M for 3-SAT that reads a random string r of length 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."

The Verifier has "completeness" (1-ε) and "soundness" 1/2 + ε (refer to PCP (complexity)). The Verifier satisfies

z in L implies exists pi Pr [V^{pi} (x) = 1] ge 1 - epsilon

z ot in L implies forall pi Pr [V^{pi} (x) = 1] le 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 system of linear equations (see MAX-3LIN-EQN) implying P = NP.

* If z ∈ "L", a fraction ≥ (1- ε) of clauses are satisfied.
* If z ∉ "L", then for a (1/2- ε) fraction of "R", 1/4 clauses are contradicted.

This is enough to prove the hardness of approximation ratio

frac{1-frac{1}{4}(frac{1}{2}-epsilon)}{1-epsilon} = frac{7}{8} + epsilon'

References

[http://www.cs.berkeley.edu/~luca/notes/ Lecture Notes from University of California, Berkeley]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • MAX-3SAT(13) — is a problem in computational complexity theory that is a restricted version of MAX 3SAT. Every variable occurs in at most 13 clauses. MAX 3SAT(13) is hard to approximate with approximation ratio 1 + delta; for some delta; > 0.ee also*PCP… …   Wikipedia

  • MAX-3LIN-EQN — is a problem in Computational complexity theory where the input is a system of linear equations (modulo 2). Each equation contains at most 3 variables. The problem is to find an assignment to the variables that satisfies the maximum number of… …   Wikipedia

  • Max Karl Ernst Ludwig Planck — Max Planck Max Karl Ernst Ludwig Planck (* 23. April 1858 in Kiel; † 4. Oktober 1947 in Göttingen) war ein bedeutender deutscher Physiker und Nobelpreisträger. Er wird als Begründer der Quantenphysik betrachtet …   Deutsch Wikipedia

  • Max Planck — Max Karl Ernst Ludwig Planck (* 23. April 1858 in Kiel; † 4. Oktober 1947 in Göttingen) war ein bedeutender deutscher Physiker auf dem Gebiet der Theoretischen Physik. Er gilt als Begründer der Quantenphysik. Für die Entdeckung des plancksche …   Deutsch Wikipedia

  • Max Raabe — auf der Berlinale 2008 Max Raabe (* 12. Dezember 1962 in Lünen als Matthias Otto[1][2][3]) ist ein deutscher Sänger im …   Deutsch Wikipedia

  • Max Bill — Max Bill, né le 22 décembre 1908 à Winterthour, (Suisse) et mort le 9 décembre 1994 à Berlin, est un architecte, peintre, sculpteur, éditeur, théoricien de l’art et homme politique suisse. Sommaire 1 Biographie 2 Œuvres …   Wikipédia en Français

  • Max Frei-Sulzer — (* 8. März 1913[1] in Zürich[2]; † 14. Januar 1983[3]) war ein Schweizer Kriminalist. Inhaltsverzeichnis 1 Leben 2 Schriften …   Deutsch Wikipedia

  • Max Bill — Reloj de cocina diseñado por Max Bill para Junghans …   Wikipedia Español

  • Karloff-Zwick algorithm — The Karloff Zwick algorithm, in computational complexity theory, is a randomised approximation algorithm taking an instance of MAX 3SAT Boolean satisfiability problem as input. If the instance is satisfiable, then the expected weight of the… …   Wikipedia

  • Maximum satisfiability problem — In computational complexity theory, the Maximum Satisfiability problem (MAX SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula, that can be satisfied by some assignment. It is an FNP generalization of SAT …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”