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 + δ for some δ > 0.

ee also

*PCP (complexity)


*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
* Rudich et al., "Computational Complexity Theory," IAS/Park City Mathematics Series, 2004 page 108 ISBN 0-8218-2872-X

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • 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… …   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”