kontrola je jednodušší než nalezení?
nalezení řešení problému by mělo být těžší než kontrola, zda je řešení správné. To se zdá být zřejmé, pokud jste někdy vyřešili Sudoku puzzle, nebo vyřešili Rubikovu kostku, nebo hráli šachovou hru. Ale toto tvrzení, jakkoli intuitivní, nás vede přímo k jedné z nejhlubších matematických otázek, které naše civilizace položila.
Non-deterministický polynomiální čas (nebo NP) problémy jsou ty, kde si můžete snadno ověřit odpověď správná., Naproti tomu polynomiální čas (nebo P) problémy jsou ty
, Kde je snadné najít odpověď. Pokud najdete odpověď, pak jste ji zkontrolovali, aby byla správná, takže každý problém v P je také v NP. Říkáme, že P je podtřída NP. Nevíme však, zda existuje nějaký konkrétní problém v NP, který není v P, a to je to, čemu říkáme problém P vs NP.
problém P vs NP je jedním z nejdůležitějších nevyřešených problémů v matematice a teoretické informatice. Existuje dokonce Cena Clay Millennium, která nabízí jeden milion dolarů za jeho řešení., Nicméně, tam jsou pravděpodobně mnohem jednodušší způsoby, jak se stát milionářem než řešení P vs NP!
nedávno došlo k bzučení, když se někdo domníval, že to vyřeší na arXiv, i když byla rychle nalezena mezera v důkazu. Vzhledem k nedávnému zájmu o problém a jeho centrální místo v matematice, diskutuji o tom v tomto týdnu blogu.
Sudoku
Pokud máte v novinách vyplněnou Sudoku, můžete ji hodit do koše. Ale pokud jste chtěli, můžete prohledat řádky, sloupce a buňky 3 x 3, abyste zjistili, že je to platné řešení: každý z 1, 2,…, 9 musí nastat přesně jednou., To je analogické s NP, protože je relativně snadné zkontrolovat, zda je řešení správné.
Pokud vám však dám částečně vyplněnou hádanku Sudoku, může být těžké najít řešení. To je radost a výzva tohoto druhu puzzle. Takže být v NP se nezdá okamžitě znamenat, že problém má snadné najít řešení. Tato intuice je jádrem problému P vs NP.
přesná formulace
abychom přesněji pochopili P a NP, musíme lépe porozumět algoritmům a měřit jejich rychlost. Problémy jsou kladeny s nějakým pevným vstupem a výstupem buď ano, nebo ne. Vstup je daná délka, řekněme n, kde n je kladné celé číslo. To představuje počet bitů potřebných k vyjádření vstupu. Algoritmus je metoda nebo postup pro řešení problému. Algoritmy poskytují pokyny na každém kroku ve výpočtu a musí ukončit., Kroky mohou být sekundy, milisekundy nebo nějaký jiný pevný časový interval, který závisí na vašem problému.
složitost problému je minimální nejhorší doba běhu ve všech možných algoritmech, které řeší problém jako funkci délky vstupu. Jinými slovy, měří, jak dlouho trvá řešení problému nejrychlejším algoritmem, ale s nejhorším případovým vstupem.
problém je řešitelný v polynomiálním čase, pokud daný vstup délky n, jeho složitost je ohraničená shora pomocí polynomické funkce nm pro nějaké nezáporné celé číslo m., Soubor všech problémů řešitelných v polynomiálním čase je označen p.
být v P nemusí nutně znamenat, že problém je proveditelný. Například, pokud to trvá n1000 kroky ke spuštění algoritmu, pak to bude zoufale pomalé a to i pro malá n. Nedeterministické polynomiální (nebo NP) problémy jsou ty, kde můžete zkontrolovat, pokud ANO, odpověď je správná v polynomiálním čase.
NP-tvrdost
problém je NP-tvrdý, pokud by algoritmus polynomu-času pro něj znamenal algoritmus polynomu-času pro každý problém v NP. Pokud tedy problém s NP byl v P, pak P = NP., Problémy NP-hard jsou přinejmenším stejně těžké jako jakýkoli problém v NP. NP-kompletní problém je ten, který je NP-tvrdý a v NP.
klasický NP-kompletní problém je najít Hamiltonův cyklus. Za tímto účelem předpokládejme, že máme síť měst Spojených silnicemi. Problém je navštívit každé město pomocí silnic (žádná letadla povolena!) a vrátit se na začátek. To se zdá snadné pro malý počet měst, ale pokud jste dostali stovky z nich, pak je to těžké., Tisíce dalších takových NP-kompletní problémy jsou známy vznikající v teorii grafů, teorie čísel, geometrie, a další oblasti matematiky a informatiky.
jaká je odpověď, opravdu?
kdybych měl vsadit, pak bych předpokládal, že P se nerovná NP a myslím, že většina odborníků by souhlasila. Museli bychom být strašně hloupí, abychom neviděli, jak všechny tisíce problémů s NP nemají algoritmus polynomu. Ale jako druh je hloupá naše výchozí pozice, takže nikdo nemůže říci, jaká je odpověď se 100% jistotou.,
zajímavé na problému P vs NP je to, že ukazuje na to, jak omezené je naše porozumění v prokázání, že určité problémy nemají rychlá řešení. To je součástí většího tématu v oblasti teorie výpočetní složitosti, která studuje desítky dalších tříd složitosti. Podívejte se na složitost zoo pro výpis z těchto tříd. Z větší části je otevřené ukázat různé (často exotické znějící) třídy složitosti jsou správné podtřídy navzájem. Například není známo, zda je nl řádnou podtřídou P, a nevíme, zda je FPT řádnou podtřídou W.,
bez ohledu na jeho pravdivost problém P vs NP pravděpodobně zůstane po určitou dobu otevřený. Pokud není prokázáno, že P = NP, Sudoku zůstává v bezpečí.
Anthony Bonato