MAXEkSAT

MAXEkSAT är ett problem inom beräkningskomplexitetsteori som är en maximeringsversion av det booleska tillfredsställbarhetsproblemet 3SAT . I MAXEkSAT har varje sats exakt k literaler, var och en med distinkta variabler, och är i konjunktiv normalform . Dessa kallas k-CNF-formler. Problemet är att bestämma det maximala antalet satser som kan uppfyllas av en sanningstilldelning till variablerna i satserna.

Vi säger att en algoritm A ger en α - approximation till MAXEkSAT om, för någon fast positiv α mindre än eller lika med 1, och varje kCNF formel φ , A kan hitta en sanningstilldelning till variablerna av φ som kommer att uppfylla åtminstone en α -fraktion av det maximala antalet tillfredsställbara satser av φ .

Eftersom NP-hårda k -SAT-problemet (för k ≥ 3) är ekvivalent med att bestämma om motsvarande MAXEkSAT-instans har ett värde lika med antalet satser, måste MAXEkSAT också vara NP-hårt, vilket betyder att det inte finns någon polynomtidsalgoritm om inte P=NP . En naturlig nästa fråga är alltså att hitta ungefärliga lösningar: vad är det största reella talet α < 1 så att någon explicit P (komplexitet) -algoritm alltid hittar en lösning av storleken α·OPT , där OPT är (potentiellt svår att hitta) ) maximera uppdraget. Även om algoritmen är effektiv är det inte självklart hur man tar bort sitt beroende av slumpmässighet. Det finns problem relaterade till tillfredsställelsen av konjunktiva booleska formler i normalform.

Approximationsalgoritm

Det finns en enkel randomiserad polynom-tidsalgoritm som ger en $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ -approximation till MAXEkSAT: ställ in varje variabel oberoende till sann med sannolikhet 1 / 2 , annars ställ in den till falsk.

Varje given sats c är otillfredsställd endast om alla dess k ingående bokstaver utvärderas till falska. Eftersom varje bokstav i en sats har en 1 ⁄ 2 att utvärderas till sann oberoende av något av sanningsvärdet för någon av de andra bokstaverna, är sannolikheten att de alla är falska ( $\displaystyle \textstyle ({\frac {1}{2}})^{k}={\frac {1}{2^{k}}}}$ . Sannolikheten för att c verkligen är uppfylld är alltså ${\displaystyle \textstyle 1-{\frac {1}{2^{k}}}} ,$ så indikatorvariabeln $\textstyle 1_ {c}$ (det vill säga 1 om c är sant och 0 annars) har förväntan $\textstyle 1-{\frac {1}{2^{k}}}$ . Summan av alla indikatorvariabler överallt $\textstyle |C|$ satser är ${\displaystyle (\textstyle 1-{\frac {1}{2^{k}}})|C|} ,$ så genom förväntanslinjäritet tillfredsställer vi a $\textstyle \left (1-{\frac {1}{2^{k}}}\right)$ bråkdel av satserna i förväntan. Eftersom den optimala lösningen inte kan tillfredsställa mer än alla $\textstyle |C|$ i satserna har vi att $right)\cdot {\textit {OPT}}} , så algoritmen$ ${\textit {ALG}}=\left(1-{\frac {1}{2^{k}}}\right)\cdot |C|>\ left(1-{\frac {1}{2^{k}}$ $) {\displaystyle \textstyle \geq \left(1-{\frac {1}{2^{k}}}\right)}$ hittar en approximation till den verkliga optimala lösningen i förväntan.

Trots sina höga förväntningar kan den här algoritmen ibland snubbla på lösningar av värde som är lägre än förväntningarna vi beräknade ovan. Men över ett stort antal försök kommer den genomsnittliga andelen av nöjda klausuler att tendera mot $\textstyle \left(1-{\frac {1}{2^{k}}}\ höger)$ . Detta innebär två saker:

Det måste finnas en tilldelning som uppfyller minst en $\textstyle \left(1-{\frac {1}{2^{k}}}\right)$ del av satserna. Om det inte var det, skulle vi aldrig kunna uppnå ett så stort värde i genomsnitt över ett stort antal försök.
Om vi kör algoritmen ett stort antal gånger kommer åtminstone hälften av försöken (i förväntan) att tillfredsställa vissa ( $\displaystyle \textstyle (1-{\frac {2}{2^{k) }}})}$ bråkdel av satserna. Detta beror på att vilken mindre bråkdel som helst skulle få ner genomsnittet så mycket att algoritmen ibland måste uppfylla mer än 100 % av satserna för att komma tillbaka till sin förväntan på ( $\displaystyle \textstyle \left(1-{ \frac {2}{2^{k}}}\right)}$ , vilket inte kan hända. Utvidga detta med Markovs olikhet , åtminstone några $\textstyle 1-\left({\frac {1}{1+2^{k}\epsilon }}\right)$ -fraktion av försöken (i förväntan) kommer att uppfylla minst en $\textstyle \left(1-{\frac {1}{2^{k}}}-\ epsilon \right)$ -fraktion av satserna. Därför, för alla positiva ${\displaystyle \textstyle \epsilon } ,$ krävs det bara ett polynomantal slumpmässiga försök tills vi förväntar oss att hitta en tilldelning som uppfyller minst en ( $\displaystyle \textstyle \ left(1-{\frac {1}{2^{k}}}-\epsilon \right)}$ bråkdel av satserna.

En mer robust analys (som den i ) visar att vi faktiskt kommer att uppfylla åtminstone en $\textstyle \left(1-{\frac {1}{2^{k) }}}\right)$ -fraktion av satserna en konstant bråkdel av tiden (beroende endast på k ), utan förlust av $\textstyle \epsilon$ .

Derandomisering

Även om ovanstående algoritm är effektiv, är det inte självklart hur man tar bort dess beroende av slumpmässighet. Att prova alla möjliga slumpmässiga tilldelningar motsvarar den naiva brute force-metoden, så det kan ta exponentiell tid. Ett smart sätt att avrandomisera ovanstående i polynomtid är beroende av arbete med felkorrigerande koder, som uppfyller en $\textstyle \left(1-{\frac {1}{2^{k}} }\right)$ bråkdel av satserna i tidspolynom i indatastorleken (även om exponenten beror på k ).

Vi behöver en definition och två fakta för att hitta algoritmen.

Definition

$S\subseteq \{0,1\}^{n}$ är en $ℓ$ -vis oberoende källa om, för en enhetligt vald slumpmässig $(x 1, x 2, ..., x n) \in S,$ $x 1, x 2, ..., x n$ är $ℓ$ -vis oberoende slumpvariabler.

Fakta 1

Observera att en sådan tilldelning kan hittas bland element i vilken $ℓ$ -vis oberoende källa som helst över n binära variabler . Detta är lättare att se när du inser att en $ℓ$ -vis oberoende källa egentligen bara är vilken uppsättning binära vektorer som helst över ${0, 1} n$ med egenskapen att alla begränsningar av dessa vektorer till $ℓ$ koordinater måste presentera de 2 ^ℓ möjliga binära kombinationer lika många gånger.

Fakta 2

Kom ihåg att BCH _{2, m , d} är en $[n=2^{m},n-1-\lceil {d-2}/2\rceil m,d]_{2}$ linjär kod.

Det finns en $ℓ$ -vis oberoende källa av storlek $O(n^{\lfloor \ell /2\rfloor })$ , nämligen dualen av en $BCH 2,log n, ℓ +1-$ kod, som är en linjär kod. Eftersom varje BCH-kod kan presenteras som en polynom-tidsberäknbar begränsning av en relaterad Reed Solomon -kod, som i sig är starkt explicit, finns det en polynom-tidsalgoritm för att hitta en sådan tilldelning till x _i :en. Faktabeviset 2 kan hittas på Dual of BCH är en oberoende källa .

Översikt över algoritmen

Algoritmen fungerar genom att generera $BCH 2,log n, ℓ +1$ , beräkna dess dubbla (som som en mängd är en $ℓ$ -vis oberoende källa) och behandla varje element (kodord) i den källan som en sanningstilldelning till de n variablerna i φ . Minst en av dem kommer att uppfylla minst $1 - 2 - ℓ$ av satserna i φ , närhelst φ är i kCNF-form, $k = ℓ$ .

Relaterade problem

Det finns många problem relaterade till tillfredsställelsen av konjunktiva booleska formler i normalform.

Beslutsproblem :
- 2SAT
- 3SAT
Optimeringsproblem, där målet är att maximera antalet uppfyllda klausuler:
- MAX-SAT , och motsvarande viktade version Weighted MAX-SAT
- MAX -k SAT, där varje sats har exakt k variabler:
  - MAX-2SAT
  - MAX-3SAT
  - MAXEkSAT
- Problemet med partiell maximal tillfredsställelse (PMAX-SAT) frågar efter det maximala antalet satser som kan uppfyllas av vilken som helst tilldelning av en given delmängd av satser. Resten av klausulerna måste vara uppfyllda.
- Problemet med mjuk tillfredsställelse (soft-SAT), givet en uppsättning SAT-problem, frågar efter det maximala antalet uppsättningar som kan uppfyllas av en tilldelning.
- Minsta tillfredsställelseproblem.
MAX-SAT-problemet kan utvidgas till det fall där variablerna för problemet med begränsningstillfredsställelse tillhör uppsättningen av reella. Problemet är att hitta den minsta q så att den q - avslappnade skärningspunkten mellan begränsningarna inte är tom.

Se även

externa länkar

Coding Theory notes vid MIT