Karloff-Zwick-algoritm

Karloff -Zwick-algoritmen , i beräkningskomplexitetsteori , är en randomiserad approximationsalgoritm som tar en instans av MAX-3SAT booleskt tillfredsställelseproblem som indata. Om instansen är tillfredsställande är den förväntade vikten av den hittade tilldelningen minst 7/8 av optimal. Det finns starka bevis (men inte ett matematiskt bevis ) för att algoritmen uppnår 7/8 av optimal även på otillfredsställande MAX-3SAT-instanser. Howard Karloff och Uri Zwick presenterade algoritmen 1997.

Algoritmen är baserad på semidefinite programmering . Den kan avrandomiseras med t.ex. teknikerna från för att ge en deterministisk polynom-tidsalgoritm med samma approximationsgarantier.

Jämförelse med slumpmässig tilldelning

För det relaterade MAX-E3SAT-problemet, där alla satser i den ingående 3SAT-formeln garanterat har exakt tre bokstaver, uppfyller den enkla slumpmässiga approximationsalgoritmen som tilldelar ett sanningsvärde till varje variabel oberoende och enhetligt slumpmässigt 7/8 av alla satser i förväntan, oavsett om den ursprungliga formeln är tillfredsställande. Vidare kan denna enkla algoritm också lätt avrandomiseras med metoden för villkorade förväntningar . Karloff-Zwick-algoritmen kräver dock inte begränsningen att inmatningsformeln ska ha tre bokstaver i varje sats.

Optimalitet

Med utgångspunkt i tidigare arbete med PCP-satsen visade Johan Håstad att, om man antar P ≠ NP, kan ingen polynom-tidsalgoritm för MAX 3SAT uppnå ett prestandaförhållande som överstiger 7/8, även när det är begränsat till tillfredsställande instanser av problemet där varje klausul innehåller exakt tre bokstaver. Både Karloff–Zwick-algoritmen och ovanstående enkla algoritm är därför optimala i denna mening.