Problém P versus NP - P versus NP problem

Question, Web Fundamentals.svgNevyřešený problém v informatice:
Je-li snadné ověřit správnost řešení problému, musí být problém snadno vyřešen?
(více nevyřešených problémů v informatice)

Schéma tříd složitosti za předpokladu, že P ≠  NP. Existence problémů uvnitř NP ale mimo oba P a NP- za tohoto předpokladu byla úplná zřízena Ladnerova věta.[1]
Problémy s cenou tisíciletí

The Problém P versus NP je hlavní nevyřešený problém v informatice. Ptá se, zda lze každý problém, jehož řešení lze rychle ověřit, rychle vyřešit.

Je to jeden ze sedmi Problémy s cenou tisíciletí vybráno Hliněný matematický institut, z nichž každý nese cenu 1 000 000 USD za první správné řešení.

Neformální termín rychle, použitý výše, znamená existenci algoritmus řešení úkolu, který běží polynomiální čas, takže čas na dokončení úkolu se liší podle a polynomiální funkce na velikosti vstupu do algoritmu (na rozdíl od, řekněme, exponenciální čas ). Obecná třída otázek, na kterou může nějaký algoritmus poskytnout odpověď v polynomiálním čase, se nazývá „třída“ P" nebo prostě "P". U některých otázek neexistuje žádný známý způsob, jak rychle najít odpověď, ale pokud je jednomu poskytnuta informace ukazující, jaká je odpověď, je možné ji rychle ověřit. Třída otázek, na kterou lze odpovědět ověřeno v polynomiálním čase se nazývá NP, což znamená „nedeterministický polynomiální čas“.[Poznámka 1]

Odpověď na P = NP otázka by určila, zda problémy, které lze ověřit v polynomiálním čase, lze také vyřešit v polynomiálním čase. Pokud se to ukázalo P ≠ NP, o kterém se všeobecně věří, by to znamenalo, že v něm jsou problémy NP které je těžší vypočítat než ověřit: nemohly být vyřešeny v polynomiálním čase, ale odpověď mohla být ověřena v polynomiálním čase.

Kromě důležitého problému ve výpočetní teorii by důkaz v obou směrech měl hluboké důsledky pro matematiku, kryptografii, výzkum algoritmů, umělá inteligence, herní teorie, zpracování multimédií, filozofie, ekonomika a mnoho dalších oborů.[2]

Příklad

Zvážit Sudoku, hra, kde hráč dostane částečně vyplněnou mřížku čísel a pokusí se ji dokončit podle určitých pravidel. Vzhledem k neúplné mřížce sudoku jakékoli velikosti existuje alespoň jedno legální řešení? Jakékoli navrhované řešení je snadno ověřitelné a čas na kontrolu řešení roste pomalu (polynomiálně), jak se mřížka zvětšuje. Všechny známé algoritmy pro hledání řešení však u obtížných příkladů vyžadují čas, který roste exponenciálně, jak se mřížka zvětšuje. Sudoku je tedy uvnitř NP (rychle zkontrolovatelné), ale nezdá se, že je v P (rychle řešitelné). Tisíce dalších problémů se zdají být podobné v tom, že se rychle kontrolují, ale pomalu se řeší. Vědci prokázali, že mnoho problémů v NP mít extra vlastnost, že rychlé řešení kteréhokoli z nich lze použít k vytvoření rychlého řešení jakéhokoli jiného problému v NP, vlastnost s názvem NP-úplnost. Desetiletí hledání nepřineslo rychlé řešení žádného z těchto problémů, takže většina vědců má podezření, že žádný z těchto problémů nelze rychle vyřešit. To však nikdy nebylo prokázáno.

Dějiny

Přesné prohlášení P proti NP problém zavedl v roce 1971 Stephen Cook ve své seminární práci „Složitost postupů dokazování věty“[3] (a nezávisle na Leonid Levin v roce 1973[4]) a mnozí jej považují za nejdůležitější otevřený problém v počítačová věda.[5]

Ačkoliv P proti NP problém byl formálně definován v roce 1971, došlo k předchozím narážkám na související problémy, obtížnost dokazování a možné důsledky. V roce 1955 matematik John Nash napsal dopis NSA kde spekuloval, že prolomení dostatečně složitého kódu bude vyžadovat časovou exponenciál v délce klíče.[6] Pokud se to prokáže (a Nash byl vhodně skeptický), znamenalo by to, co se nyní nazývá P ≠ NP, protože navrhovaný klíč lze snadno ověřit v polynomiálním čase. Další zmínka o základním problému se objevila v dopise z roku 1956, který napsal Kurt Gödel na John von Neumann. Gödel se zeptal, zda dokazování věty (nyní známé jako co-NP-kompletní ) lze vyřešit v kvadratický nebo lineární čas,[7] a poukázal na jeden z nejdůležitějších důsledků - že pokud ano, pak by mohlo být automatizováno objevování matematických důkazů.

Kontext

Vztah mezi třídy složitosti P a NP je studován v teorie výpočetní složitosti, část teorie výpočtu řešení zdrojů potřebných během výpočtu k vyřešení daného problému. Nejběžnějšími prostředky jsou čas (kolik kroků je potřeba k vyřešení problému) a prostor (kolik paměti je potřeba k vyřešení problému).

Při této analýze je vyžadován model počítače, pro který musí být analyzován čas. Typicky takové modely předpokládají, že počítač je deterministický (vzhledem k aktuálnímu stavu počítače a jakýmkoli vstupům existuje pouze jedna možná akce, kterou by počítač mohl provést) a sekvenční (provádí akce jeden po druhém).

V této teorii třída P se skládá ze všech těch rozhodovací problémy (definovaný níže ), které lze vyřešit na deterministickém sekvenčním stroji za určitou dobu polynomiální ve velikosti vstupu; třída NP se skládá ze všech těch rozhodovacích problémů, jejichž pozitivní řešení lze ověřit v polynomiální čas vzhledem k tomu, správné informace, nebo ekvivalentně, jehož řešení lze nalézt v polynomiálním čase na a nedeterministický stroj.[8] Jasně, P ⊆ NP. Pravděpodobně největší otevřená otázka v teoretická informatika týká se vztahu mezi těmito dvěma třídami:

Je P rovná NP?

Od roku 2002 William Gasarch provedla tři průzkumy veřejného mínění výzkumných pracovníků týkajících se této a souvisejících otázek.[9][10][11] Důvěra, že P ≠ NP roste - v roce 2019 věřilo 88% P ≠ NP, na rozdíl od 83% v roce 2012 a 61% v roce 2002. Když se omezí na odborníky, odpovědi z roku 2019 se domnívají, že 99% věří P ≠ NP.[11]

NP-úplnost

Eulerův diagram pro P, NP, NP-kompletní a NP-tvrdá sada problémů (vyjma prázdného jazyka a jeho doplňku, ke kterému patří P ale nejsou NP-kompletní)
Hlavní článek: NP-úplnost

Zaútočit na P = NP otázka, pojem NP- úplnost je velmi užitečná. NP-kompletní problémy jsou souborem problémů, z nichž každý jiný NP-problém lze snížit v polynomiálním čase a jehož řešení může být stále ověřeno v polynomiálním čase. To je kdokoli NP problém lze převést na některý z NP-kompletní problémy. Neformálně, an NP-kompletní problém je NP problém, který je přinejmenším stejně "tvrdý" jako jakýkoli jiný problém v systému Windows NP.

NP-tvrdý problémy jsou přinejmenším stejně těžké jako NP problémy, tj. všechny NP problémy jim lze snížit (v polynomiálním čase). NP-tvrdé problémy nemusí být v NP, tj. nemusí mít řešení ověřitelná v polynomiálním čase.

Například Booleovský problém uspokojivosti je NP-kompletní Cook – Levinova věta, tak žádný instance žádný problém v NP lze mechanicky transformovat na instanci booleovského problému uspokojivosti v polynomiálním čase. Booleovský problém uspokojivosti je jedním z mnoha takových NP-kompletní problémy. Jestli nějaký NP-kompletní problém je v P, pak by to následovalo P = NP. Ukázalo se však, že existuje mnoho důležitých problémů NP-kompletní a pro žádný z nich není znám žádný rychlý algoritmus.

Na základě samotné definice není zřejmé, že NP- existují úplné problémy; nicméně triviální a vykonstruovaný NP-kompletní problém může být formulován následovně: uveden popis a Turingův stroj M zaručeně se zastaví v polynomiálním čase, existuje vstup polynomiální velikosti, který M přijme?[12] To je v NP protože (zadaný vstup) je snadné zkontrolovat, zda M přijímá vstup simulací M; to je NP-kompletní, protože ověřovatel pro jakoukoli konkrétní instanci problému v NP lze kódovat jako stroj s polynomiálním časem M který vyžaduje ověření řešení jako vstupu. Pak otázka, zda je instance instance ano nebo ne, je určena tím, zda existuje platný vstup.

První přirozený problém se ukázal být NP-úplný byl booleovský problém uspokojivosti, známý také jako SAT. Jak bylo uvedeno výše, jedná se o Cook – Levinovu větu; jeho důkaz, že uspokojivost je NP-complete obsahuje technické podrobnosti o Turingových strojích, které se vztahují k definici NP. Poté, co se tento problém ukázal NP-kompletní, důkaz redukcí poskytl jednodušší způsob, jak ukázat, že existuje i mnoho dalších problémů NP-kompletní, včetně hry Sudoku popsané dříve. V tomto případě důkaz ukazuje, že k dokončení lze použít i řešení sudoku v polynomiálním čase Latinské čtverce v polynomiálním čase.[13] To zase dává řešení problému rozdělení na oddíly trojdílné grafy do trojúhelníků,[14] který by pak mohl být použit k nalezení řešení pro speciální případ SAT známý jako 3-SAT,[15] který pak poskytuje řešení pro obecnou booleovskou uspokojivost. Polynomiální časové řešení Sudoku tedy vede řadou mechanických transformací k polynomiálnímu časovému řešení uspokojivosti, které lze zase použít k řešení jakéhokoli jiného NP-problém v polynomiálním čase. Použitím takových transformací je obrovská třída zdánlivě nesouvisejících problémů navzájem redukovatelná a jsou v jistém smyslu „stejný problém“.

Těžší problémy

Viz také: Třída složitosti

Ačkoli není známo, zda P = NP, problémy mimo P jsou známy. Stejně jako třída P je definována z hlediska doby běhu polynomu, třídy EXPTIME je soubor všech rozhodovacích problémů, které mají exponenciální provozní doba. Jinými slovy, jakýkoli problém v EXPTIME je řešitelný a deterministický Turingův stroj v Ó (2p(n)) čas, kde p(n) je polynomiální funkcí n. Rozhodovací problém je EXPTIME-kompletní pokud je v EXPTIMEa každý problém v EXPTIME má polynomial-time many-one reduction k tomu. Je známo mnoho problémů EXPTIME-kompletní. Protože to lze ukázat P ≠ EXPTIME, tyto problémy jsou venku P, a proto vyžadují více než polynomiální čas. Ve skutečnosti tím věta o časové hierarchii, nelze je vyřešit za podstatně méně než exponenciální čas. Mezi příklady patří nalezení perfektní strategie pro šachy pozice na N × N prkno[16] a podobné problémy pro jiné deskové hry.[17]

Problém rozhodování o pravdivosti prohlášení v Presburgerova aritmetika vyžaduje ještě více času. Fischer a Rabine prokázáno v roce 1974[18] že každý algoritmus, který rozhoduje o pravdivosti Presburgerových výroků o délce n má runtime minimálně pro nějakou konstantu C. Je tedy známo, že problém potřebuje více než exponenciální dobu běhu. Ještě obtížnější jsou nerozhodnutelné problémy, tak jako zastavení problému. Nelze je zcela vyřešit žádným algoritmem v tom smyslu, že pro jakýkoli konkrétní algoritmus existuje alespoň jeden vstup, pro který tento algoritmus nepřinese správnou odpověď; buď vyprodukuje špatnou odpověď, dokončí bez přesvědčivé odpovědi, nebo jinak poběží navždy, aniž by vůbec něco odpovědělo.

Je možné zvážit i jiné otázky než rozhodovací problémy. Jedna taková třída, skládající se z počítání problémů, se nazývá #P: vzhledem k tomu, že NP problém se ptá „Existují nějaká řešení?“, odpovídající #P problém se ptá „Kolik řešení existuje?“ Je zřejmé, že #P problém musí být alespoň tak tvrdý jako odpovídající NP problém, protože počet řešení okamžitě řekne, zda existuje alespoň jedno řešení, pokud je počet větší než nula. Překvapivě někteří #P problémy, které jsou považovány za obtížné, odpovídají snadným (například lineární čas) P problémy.[19] U těchto problémů je velmi snadné zjistit, zda řešení existují, ale zdá se, že je velmi těžké zjistit, kolik z nich. Mnoho z těchto problémů je #P-kompletní, a tedy mezi nejtěžší problémy v #P, protože polynomiální časové řešení kteréhokoli z nich by umožnilo polynomiální časové řešení všem ostatním #P problémy.

Není známo, že by problémy v NP byly v P nebo NP-úplné

Hlavní článek: NP-středně pokročilí

V roce 1975 Richard E. Ladner ukázal, že pokud P ≠ NP pak existují problémy v NP které nejsou ani v P ani NP-kompletní.[1] Takovým problémům se říká NP- přechodné problémy. The problém grafového izomorfismu, problém diskrétního logaritmu a problém celočíselné faktorizace jsou příklady problémů, o nichž se věří, že jsou NP-středně pokročilí. Jsou jedni z mála NP problémy, o kterých není známo, že jsou v P nebo být NP-kompletní.

Problém isomorfismu grafu je výpočetním problémem při určování, zda jsou dva konečné grafy jsou izomorfní. Důležitým nevyřešeným problémem v teorii složitosti je, zda je problém isomorfismu grafu P, NP-kompletní nebo NP-středně pokročilí. Odpověď není známa, ale předpokládá se, že problém alespoň není NP-kompletní.[20] Pokud je izomorfismus grafu NP-dokončit polynomiální časová hierarchie se zhroutí na druhou úroveň.[21] Jelikož se obecně věří, že se polynomiální hierarchie nespadne na žádnou konečnou úroveň, předpokládá se, že izomorfismus grafů není NP-kompletní. Nejlepší algoritmus pro tento problém, kvůli László Babai a Eugene Luks, má dobu běhu 2Ó(√n log n) pro grafy s n vrcholy.

The problém celočíselné faktorizace je výpočetní problém stanovení Prvočíselný rozklad daného celého čísla. Frázi jako rozhodovací problém představuje problém rozhodování, zda má vstup faktor menší než k. Žádný efektivní celočíselný faktorizační algoritmus není znám a tato skutečnost tvoří základ několika moderních kryptografických systémů, jako je RSA algoritmus. Problém celočíselné faktorizace je v NP a v co-NP (a dokonce i v NAHORU a co-UP[22]). Pokud je problém NP-kompletní, hierarchie polynomiálního času se zhroutí na svou první úroveň (tj. NP = co-NP). Nejznámějším algoritmem pro celočíselnou faktorizaci je síto obecného čísla, což trvá očekávaný čas

započítat an n-bit celé číslo. Nejznámější kvantový algoritmus pro tento problém, Shorův algoritmus, běží v polynomiálním čase, i když to neindikuje, v čem spočívá problém s ohledem natřídy kvantové složitosti.

Znamená P „snadné“?

Graf zobrazuje čas (průměrně 100 instancí v ms při použití Pentium III o frekvenci 933 MHz) vs. velikost problému u problémů s batohem pro nejmodernější specializovaný algoritmus. Kvadratické přizpůsobení naznačuje, že empirická algoritmická složitost pro instance s 50–10 000 proměnnými je O ((log (n))2).[23]

Všechna výše uvedená diskuse to předpokládala P znamená „snadné“ a „ne v P„znamená„ tvrdý “, předpoklad známý jako Cobhamova teze. Je to běžný a přiměřeně přesný předpoklad v teorii složitosti; má však určité výhrady.

Zaprvé, v praxi to vždy neplatí. Teoretický polynomiální algoritmus může mít extrémně velké konstantní faktory nebo exponenty, což jej činí nepraktickým. Například problém rozhodování zda graf G obsahuje H jako Méně důležitý, kde H je opraven, lze vyřešit za běhu Ó(n2),[24] kde n je počet vrcholů v G. Nicméně velká O notace skrývá konstantu, na které superexponenciálně závisí H. Konstanta je větší než (použitím Knuthova nota se šipkou nahoru ), a kde h je počet vrcholů v H.[25]

Na druhou stranu, i když se problém ukáže NP-kompletní, i když P ≠ NP, stále mohou existovat účinné přístupy k řešení problému v praxi. Pro mnoho existují algoritmy NP-kompletní problémy, jako je batoh problém, problém obchodního cestujícího a Booleovský problém uspokojivosti, které mohou v rozumném čase vyřešit optimálnost mnoha instancí v reálném světě. Empirický průměrná složitost (čas vs. velikost problému) takových algoritmů může být překvapivě nízká. Příkladem je simplexní algoritmus v lineární programování, který v praxi funguje překvapivě dobře; navzdory exponenciálnímu nejhoršímu případu časová složitost běží na stejné úrovni jako nejznámější algoritmy polynomiálního času.[26]

Konečně existují typy výpočtů, které neodpovídají modelu Turingova stroje, na kterém P a NP jsou definovány, jako např kvantový výpočet a randomizované algoritmy.

Důvody věřit P ≠ NP nebo P = NP

Podle průzkumů veřejného mínění[9][27] většina počítačových vědců tomu věří P ≠ NP. Klíčovým důvodem této víry je, že po desetiletích studia těchto problémů nebyl nikdo schopen najít algoritmus polynomiálního času pro žádný z více než 3000 důležitých známých NP-kompletní problémy (viz Seznam NP-kompletní problémy ). Tyto algoritmy byly hledány dlouho před konceptem NP-úplnost byla dokonce definována (Karp je 21 NP-kompletní problémy, mezi prvními nalezenými, byly všechny dobře známé existující problémy v době, kdy se ukázalo, že jsou NP-kompletní). Dále výsledek P = NP by znamenalo mnoho dalších překvapivých výsledků, které jsou v současné době považovány za nepravdivé, jako např NP = co-NP a P = PH.

Intuitivně se také tvrdí, že existence problémů, které se těžko řeší, ale pro něž je snadné ověřit řešení, odpovídá realitě.[28]

Li P = NP, pak by svět byl úplně jiným místem, než si obvykle myslíme. „Kreativní skoky“ by neměly žádnou zvláštní hodnotu, neexistovala by zásadní mezera mezi řešením problému a rozpoznáním řešení, jakmile bude nalezeno.

— Scott Aaronson, UT Austin

Na druhou stranu se někteří vědci domnívají, že ve víru existuje přílišná důvěra P ≠ NP a že vědci by měli prozkoumat důkazy o P = NP také. Například v roce 2002 byla učiněna tato prohlášení:[9]

Hlavní argument ve prospěch P ≠ NP je naprostý nedostatek zásadního pokroku v oblasti vyčerpávajícího hledání. Toto je podle mého názoru velmi slabý argument. Prostor algoritmů je velmi velký a my jsme teprve na začátku jeho zkoumání. [...] Rozlišení Fermatova poslední věta také ukazuje, že velmi jednoduché otázky mohou být vyřešeny pouze velmi hlubokými teoriemi.

— Moshe Y. Vardi, Rice University

Být připoután ke spekulacím není dobrý průvodce plánováním výzkumu. Jeden by měl vždy vyzkoušet oba směry každého problému. Předsudek způsobil, že slavní matematici nedokázali vyřešit slavné problémy, jejichž řešení bylo v protikladu k jejich očekáváním, přestože vyvinuli všechny požadované metody.

— Anil Nerode, Cornell University

Důsledky řešení

Jedním z důvodů, proč problém přitahuje tolik pozornosti, jsou důsledky odpovědi. Oba směry řešení by enormně posílily teorii a mohly by mít také obrovské praktické důsledky.

P = NP

Důkaz toho P = NP může mít ohromující praktické důsledky, pokud důkaz povede k účinným metodám řešení některých důležitých problémů v systému Windows NP. Je také možné, že důkaz by nevedl přímo k účinným metodám, možná pokud důkaz je nekonstruktivní, nebo je velikost ohraničujícího polynomu příliš velká, aby byla v praxi efektivní. Důsledky, pozitivní i negativní, vznikají, protože jsou různé NP- úplné problémy jsou zásadní v mnoha oblastech.

Například kryptografie spoléhá na to, že některé problémy jsou obtížné. Konstruktivní a efektivní řešení[Poznámka 2] do NP-kompletní problém jako např 3-SAT rozbije většinu stávajících kryptosystémů včetně:

  • Stávající implementace kryptografie veřejného klíče,[29] základ mnoha moderních bezpečnostních aplikací, jako jsou bezpečné finanční transakce přes internet.
  • Symetrické šifry jako AES nebo 3DES,[30] slouží k šifrování komunikačních dat.
  • Kryptografický hash, který je základem blockchain kryptoměny jako Bitcoin, a slouží k ověřování aktualizací softwaru. U těchto aplikací musí být problém s nalezením předobrazu, který má hash na danou hodnotu, obtížný, aby byl užitečný, a v ideálním případě by měl vyžadovat exponenciální čas. Pokud však P = NP, poté vyhledejte předobraz M lze provést v polynomiálním čase, prostřednictvím redukce na SAT.[31]

Ty by musely být upraveny nebo nahrazeny informace - teoreticky bezpečné řešení, která nejsou ze své podstaty založena P-NP nerovnost.

Na druhou stranu existují obrovské pozitivní důsledky, které by vyplynuly z toho, že se dá zvládnout mnoho v současnosti matematicky neřešitelných problémů. Například mnoho problémů v operační výzkum jsou NP-kompletní, například některé typy celočíselné programování a problém obchodního cestujícího. Efektivní řešení těchto problémů by mělo obrovské důsledky pro logistiku. Mnoho dalších důležitých problémů, například některé problémy v systému Windows predikce proteinové struktury, jsou také NP-kompletní;[32] pokud by tyto problémy byly efektivně řešitelné, mohlo by to podnítit značný pokrok v biologických vědách a biotechnologiích.

Ale tyto změny mohou významně blednout ve srovnání s revolucí, účinnou metodou řešení NP- úplné problémy by způsobily v samotné matematice. Gödel ve svých raných úvahách o výpočetní složitosti poznamenal, že mechanická metoda, která by mohla vyřešit jakýkoli problém, by znamenala revoluci v matematice:[33][34]

Pokud by skutečně existoval stroj s φ (n) ∼ k ⋅ n (nebo dokonce ∼ k ⋅ n2), mělo by to důsledky největší důležitosti. Jmenovitě by to zjevně znamenalo, že navzdory nerozhodnutelnosti Entscheidungsproblem, mentální práce matematika týkající se otázek ano-ne-ne, by mohla být zcela nahrazena strojem. Koneckonců, člověk by prostě musel zvolit přirozené číslo n tak velké, že když stroj nepřináší výsledek, nemá smysl o problému více přemýšlet.

Podobně, Stephen Cook říká[35]

... transformovalo by to matematiku tím, že by umožnilo počítači najít formální důkaz jakékoli věty, která má důkaz přiměřené délky, protože formální důkazy lze snadno rozpoznat v polynomiálním čase. Ukázkové problémy mohou dobře zahrnovat všechny Problémy s cenou CMI.

Výzkumní matematici tráví svou kariéru snahou dokázat věty a některým důkazům trvalo desetiletí či dokonce staletí, než se objevily problémy - například Fermatova poslední věta trvalo více než tři století, než se dokázalo. Metoda, která je zaručena k nalezení důkazů k větám, pokud by existovala „přiměřená“ velikost, by tento boj v podstatě ukončila.

Donald Knuth uvedl, že tomu věřil P = NP, ale vyhrazuje si dopad možného důkazu:[36]

[...] Nevěřím, že rovnost P = NP se ukáže jako užitečný, i když se prokáže, protože takový důkaz bude téměř jistě nekonstruktivní.

P ≠ NP

Důkaz, který to ukázal P ≠ NP by postrádal praktické výpočetní výhody důkazu, že P = NP, ale přesto by představoval velmi významný pokrok v teorii výpočetní složitosti a poskytl vodítko pro budoucí výzkum. Umožnilo by to formálně ukázat, že mnoho běžných problémů nelze efektivně vyřešit, takže pozornost vědců může být zaměřena na dílčí řešení nebo řešení jiných problémů. Kvůli rozšířené víře v P ≠ NP, velká část tohoto zaměření výzkumu již proběhla.[37]

Taky P ≠ NP stále ponechává otevřené průměrná složitost těžkých problémů v NP. Například je možné, že SAT vyžaduje v nejhorším případě exponenciální čas, ale že téměř všechny jeho náhodně vybrané instance jsou efektivně řešitelné. Russell Impagliazzo popsal pět hypotetických „světů“, které by mohly vyplývat z různých možných řešení otázky průměrné složitosti.[38] Ty se pohybují od „Algorithmica“, kde P = NP a problémy jako SAT lze efektivně vyřešit ve všech případech, do „Kryptomanie“, kde P ≠ NP a generování tvrdých případů problémů venku P je snadné a tři mezilehlé možnosti odrážejí různá možná rozdělení obtížnosti v různých případech NP-tvrdé problémy. „Svět“, kde P ≠ NP ale všechny problémy v NP v průměrném případě se v článku nazývají „Heuristica“. A Univerzita Princeton Workshop v roce 2009 studoval stav pěti světů.[39]

Výsledky týkající se obtížnosti důkazu

Ačkoliv P = NP problém sám o sobě zůstává otevřený navzdory ceně v hodnotě milionů dolarů a velkému množství specializovaného výzkumu, vedlo úsilí k vyřešení problému k několika novým technikám. Zejména některé z nejplodnějších výzkumů týkajících se EU P = NP problémem bylo ukázat, že stávající techniky dokazování nejsou dostatečně silné, aby odpověděly na otázku, což naznačuje, že jsou vyžadovány nové technické přístupy.

Jako další důkaz obtížnosti problému, v podstatě všechny známé důkazní techniky v teorie výpočetní složitosti spadají do jedné z následujících klasifikací, z nichž každá je známa jako nedostatečná k prokázání toho P ≠ NP:

KlasifikaceDefinice
Relativizace důkazůPředstavte si svět, kde každý algoritmus smí provádět dotazy na nějaký pevný podprogram nazývaný an věštec (černá skříňka, která dokáže odpovídat na pevnou sadu otázek v konstantním čase, například černá skříňka, která řeší jakýkoli problém s cestujícím prodavačem v 1 kroku) a doba běhu věštce se nezapočítává do doby běhu algoritmu . Většina důkazů (zejména těch klasických) platí ve světě s věštci jednotně bez ohledu na to, co věštec dělá. Tyto důkazy se nazývají relativizující. V roce 1975 Baker, Gill a Solovay to ukázal P = NP s ohledem na některé věštce, zatímco P ≠ NP pro ostatní věštce.[40] Protože relativizující důkazy mohou prokázat pouze tvrzení, která jsou jednotně pravdivá s ohledem na všechny možné věštce, ukázalo se, že relativizační techniky nemohou vyřešit P = NP.
Přírodní důkazyV roce 1993 Alexander Razborov a Steven Rudich definoval obecnou třídu důkazních technik pro dolní hranice složitosti obvodu, tzv přírodní důkazy.[41] V té době byly všechny dříve známé dolní hranice obvodu přirozené a složitost okruhu byla považována za velmi slibný přístup k řešení P = NP. Razborov a Rudich to však ukázali, pokud jednosměrné funkce neexistuje žádná metoda přirozeného důkazu P a NP. Ačkoli jednosměrné funkce nikdy nebyly formálně prokázány, většina matematiků věří, že ano, a důkaz jejich existence by byl mnohem silnějším výrokem než P ≠ NP. Je tedy nepravděpodobné, že by to mohly vyřešit pouze přírodní důkazy P = NP.
Algebrizující důkazyPo výsledku Baker-Gill-Solovay byly k prokázání toho úspěšně použity nové nerelativizující důkazní techniky IP = PSPACE. V roce 2008 však Scott Aaronson a Avi Wigderson ukázal, že hlavní technický nástroj používaný v EU IP = PSPACE důkaz, známý jako aritmetizace, bylo také nedostatečné k vyřešení P = NP.[42]

Tyto překážky jsou dalším důvodem proč NP-kompletní problémy jsou užitečné: pokud lze u algoritmu demonstrovat algoritmus polynomiálního času NP-úplný problém, to by vyřešilo P = NP problém způsobem, který není vyloučen výše uvedenými výsledky.

Tyto bariéry také vedly některé počítačové vědce k domněnce, že P proti NP problém může být nezávislý standardních systémů axiomu jako ZFC (nelze v nich prokázat ani vyvrátit). Interpretace výsledku nezávislosti by mohla spočívat v tom, že pro žádný neexistuje žádný algoritmus polynomiálního času NP-úplný problém, a takový důkaz nelze zkonstruovat v (např.) ZFC, nebo že algoritmy polynomiálního času pro NP-mohou existovat úplné problémy, ale v ZFC není možné dokázat, že takové algoritmy jsou správné.[43] Pokud je však možné pomocí technik takového druhu, o nichž je v současnosti známo, že jsou použitelné, prokázat, že o problému nelze rozhodnout ani při mnohem slabších předpokladech rozšiřujících Peanoovy axiomy (PA) pro celočíselnou aritmetiku, pak by pro každý problém nutně existovaly algoritmy téměř v polynomiálním čase NP.[44] Pokud tedy někdo věří (jak to dokládají teoretici složitosti), že ne všechny problémy v něm NP mít efektivní algoritmy, z toho by vyplývalo, že důkazy o nezávislosti pomocí těchto technik nemohou být možné. Tento výsledek navíc naznačuje, že prokázání nezávislosti na PA nebo ZFC pomocí aktuálně známých technik není o nic snazší než prokázání existence účinných algoritmů pro všechny problémy v NP.

Požadovaná řešení

Zatímco P proti NP problém je obecně považován za nevyřešený,[45] mnoho amatérských a někteří profesionální vědci požadovali řešení. Gerhard J. Woeginger udržuje seznam, který od roku 2018 obsahuje 62 údajných důkazů o P = NP, 50 důkazů o P ≠ NP, 2 důkazy, že problém je neprokazatelný, a jeden důkaz, že je nerozhodnutelný.[46] Některé pokusy o vyřešení P proti NP dostali krátkou pozornost médií,[47] ačkoli tyto pokusy byly od té doby vyvráceny.

Logické charakterizace

The P = NP problém lze zopakovat, pokud jde o vyjádřitelné určité třídy logických příkazů, jako výsledek práce v popisná složitost.

Zvažte všechny jazyky konečných struktur s pevným podpis včetně a lineární pořadí vztah. Pak všechny tyto jazyky v P lze vyjádřit v logika prvního řádu s přidáním vhodného minima kombinátor pevných bodů. Efektivně to v kombinaci s objednávkou umožňuje definovat rekurzivní funkce. Pokud podpis obsahuje kromě vztahu rozlišeného pořadí alespoň jeden predikát nebo funkci, takže velikost prostoru potřebného k uložení takových konečných struktur je ve skutečnosti polynomická v počtu prvků ve struktuře, přesně to charakterizuje P.

Podobně, NP je sada jazyků vyjádřitelných v existenciálním jazyce logika druhého řádu —Takže je logika druhého řádu omezena na vyloučení univerzální kvantifikace nad vztahy, funkcemi a podmnožinami. Jazyky v polynomiální hierarchie, PH, odpovídají celé logice druhého řádu. Otázka tedy zní P správná podmnožina NP„lze přeformulovat jako“ je existenciální logika druhého řádu schopná popsat jazyky (konečných lineárně uspořádaných struktur s netriviální signaturou), které logika prvního řádu s nejméně pevným bodem nemůže? “.[48] Slovo „existenciální“ lze dokonce vynechat z předchozí charakterizace P = NP kdyby a jen kdyby P = PH (protože první by to stanovil NP = co-NPz čehož vyplývá, že NP = PH).

Algoritmy polynomiálního času

Žádný algoritmus pro nikoho NP-kompletní problém je známo, že běží v polynomiálním čase. Existují však známé algoritmy NP-kompletní problémy s vlastností, že pokud P = NP, pak algoritmus běží v polynomiálním čase při přijímání instancí (i když s enormními konstantami, což činí algoritmus nepraktickým). Tyto algoritmy se však nekvalifikují jako polynomiální čas, protože jejich doba běhu u odmítajících instancí není polynomiální. Následující algoritmus, kvůli Levin (bez jakékoli citace), je takový příklad níže. Správně přijímá NP-kompletní jazyk SOUHRNNÁ SOUHRN. Spouští se v polynomiálním čase na vstupech, které jsou v SUBSET-SUM právě tehdy P = NP:

// Algoritmus, který přijímá NP-kompletní jazyk SUBSET-SUM.//// toto je algoritmus polynomiálního času právě tehdy P = NP.//// „Polynomial-time“ znamená, že vrací „yes“ v polynomiálním čase, když// odpověď by měla být „ano“ a běží navždy, když je „ne“.//// Vstup: S = konečná množina celých čísel// Výstup: „ano“, pokud některá podmnožina S přidá až 0.// Spouští se navždy bez jakéhokoli výstupu.// Poznámka: „Číslo programu M“ je program získaný pomocí// zápis celého čísla M v binárním formátu// vzhledem k tomu, že řetězec bitů je a// program. Může být každý možný program// generováno tímto způsobem, ačkoli většina nedělá nic// z důvodu syntaktických chyb.FOR K = 1 ... ∞ FOR M = 1 ... K Spusťte číslo programu M pro kroky K se vstupem S IF program vydá seznam odlišných celých čísel AND celá čísla jsou v S AND celá čísla součet na 0 POTOM VÝSTUP „ano“ a HALT

Kdyby a jen kdyby P = NP, pak se jedná o algoritmus polynomiálního času přijímající NP-kompletní jazyk. „Přijímat“ znamená, že poskytuje odpovědi „ano“ v polynomiálním čase, ale může běžet navždy, když je odpověď „ne“ (také známá jako semi-algoritmus).

Tento algoritmus je nesmírně nepraktický, i když P = NP. Pokud je nejkratší program, který dokáže vyřešit SUBSET-SUM v polynomiálním čase b bitů dlouhý, výše uvedený algoritmus se pokusí alespoň 2b − 1 ostatní programy jako první.

Formální definice

P a NP

Koncepčně vzato, a rozhodovací problém je problém, který bere jako vstup některé tětiva w přes abecedu Σ a výstupy „ano“ nebo „ne“. Pokud existuje algoritmus (řekni a Turingův stroj nebo počítačový program s neomezenou pamětí), které mohou poskytnout správnou odpověď na jakýkoli vstupní řetězec délky n maximálně cnk kroky, kde k a C jsou konstanty nezávislé na vstupním řetězci, pak říkáme, že problém lze vyřešit v polynomiální čas a umístíme to do třídy P. Formálně, P je definována jako množina všech jazyků, o kterých může rozhodovat deterministický polynomiálně-Turingův stroj. To znamená

kde

a deterministický Turingův stroj v polynomiálním čase je deterministický Turingův stroj M který splňuje následující dvě podmínky:

  1. M zastaví se na všech vstupech w a
  2. tady existuje takhle , kde Ó Odkazuje na velká O notace a

NP lze definovat podobně pomocí nedeterministických Turingových strojů (tradiční způsob). Je však moderní přístup k definování NP je použít koncept osvědčení a ověřovatel. Formálně, NP je definována jako sada jazyků přes konečnou abecedu, která má ověřovatel, který běží v polynomiálním čase, kde je pojem „ověřovatel“ definován následovně.

Nechat L být jazykem přesnou abecedu, Σ.

L ∈ NP if, and only if, there is a binary relationship a kladné celé číslo k tak, aby byly splněny následující dvě podmínky:

  1. Pro všechny , takový, že (X, y) ∈ R a ; a
  2. jazyk přes je rozhodnutelný deterministickým Turingovým strojem v polynomiálním čase.

Turingův stroj, který rozhoduje LR se nazývá a ověřovatel pro L a a y takový, že (X, y) ∈ R se nazývá a osvědčení o členství z X v L.

Obecně nemusí mít ověřovatel polynomiální čas. Nicméně pro L být v NP, musí existovat ověřovatel, který běží v polynomiálním čase.

Příklad

Nechat

Clearly, the question of whether a given X je kompozitní is equivalent to the question of whether X is a member of COMPOSITE. It can be shown that COMPOSITE ∈ NP by verifying that it satisfies the above definition (if we identify natural numbers with their binary representations).

COMPOSITE also happens to be in P, a fact demonstrated by the invention of the Test prvosti AKS.[49]

NP-completeness

Hlavní článek: NP-completeness

There are many equivalent ways of describing NP-completeness.

Nechat L be a language over a finite alphabet Σ.

L je NP-complete if, and only if, the following two conditions are satisfied:

  1. L ∈ NP; a
  2. žádný L ' v NP is polynomial-time-reducible to L (written as ), kde if, and only if, the following two conditions are satisfied:
    1. Tady existuje F : Σ* → Σ* such that for all w in Σ* we have: ; a
    2. there exists a polynomial-time Turing machine that halts with F(w) on its tape on any input w.

Alternatively, if L ∈ NP, and there is another NP-complete problem that can be polynomial-time reduced to L, pak L je NP-complete. This is a common way of proving some new problem is NP-complete.

Populární kultura

Film Travelling Salesman, by director Timothy Lanzone, is the story of four mathematicians hired by the US government to solve the P proti NP problém.[50]

In the sixth episode of Simpsonovi' seventh season "Treehouse of Horror VI ", the equation P=NP is seen shortly after Homer accidentally stumbles into the "third dimension".[51][52]

In the second episode of season 2 of Základní, "Solve for X" revolves around Sherlock and Watson investigating the murders of mathematicians who were attempting to solve P proti NP.[53][54]

Viz také

Poznámky

  1. ^ A nedeterministický Turingův stroj can move to a state that is not determined by the previous state. Such a machine could solve an NP problem in polynomial time by falling into the correct answer state (by luck), then conventionally verifying it. Such machines are not practical for solving realistic problems but can be used as theoretical models.
  2. ^ Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of with a reasonable constant term would be disastrous. On the other hand, a solution that is in almost all cases would not pose an immediate practical danger.

Reference

  1. ^ A b R. E. Ladner "On the structure of polynomial time reducibility," Deník ACM 22, pp. 151–171, 1975. Corollary 1.1. ACM site.
  2. ^ Fortnow, Lance (2013). The Golden Ticket: P, NP, and the Search for the Impossible. Princeton, NJ: Princeton University Press. ISBN  9780691156491.
  3. ^ Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.
  4. ^ L. A. Levin (1973). "Универсальные задачи перебора" (v Rusku). 9 (3) (Problems of Information Transmission ed.): 115–116. Citovat deník vyžaduje | deník = (Pomoc)
  5. ^ Fortnow, Lance (2009). "The status of the P proti NP problem" (PDF). Komunikace ACM. 52 (9): 78–86. CiteSeerX  10.1.1.156.767. doi:10.1145/1562164.1562186. Archivovány od originál (PDF) dne 24. února 2011. Citováno 26. ledna 2010.
  6. ^ NSA (2012). "Letters from John Nash" (PDF).
  7. ^ Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
  8. ^ Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
  9. ^ A b C William I. Gasarch (June 2002). „The P=?NP poll" (PDF). Novinky SIGACT. 33 (2): 34–47. CiteSeerX  10.1.1.172.1005. doi:10.1145/564585.564599.
  10. ^ William I. Gasarch. "The Second P=?NP poll" (PDF). Novinky SIGACT. 74.
  11. ^ A b "Guest Column: The Third P =? NP Poll1" (PDF). Citováno 25. května 2020.
  12. ^ Scott Aaronson. "PHYS771 Lecture 6: P, NP, and Friends". Citováno 27. srpna 2007.
  13. ^ "MSc course: Foundations of Computer Science". www.cs.ox.ac.uk. Citováno 25. května 2020.
  14. ^ Colbourn, Charles J. (1984). "The complexity of completing partial Latin squares". Diskrétní aplikovaná matematika. 8 (1): 25–30. doi:10.1016/0166-218X(84)90075-1.
  15. ^ I. Holyer (1981). „The NP-completeness of some edge-partition problems". SIAM J. Comput. 10 (4): 713–717. doi:10.1137/0210054.
  16. ^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n × n chess requires time exponential in n". Journal of Combinatorial Theory, Series A. 31 (2): 199–214. doi:10.1016/0097-3165(81)90016-9.
  17. ^ David Eppstein. "Computational Complexity of Games and Puzzles".
  18. ^ Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41. Archivovány od originál on 15 September 2006. Citováno 15. října 2017.
  19. ^ Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems". SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.
  20. ^ Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP". Informace a výpočet. 204 (5): 835–852. doi:10.1016/j.ic.2006.02.002.
  21. ^ Schöning, Uwe (1988). "Graph isomorphism is in the low hierarchy". Journal of Computer and System Sciences. 37 (3): 312–323. doi:10.1016/0022-0000(88)90010-4.
  22. ^ Lance Fortnow. Computational Complexity Blog: Complexity Class of the Week: Factoring. 13 September 2002.
  23. ^ Pisinger, D. 2003. "Where are the hard knapsack problems?" Technical Report 2003/08, Department of Computer Science, University of Copenhagen, Copenhagen, Denmark
  24. ^ Kawarabayashi, K. I.; Kobayashi, Y .; Reed, B. (2012). "The disjoint paths problem in quadratic time". Journal of Combinatorial Theory, Series B. 102 (2): 424–435. doi:10.1016/j.jctb.2011.07.004.
  25. ^ Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303. CiteSeerX  10.1.1.114.3864. doi:10.1016/0196-6774(87)90043-5.
  26. ^ Gondzio, Jacek; Terlaky, Tamás (1996). "3 A computational view of interior point methods". In J. E. Beasley (ed.). Advances in linear and integer programming. Oxford Lecture Series in Mathematics and its Applications. 4. New York: Oxford University Press. pp. 103–144. PAN  1438311. Postscript file at website of Gondzio a at McMaster University website of Terlaky.
  27. ^ Rosenberger, Jack (May 2012). "P vs. NP poll results". Komunikace ACM. 55 (5): 10.
  28. ^ Scott Aaronson. "Reasons to believe"., point 9.
  29. ^ Vidět Horie, S.; Watanabe, O. (1997). "Hard instance generation for SAT". Algorithms and Computation. Přednášky z informatiky. 1350. Springer. pp. 22–31. arXiv:cs/9809117. Bibcode:1998cs........9117H. doi:10.1007/3-540-63890-3_4. ISBN  978-3-540-63890-2. for a reduction of factoring to SAT. A 512 bit factoring problem (8400 MIPS-years when factored) translates to a SAT problem of 63,652 variables and 406,860 clauses.
  30. ^ Viz například Massacci, F. & Marraro, L. (2000). "Logical cryptanalysis as a SAT problem". Journal of Automated Reasoning. 24 (1): 165–203. CiteSeerX  10.1.1.104.962. doi:10.1023/A:1006326723002. in which an instance of DES is encoded as a SAT problem with 10336 variables and 61935 clauses. A 3DES problem instance would be about 3 times this size.
  31. ^ De, Debapratim; Kumarasubramanian, Abishek; Venkatesan, Ramarathnam (2007). "Inversion attacks on secure hash functions using SAT solvers". Springer. 377–382. doi:10.1007/978-3-540-72788-0_36.
  32. ^ Berger B, Leighton T (1998). "Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete". J. Comput. Biol. 5 (1): 27–40. CiteSeerX  10.1.1.139.5547. doi:10.1089/cmb.1998.5.27. PMID  9541869.
  33. ^ History of this letter and its translation from Michael Sipser. "The History and Status of the P proti NP question" (PDF).
  34. ^ David S. Johnson. "A Brief History of NP-Completeness, 1954–2012" (PDF). From pages 359–376 of Optimization Stories, M. Grötschel (editor), a special issue of ¨ Documenta Mathematica, published in August 2012 and distributed to attendees at the 21st International Symposium on Mathematical Programming in Berlin.
  35. ^ Cook, Stephen (Duben 2000). „The P proti NP Problem" (PDF). Clay Mathematics Institute. Citováno 18. října 2006. Citovat deník vyžaduje | deník = (Pomoc)
  36. ^ Knuth, Donald E. (20 May 2014). Twenty Questions for Donald Knuth. informit.com. InformIT. Citováno 20. července 2014.
  37. ^ L. R. Foulds (October 1983). "The Heuristic Problem-Solving Approach". Journal of the Operational Research Society. 34 (10): 927–934. doi:10.2307/2580891. JSTOR  2580891.
  38. ^ R. Impagliazzo, "A personal view of average-case complexity," sct, pp.134, 10th Annual Structure in Complexity Theory Conference (SCT'95), 1995
  39. ^ "Tentative program for the workshop on "Complexity and Cryptography: Status of Impagliazzo's Worlds"". Archivovány od originál on 15 November 2013.
  40. ^ T. P. Baker; J. Gill; R. Solovay. (1975). "Relativizations of the P =? NP Question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.
  41. ^ Razborov, Alexander A.; Steven Rudich (1997). "Natural proofs". Journal of Computer and System Sciences. 55 (1): 24–35. doi:10.1006/jcss.1997.1494.
  42. ^ S. Aaronson & A. Wigderson (2008). Algebrization: A New Barrier in Complexity Theory (PDF). Proceedings of ACM STOC'2008. pp. 731–740. doi:10.1145/1374376.1374481.
  43. ^ Aaronson, Scott. "Is P Proti NP Formally Independent?" (PDF)..
  44. ^ Ben-David, Shai; Halevi, Shai (1992). "On the independence of P proti NP". Technical Report. 714. Technion. Citovat deník vyžaduje | deník = (Pomoc).
  45. ^ John Markoff (8 October 2009). "Prizes Aside, the P-NP Puzzler Has Consequences". The New York Times.
  46. ^ Gerhard J. Woeginger. „The P-versus-NP page". Citováno 24. června 2018.
  47. ^ Markoff, John (16 August 2010). "Step 1: Post Elusive Proof. Step 2: Watch Fireworks". The New York Times. Citováno 20. září 2010.
  48. ^ Elvira Mayordomo. "P versus NP" Archivováno 16 February 2012 at the Wayback Machine Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
  49. ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES is in P" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR  3597229.
  50. ^ Geere, Duncan (26 April 2012). "'Travelling Salesman' movie considers the repercussions if P equals NP". Wired UK. Citováno 26. dubna 2012.
  51. ^ Hardesty, Larry. "Explained: P vs. NP".
  52. ^ Shadia, Ajam. "What is the P vs. NP problem? Why is it important?".
  53. ^ Gasarch, William (7 October 2013). "P vs NP is Elementary? No— P vs NP is ON Elementary". blog.computationalcomplexity.org. Citováno 6. července 2018.
  54. ^ Kirkpatrick, Noel (4 October 2013). "Elementary Solve for X Review: Sines of Murder". TV.com. Citováno 6. července 2018.

Další čtení

externí odkazy