Izolační lemma - Isolation lemma

v teoretická informatika, termín izolační lemma (nebo izolační lemma) odkazuje na randomizované algoritmy které snižují počet řešení problému na jedno, pokud by řešení existovalo. Toho je dosaženo konstrukcí náhodných omezení tak, aby s nezanedbatelnou pravděpodobností přesně jedno řešení splňovalo tato další omezení, pokud není prostor řešení prázdný. mít důležité aplikace v informatice, jako je Věta Valiant – Vazirani a Todova věta v teorie výpočetní složitosti.

První izolační lemma představil Valiant & Vazirani (1986) I když ne pod tímto jménem. Jejich izolační lemma vybírá náhodný počet náhodných hyperplánů a má tu vlastnost, že s nezanedbatelnou pravděpodobností průsečík jakéhokoli fixního neprázdného prostoru řešení se zvolenými hyperplany obsahuje právě jeden prvek. To stačí k zobrazení Věta Valiant – Vazirani: existuje randomizovaná redukce polynomiálního času z problém uspokojivosti pro booleovské vzorce k problému zjistit, zda má booleovský vzorec jedinečné řešení.Mulmuley, Vazirani & Vazirani (1987) představil izolační lemma trochu jiného druhu: Zde se každé souřadnici prostoru řešení přidělí náhodná váha v určitém rozsahu celých čísel a vlastnost je, že se nezanedbatelnou pravděpodobností je v prostoru řešení právě jeden prvek který má minimální váhu. To lze použít k získání randomizovaného paralelního algoritmu pro maximální shoda problém.

V literatuře byla zavedena silnější izolační lemata, aby vyhovovala různým potřebám v různých prostředích. Například izolační lemma Chari, Rohatgi a Srinivasan (1993) má podobné záruky jako Mulmuley et al., ale používá méně náhodných bitů. V kontextu exponenciální časová hypotéza, Calabro a kol. (2008) prokázat izolační lemma pro vzorce k-CNF Noam Ta-Shma^[1] dává izolační lemma s mírně silnějšími parametry a dává netriviální výsledky, i když je velikost váhové domény menší než počet proměnných.

Izolační lemma Mulmuley, Vazirani a Vazirani

Žádný lineární program s náhodně zvolenou funkcí lineárních nákladů má jedinečné optimum s vysokou pravděpodobností. Izolační lemma Mulmuley, Vazirani a Vazirani rozšiřuje tuto skutečnost na libovolný množiny a funkce náhodných nákladů, která je vzorkována pomocí málo náhodné bity.

Lemma. Nechat ${ displaystyle n}$ a ${ displaystyle N}$ být kladná celá čísla a nechat ${ displaystyle { mathcal {F}}}$ být libovolnou rodinou podmnožin vesmíru ${ displaystyle {1, tečky, n }}$. Předpokládejme každý prvek ${ displaystyle x in {1, tečky, n }}$ ve vesmíru dostává celočíselnou váhu ${ displaystyle w (x)}$, z nichž každý je vybrán nezávisle a rovnoměrně náhodně z ${ displaystyle {1, tečky, N }}$. Hmotnost sady S v ${ displaystyle { mathcal {F}}}$ je definován jako

${ displaystyle w (S) = součet _ {x v S} w (x) ,.}$

Potom, alespoň s pravděpodobností ${ displaystyle 1-n / N}$, tady je unikátní stanovené v ${ displaystyle { mathcal {F}}}$ která má minimální hmotnost mezi všemi sadami ${ displaystyle { mathcal {F}}}$.

Je pozoruhodné, že lemma nepředpokládá nic o povaze rodiny ${ displaystyle { mathcal {F}}}$: například ${ displaystyle { mathcal {F}}}$ může zahrnovat Všechno ${ displaystyle 2 ^ {n} -1}$ neprázdné podmnožiny. Vzhledem k tomu, hmotnost každé sady v ${ displaystyle { mathcal {F}}}$ je mezi ${ displaystyle 1}$ a ${ displaystyle nN}$ v průměru bude ${ displaystyle (2 ^ {n} -1) / (nN)}$ sady každé možné hmotnosti. Přesto s velkou pravděpodobností existuje jedinečná sada, která má minimální hmotnost.

Příklady / aplikace

• Původní aplikace spočívala v dokonalém párování v grafu s minimální hmotností (nebo maximální hmotností). Každému okraji je v {1,…, 2 přiřazena náhodná váham}, a ${ displaystyle { mathcal {F}}}$ je sada dokonalých shody, takže s pravděpodobností alespoň 1/2 existuje jedinečná dokonalá shoda. Když každý neurčitý ${ displaystyle x_ {ij}}$ v Tutte matrix grafu je nahrazen ${ displaystyle 2 ^ {w_ {ij}}}$ kde ${ displaystyle w_ {ij}}$ je náhodná váha hrany, můžeme ukázat, že determinant matice je nenulový, a dále ji použít k nalezení shody.
• Obecněji článek také zaznamenal, že jakýkoli problém s vyhledáváním formuláře „Vzhledem k nastavenému systému ${ displaystyle (S, { mathcal {F}})}$, najít soubor v ${ displaystyle { mathcal {F}}}$„lze omezit na rozhodovací problém formuláře“ Existuje soubor ${ displaystyle { mathcal {F}}}$ s maximální hmotností kUkázalo se například, jak vyřešit následující problém, který představují Papadimitriou a Yannakakis, pro který (v době psaní článku) není znám žádný deterministický algoritmus polynomiálního času: daný graf a podmnožina hran označen jako „červený“, najděte perfektní shodu s přesně k červené okraje.
• The Věta Valiant – Vazirani, týkající se jedinečných řešení NP-úplných problémů, má jednodušší důkaz pomocí izolačního lemmatu. To dokazuje randomizované snížení z KLIKA na UNIQUE-CLIQUE.^[3]
• Ben-David, Chor & Goldreich (1989) použít důkaz Valiant-Vazirani při redukci vyhledávání na rozhodnutí pro průměrná složitost.
• Avi Wigderson použil izolační lemma v roce 1994 k náhodnému snížení z NL UL, a tím dokázat, že NL / poly ⊆ ⊕L / poly.^[4] Reinhardt a Allender později znovu použili izolační lemma k prokázání, že NL / poly = UL / poly.^[5]
• Kniha Hemaspaandry a Ogihary má kapitolu o izolační technice, včetně zevšeobecnění.^[6]
• Izolační lemma bylo navrženo jako základ schématu pro digitální vodoznak.^[7]
• V konkrétních případech probíhají práce na derandomizaci izolačního lemmatu^[8] a o jeho použití pro testování identity.^[9]

Poznámky

Reference

externí odkazy

• Oblíbené věty: Unikátní svědkové podle Lance Fortnow
• Izolační lemma a další podle Richard J. Lipton