Gap minskning
I beräkningskomplexitetsteori är en gapreduktion en reduktion till en viss typ av beslutsproblem, känt som ett c-gap-problem . Sådana minskningar ger information om hårdheten i att approximera lösningar på optimeringsproblem . Kortfattat hänvisar ett gapproblem till ett där målet är att skilja mellan fall där den bästa lösningen ligger över en tröskel från fall där den bästa lösningen ligger under en annan tröskel, så att de två tröskelvärdena har ett gap däremellan. Gap-reduktioner kan användas för att demonstrera inapproximability-resultat, som om ett problem kan approximeras till en bättre faktor än gapets storlek, då kan approximationsalgoritmen användas för att lösa motsvarande gap-problem.
c -gap problem
Vi definierar ett c -gap-problem enligt följande: givet ett optimeringsproblem (maximering eller minimering) P , skiljer det ekvivalenta c -gap-problemet mellan två fall, för en ingång k och en instans x av problemet P :
- . Här har den bästa lösningen på instans x av problem P en kostnad, eller poäng, under k .
- . Här har den bästa lösningen på instans x av problemet P en kostnad över c ⋅ k . Gapet mellan de två tröskelvärdena är alltså c .
Observera att närhelst OPT faller mellan tröskelvärdena finns det inga krav på vad utmatningen ska vara. En giltig algoritm för c -gap-problemet kan svara på vad som helst om OPT är mitt i gapet. Värdet c behöver inte vara konstant; det kan bero på storleken på instansen av P . Observera att c -approximera lösningen till en instans av P är minst lika svårt som att lösa c -gap-versionen av P .
Man kan definiera ett ( a , b ) -gapproblem på liknande sätt. Skillnaden är att tröskelvärdena inte beror på ingången; istället är den nedre tröskeln a och den övre tröskeln är b .
Gapproducerande minskning
En gap-producerande minskning är en reduktion från ett optimeringsproblem till ett c-gap-problem, så att en snabb lösning av c-gap-problemet skulle möjliggöra en snabb lösning av optimeringsproblemet. Termen gap-producerande uppstår från reduktionens natur: den optimala lösningen i optimeringsproblemet kartläggs till den motsatta sidan av gapet från varannan lösning via reduktion. Således skapas ett gap mellan den optimala lösningen och alla andra lösningar.
Ett enkelt exempel på en gap-producerande minskning är det icke-metriska Traveling Salesman-problemet (dvs där grafens kantkostnader inte behöver uppfylla villkoren för ett mått ). Vi kan reducera från det Hamiltonska vägproblemet på en given graf G = (V, E) till detta problem enligt följande: vi konstruerar en komplett graf G' = (V, E'), för resandeförsäljarproblemet. För varje kant e ∈ G' låter vi kostnaden för att korsa den vara 1 om e finns i den ursprungliga grafen G och ∞ annars. En Hamiltonsk bana i den ursprungliga grafen G existerar om och endast om det finns en resande säljarlösning med vikt (|V|-1). Men om det inte finns någon sådan Hamilton-bana, måste den bästa resande försäljarturen väga minst |V|. Således minskar Hamiltonian Path till |V|/(|V|-1)-gap icke-metrisk resande säljare.
Gapbevarande minskning
En gap-bevarande minskning är en minskning från ett c-gap-problem till ett c'-gap-problem. Mer specifikt får vi en instans x av ett problem A med |x| = n och vill reducera det till en instans x' av ett problem B med |x'| = n'. En gapbevarande reduktion från A till B är en uppsättning funktioner (k(n), k'(n'), c(n), c'(n')) så att
För minimeringsproblem:
- OPT A (x) ≤ k ⇒ OPT B (x') ≤ k', och
- OPT A (x) ≥ c⋅k ⇒ OPT B (x') ≥ c'⋅k'
För maximeringsproblem:
- OPT A (x) ≥ k ⇒ OPT B (x') ≥ k', och
- OPT A (x) ≤ k/c ⇒ OPT B (x') ≤ k'/c'
Om c' > c är detta en gap-förstärkande minskning .
Exempel
Max E3SAT
Detta problem är en form av det booleska tillfredsställbarhetsproblemet (SAT), där varje sats innehåller tre distinkta bokstaver och vi vill maximera antalet satser som är uppfyllda.
Håstad visade att (1/2+ε, 1-ε)-gap versionen av ett liknande problem, MAX E3-X(N)OR-SAT, är NP-hård. MAX E3-X(N)OR-SAT-problemet är en form av SAT där varje sats är XOR för tre distinkta bokstaver, varav exakt en är negerad. Vi kan minska från MAX E3-X(N)OR-SAT till MAX E3SAT enligt följande:
- En sats x i ⊕ x j ⊕ x k = 1 omvandlas till (xi ∨ x j ∨ x k ) ∧ (¬x i ∨ ¬x j ∨ x k ) ∧ (¬x i ∨ x j ∨ ¬x k ) ∧ (xi ∨ ¬x j ∨ ¬x k )
- En sats x i ⊕ x j ⊕ x k = 0 omvandlas till (¬x i ∨ ¬x j ∨ ¬x k ) ∧ (¬x i ∨ x j ∨ x k ) ∧ (xi ∨ ¬x j ∨ x k ) ∧ (xi ∨ x j ∨ ¬x k )
Om en klausul inte är uppfylld i den ursprungliga instansen av MAX E3-X(N)OR-SAT, kan högst tre av de fyra motsvarande satserna i vår MAX E3SAT-instans vara uppfyllda. Med hjälp av ett gap-argument följer det att en JA-instans av problemet har minst en (1-ε) bråkdel av klausulerna uppfyllda, medan en NO-instans av problemet har som mest en (1/2+ε)(1) + (1/2-ε)(3/4) = (7/8 + ε/4)-bråkdel av klausulerna uppfyllda. Sålunda följer att (7/8 + ε, 1 - ε)-gap MAX E3SAT är NP-hård. Observera att denna gräns är snäv, eftersom en slumpmässig tilldelning av variabler ger en förväntad 7/8 bråkdel av nöjda klausuler.
Etikettskydd
Etikettskyddsproblemet definieras enligt följande: givet en tvådelad graf G = (A∪B, E), med
- A = A 1 ∪ A 2 ∪ ... ∪ A k , |A| = n, och | Ai | = n/k
- B = B 1 ∪ B 2 ∪ ... ∪ B k , |B| = n, och | Bi | = n/k
Vi definierar en "överkant" mellan Ai och Bj om åtminstone en kant existerar från Ai till Bj i G, och definierar överkanten som ska täckas om åtminstone en kant från Ai till Bj täcks .
I max-rep- versionen av problemet tillåts vi välja en vertex från varje A i och varje B i , och vi strävar efter att maximera antalet täckta överkanter. I min-rep -versionen måste vi täcka varje överkant i grafen och vill minimera antalet hörn vi väljer. Manurangsi och Moshkovitz visar att (O(n 1/4 ), 1)-gapversionen av båda problemen är lösbar i polynomtid.