NP (složitost) - NP (complexity)

Tento článek obsahuje seznam obecných Reference, ale zůstává z velké části neověřený, protože postrádá dostatečné odpovídající vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Říjen 2015) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Nevyřešený problém v informatice: ${displaystyle {mathsf {P {overset {?} {=}} NP}}}$ (více nevyřešených problémů v informatice)

Eulerův diagram pro P, NP, NP-kompletní, a NP-tvrdé soubor problémů. Za předpokladu, že P ≠ NP, existence problémů uvnitř NP, ale mimo obojí P a NP-kompletní bylo založil Ladner.^[1]

v teorie výpočetní složitosti, NP (nedeterministický polynomiální čas) je třída složitosti slouží ke klasifikaci rozhodovací problémy. NP je soubor problémů s rozhodováním, pro které problémové instance, kde odpověď zní „ano“, mít důkazy ověřitelné v polynomiální čas podle a deterministický Turingův stroj.^{[2][Poznámka 1]}

Ekvivalentní definicí NP je soubor rozhodovacích problémů řešitelný v polynomiálním čase o a nedeterministický Turingův stroj. Tato definice je základem pro zkratku NP; "nedeterministické „polynomický čas.“ Tyto dvě definice jsou ekvivalentní, protože algoritmus založený na Turingově stroji se skládá ze dvou fází, z nichž první sestává z hádky o řešení, která je generována nedeterministickým způsobem, zatímco druhá fáze se skládá deterministického algoritmu, který ověří, zda je odhad řešením problému.^[3]

Rozhodovacím problémům jsou přiřazeny třídy složitosti (například NP) na základě nejrychleji známých algoritmů. Proto mohou problémy s rozhodováním změnit třídy, pokud jsou objeveny rychlejší algoritmy.

Je snadné vidět, že třída složitosti P (všechny problémy řešitelné, deterministicky, v polynomiálním čase) je obsažen v NP (problémy, kde lze řešení ověřit v polynomiálním čase), protože pokud je problém řešitelný v polynomiálním čase, pak je řešení také ověřitelné v polynomiálním čase jednoduchým řešením problému . NP však obsahuje mnohem více problémů^{[Poznámka 2]}, z nichž nejtěžší jsou tzv NP-kompletní problémy. Algoritmus řešení takového problému v polynomiálním čase je také schopen vyřešit jakýkoli jiný NP problém v polynomiálním čase. Nejdůležitější Problém P versus NP („P = NP?“), se ptá, zda existují polynomiální časové algoritmy pro řešení NP-complete a jako důsledek všech NP problémů. Obecně se věří, že tomu tak není.^[4]

Třída složitosti NP souvisí se třídou složitosti co-NP u nichž lze odpověď „ne“ ověřit v polynomiálním čase. Zda NP = co-NP je nebo není další vynikající otázka v teorii složitosti.^[5]

Formální definice

Třídu složitosti NP lze definovat z hlediska NTIME jak následuje:

${displaystyle {mathsf {NP}} = igcup _ {kin mathbb {N}} {mathsf {NTIME}} (n ^ {k}).}$

kde ${displaystyle {mathsf {NTIME}} (n ^ {k})}$ je soubor rozhodovacích problémů, které lze vyřešit pomocí a nedeterministický Turingův stroj v ${displaystyle O (n ^ {k})}$ čas.

Alternativně lze NP definovat pomocí deterministických Turingových strojů jako ověřovatelů. A Jazyk L je v NP právě tehdy, pokud existují polynomy p a qa deterministický Turingův stroj M, takový, že

• Pro všechny X a y, stroj M běží v čase p(|X|) na vstupu ${displaystyle (x, y)}$
• Pro všechny X v L, existuje řetězec y délky q(|X|) takové, že ${displaystyle M (x, y) = 1}$
• Pro všechny X ne v L a všechny řetězce y délky q(|X|), ${displaystyle M (x, y) = 0}$

Pozadí

Mnoho počítačová věda problémy jsou obsaženy v NP, jako rozhodovací verze mnoha Vyhledávání a optimalizační problémy.

Definice založená na ověřovateli

Abychom vysvětlili definici NP na základě ověřovatele, zvažte problém podmnožiny: Předpokládejme, že nějaké dostáváme celá čísla, {−7, −3, −2, 5, 8} a my bychom chtěli vědět, zda některá z těchto celých čísel sčítají až nulu. Zde je odpověď „ano“, protože celá čísla {−3, −2, 5} odpovídají součtu (−3) + (−2) + 5 = 0. Úkol rozhodnout, zda taková podmnožina s nulovým součtem existuje, se nazývá problém podmnožiny.

Abychom odpověděli, pokud některá z celých čísel přidají nulu, můžeme vytvořit algoritmus, který získá všechny možné podmnožiny. Jak se zvyšuje počet celých čísel, která vkládáme do algoritmu, exponenciálně roste jak počet podmnožin, tak výpočetní čas.

Všimněte si však, že pokud dostaneme určitou podmnožinu, můžeme efektivně ověřovat zda je součet podmnožiny nula, sečtením celých čísel podmnožiny. Pokud je součet nula, je tato podmnožina a důkaz nebo svědek odpověď je „ano“. Algoritmus, který ověří, zda má daná podmnožina součet nula, je a ověřovatel. Je zřejmé, že součet celých čísel podmnožiny lze provést v polynomiálním čase a problém součtu podmnožiny je tedy v NP.

Výše uvedený příklad lze zobecnit pro jakýkoli rozhodovací problém. Vzhledem k jakémukoli případu problému ${displaystyle Pi}$ a svědek W, pokud existuje a ověřovatel V tak, že vzhledem k objednanému páru (I, W) jako vstupu V vrátí „ano“ v polynomiálním čase, pokud svědek prokáže, že odpověď je „ano“ nebo „ne“ v polynomiálním čase, pak ${displaystyle Pi}$ je v NP.

Verze „ne“ s odpovědí na tento problém je uvedena jako: „vzhledem k konečné množině celých čísel má každá neprázdná podmnožina nenulovou částku?“. Definice NP založená na ověřovateli ano ne vyžadovat účinného ověřovatele odpovědí „ne“. Třída problémů s takovými ověřovateli odpovědí „ne“ se nazývá co-NP. Ve skutečnosti jde o otevřenou otázku, zda všechny problémy v NP mají také ověřovatele „ne“ odpovědí a jsou tedy v co-NP.

V některé literatuře se ověřovatel nazývá „ověřovatel“ a svědek „osvědčení ".^[2]

Definice stroje

Ekvivalentní k definici založené na ověřovateli je následující charakterizace: NP je třída rozhodovací problémy řešitelný a nedeterministický Turingův stroj který běží dovnitř polynomiální čas. To znamená, problém s rozhodnutím ${displaystyle Pi}$ je v NP kdykoli ${displaystyle Pi}$ je rozpoznán nějakým nedeterministickým Turingovým strojem v polynomiálním čase ${displaystyle M}$ s existenční podmínka přijetí, znamenající, že ${displaystyle win Pi}$ právě když nějaká výpočetní cesta z ${displaystyle M (w)}$ vede k přijímajícímu stavu. Tato definice je ekvivalentní definici založené na ověřovateli, protože nedeterministický Turingův stroj by mohl vyřešit problém NP v polynomiálním čase nedeterministickým výběrem certifikátu a spuštěním ověřovatele na certifikátu. Podobně, pokud takový stroj existuje, lze z něj přirozeně sestrojit polynomiální ověřovač času.

V tomto světle můžeme definovat co-NP dually jako třídu rozhodovacích problémů rozpoznatelných polynomiálně-časově nedeterministickými Turingovými stroji s existenční podmínkou odmítnutí. Protože podmínka existenčního odmítnutí je přesně to samé jako a podmínka univerzálního přijetí, můžeme rozumět NP vs. co-NP otázka jako otázka, zda mají existenciální a univerzální podmínky přijetí stejnou expresivní sílu pro třídu polynomiálně-neurčitých Turingových strojů.

Vlastnosti

NP je uzavřen pod svaz, průsečík, zřetězení, Kleene hvězda a obrácení. Není známo, zda je NP uzavřen pod doplněk (tato otázka je takzvaná otázka „NP versus co-NP“)

Proč je těžké vyřešit některé NP problémy

Vzhledem k mnoha důležitým problémům v této třídě bylo vyvinuto značné úsilí k nalezení algoritmů polynomiálního času pro řešení problémů v NP. V NP však stále existuje velké množství problémů, které takové pokusy vzdorují, což se zdá být nutné superpolynomický čas. Zda tyto problémy nejsou rozhodující v polynomiálním čase, je jednou z největších otevřených otázek počítačová věda (vidět P versus NP ("P = NP") problém pro podrobnou diskusi).

Důležitým pojmem v této souvislosti je soubor NP-kompletní rozhodovací problémy, což je podmnožina NP a lze ji neformálně popsat jako „nejtěžší“ problémy NP. Pokud existuje algoritmus polynomiálního času pro sudé jeden z nich, pak existuje algoritmus polynomiálního času pro Všechno problémy v NP. Z tohoto důvodu a protože specializovaný výzkum nedokázal najít polynomiální algoritmus pro jakýkoli NP-úplný problém, jakmile se problém ukáže jako NP-úplný, je to obecně považováno za znamení, že je nepravděpodobné, že by polynomiální algoritmus pro tento problém existovat.

Avšak při praktickém použití lze místo polynomiálního času místo vynaložení výpočetních zdrojů na hledání optimálního řešení najít dostatečně dobré (ale potenciálně neoptimální) řešení. Aplikace některých problémů v reálném životě jsou také snazší než jejich teoretické ekvivalenty.

Rovnocennost definic

Tyto dvě definice NP jako třídy problémů řešitelné nedeterministicky Turingův stroj (TM) v polynomiálním čase a třída problémů ověřitelných deterministickým Turingovým strojem v polynomiálním čase jsou ekvivalentní. Důkaz popisuje mnoho učebnic, například Sipser's Úvod do teorie výpočtu, oddíl 7.3.

Abychom to ukázali, nejprve předpokládejme, že máme deterministický ověřovatel. Nedeterministický stroj může jednoduše nedeterministicky spustit ověřovatel na všech možných řetězcích kontroly (vyžaduje to jen polynomiálně mnoho kroků, protože v každém kroku může nedeterministicky zvolit další znak v řetězci kontroly a délka řetězce kontroly musí být polynomiálně ohraničená). Pokud je nějaký důkaz platný, některá cesta bude akceptována; pokud není platný žádný důkaz, řetězec není v jazyce a bude odmítnut.

Naopak, předpokládejme, že máme nedeterministickou TM nazvanou A, která přijímá daný jazyk L. V každém z jeho polynomiálně mnoha kroků stroj výpočetní strom větví nanejvýš konečným počtem směrů. Musí existovat alespoň jedna akceptační cesta a řetězec popisující tuto cestu je důkaz dodaný ověřovateli. Ověřovatel pak může deterministicky simulovat A, sledovat pouze akceptační cestu a na konci ověřit, že přijímá. Pokud A odmítne vstup, neexistuje žádná akceptační cesta a ověřovatel vždy odmítne.

Vztah k jiným třídám

NP obsahuje všechny problémy v P, protože lze ověřit jakoukoli instanci problému jednoduše ignorováním důkazu a jeho řešením. NP je obsažen v PSPACE —K tomu, aby to bylo zřejmé, postačí zkonstruovat stroj PSPACE, který prochází všemi řetězci kontroly a každý z nich přivádí k polynomiálnímu časovému ověření. Protože stroj s polynomiálním časem dokáže číst pouze polynomiálně mnoho bitů, nemůže používat více než polynomiální prostor, ani nemůže číst řetězec důkazů, který zabírá více než polynomiální prostor (takže nemusíme uvažovat o důkazech delší než tento). NP je také obsažen v EXPTIME, protože stejný algoritmus pracuje v exponenciálním čase.

co-NP obsahuje ty problémy, které mají jednoduchý důkaz Ne instance, někdy nazývané protiklady. Například, testování primality triviálně spočívá v co-NP, protože lze vyvrátit primitivitu celého čísla pouhým dodáním netriviálního faktoru. NP a co-NP společně tvoří první úroveň v polynomiální hierarchie, vyšší než P.

NP je definován pouze pomocí deterministických strojů. Pokud povolíme, aby byl ověřovatel pravděpodobnostní (toto však nemusí být nutně stroj BPP^[6]), dostaneme třídu MA řešitelné pomocí Protokol Arthur-Merlin bez komunikace mezi Arthurem a Merlinem.

NP je třída rozhodovací problémy; analogická třída funkčních problémů je FNP.

Jediné známé přísné inkluze pocházely z věta o časové hierarchii a věta o hierarchii prostoru, respektive jsou ${displaystyle {mathsf {NPsubsetneq NEXPTIME}}}$ a ${displaystyle {mathsf {NPsubsetneq EXPSPACE}}}$.

Další charakterizace

Ve smyslu teorie popisné složitosti, NP přesně odpovídá množině jazyků definovatelných existenciálně logika druhého řádu (Faginova věta ).

NP lze považovat za velmi jednoduchý typ interaktivní kontrolní systém, kde prover přichází s osvědčením o ověření a ověřovatelem je deterministický stroj s polynomiálním časem, který jej kontroluje. Je to úplné, protože správný kontrolní řetězec jej přijme, pokud existuje, a je zdravý, protože ověřovatel nemůže přijmout, pokud neexistuje žádný přijatelný kontrolní řetězec.

Hlavním výsledkem teorie složitosti je, že NP lze charakterizovat jako problémy řešitelné pomocí pravděpodobnostně ověřitelné důkazy kde ověřovatel používá O (log n) náhodné bity a zkoumá pouze konstantní počet bitů zkušebního řetězce (třída PCP(log n, 1)). Více neformálně to znamená, že výše popsaný ověřovatel NP může být nahrazen takovým, který pouze „namátkově zkontroluje“ několik míst v řetězci kontroly a použití omezeného počtu převrácení mincí může určit správnou odpověď s vysokou pravděpodobností. To umožňuje několik výsledků o tvrdosti aproximační algoritmy být prokázáno.

Příklad

Toto je seznam některých problémů, které jsou v NP:

Všechny problémy v P, označeno ${displaystyle {mathsf {Psubseteq NP}}}$. Dostal certifikát na problém v P, můžeme certifikát ignorovat a vyřešit problém v polynomiálním čase.

Rozhodovací verze problém obchodního cestujícího je v NP. Vzhledem k tomu, vstupní matice vzdáleností mezi n měst je problém určit, zda existuje trasa navštěvující všechna města s celkovou vzdáleností menší než k.

Důkazem může být jednoduše seznam měst. Pak lze ověření jasně provést v polynomiálním čase. Jednoduše přidá maticové záznamy odpovídající cestám mezi městy.

A nedeterministický Turingův stroj můžete najít takovou trasu následujícím způsobem:

• V každém městě, které navštíví, bude „hádat“ další město, které má navštívit, dokud nenavštíví každý vrchol. Pokud se zasekne, okamžitě se zastaví.
• Na konci ověří, že trasa, kterou prošel, stála méně než k v Ó (n) čas.

Jeden může myslet na každý odhad jako „rozvětvení „nová kopie Turingova stroje, která sleduje každou z možných cest vpřed, a pokud alespoň jeden stroj najde trasu vzdálenosti menší než k, tento stroj přijímá vstup. (Ekvivalentně to lze považovat za jediný Turingův stroj, který vždy správně odhadne)

A binární vyhledávání v rozsahu možných vzdáleností lze převést rozhodovací verzi Traveling Salesman na optimalizační verzi opakovaným voláním rozhodovací verze (několikanásobný polynom).^{[Citace je zapotřebí ]}

Verze problému s rozhodnutím problém celočíselné faktorizace: zadaná celá čísla n a k, existuje faktor F s 1 < F < k a F dělení n?^{[Citace je zapotřebí ]}

The Problém izomorfismu podgrafu stanovení, zda graf G obsahuje podgraf, který je izomorfní s grafem H.

The booleovský problém uspokojivosti, kde chceme vědět, zda je či není určitý vzorec v výroková logika s booleovskými proměnnými platí pro určitou hodnotu proměnných.

Viz také

• Turingův stroj

Poznámky

Reference

Další čtení

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, a Clifford Stein. Úvod do algoritmů, Druhé vydání. MIT Press a McGraw-Hill, 2001. ISBN  0-262-03293-7. Oddíl 34.2: Ověření polynomiálního času, s. 979–983.
• Michael Sipser (1997). Úvod do teorie výpočtu. PWS Publishing. ISBN  0-534-94728-X. Sekce 7.3–7.5 (Třída NP, NP-úplnost, Další NP-úplné problémy), s. 241–271.
• David Harel, Yishai Feldman. Algorithmics: The Spirit of Computing, Addison-Wesley, Reading, MA, 3. vydání, 2004.

externí odkazy

• Složitost Zoo: NP
• Americký vědec základ pro tradiční a nedávný výzkum teorie složitosti: „Náhodné algoritmy“