Student World

Jak na řešení problému, zda NP je P?

Keith Devlin řadí otázku NP úplných úloh a jejich vztah k P úlohám mezi jeden ze sedmi největších problémů, které stojí před matematikou nového tisíciletí. Podle něj jde však současně o jediný z těchto problémů, na jehož řešení má šanci dosáhnout i laik…

Sedm nejvýznamnějších matematických úloh podle Devlina jsou:
– Riemanova hypotéza (o rozložení prvočísel)
– Yangova-Millsova teorie a hypotéza hmotnostních rozdílů
– P versus NP
– Navier-Stokesovy rovnice
– hypotézy Poincarého, Birchova/Swinnerton-Dyerova a Hodgeova.

Co se týče problému NP, Devlin je přesvědčen, že se podaří prokázat, že NP je různé od P. Probírat se třeba známými procedurami pro řešení úlohy obchodního cestujícího ovšem podle Devlina nejspíš nikam nepovede. Konec konců nehledáme konkrétní řešící algoritmus fungující v polynomiálním čase (pokud se tedy shodneme na tom, že takový ani neexistuje). Probírání se řadou algoritmů ale těžko může přivést k důkazu, že žádný polynomiální algoritmus nemůže existovat obecně.
Za nejnadějnější pokládá Devlin postup, kdy nejprve budeme konstruovat nějaký nový problém, který ze své podstaty není řešitelný v polynomiálním čase, a poté dokážeme, že je ekvivalentní některému z "velkých" NP úplných problémů. Uznává však, že sám při svých pokusech v tomto směru nijak nepokročil, vlastně ani o píď. Nepřišel totiž na to, jak přímo do podstaty problému zabudovat jeho neřešitelnost v polynomiálně rostoucím čase.
Devlin je ovšem přesvědčen, že problém NP versus P má největší šanci, že jej vyřeší nějaký neznámý amatér. Mj. i proto, že je to jeden z mála současných matematických problémů, kde amatér může vůbec porozumět formulaci úlohy :-). Možná, na rozdíl od ostatních matematických problémů, postačí jeden dobrý nápad…
(To by konec konců stačilo i ve velmi neočekávaném případě, že NP=P; také zde by šlo o nalezení jediného algoritmu.)

Mimochodem, Ian Stewart ve sborníku Příštích padesát let naopak vyslovil názor, že se nakonec ukáže, že vzhledem k neúplnosti aritmetiky je problém P versus NP formálně nerozhodnutelný.
(http://www.scienceworld.cz/sw.nsf/ID/3C7FF60999CC7639C1256F5D003D7E62)
Přiznám se, že tento pohled na věc nechápu. Následuje několik nesouvislých poznámek k tématu:
Formální nerozhodnutelnost by znamenala, že lze klidně přidat axiom i jeho negaci. Takže – pokud bychom přidali axiom, že P rovná se NP, mohli bychom řešit NP úplné problémy v polynomiálním čase (tady totiž jde o něco de facto empirického). Luštitelé by si jistě jeden axiom klidně přidali, pokud by jim to umožnilo najít rychleji řešení. Jediné, co mě napadá, je, že axiom P rovná se NP by ještě nemusel obnášet znalost konkrétního algoritmu, který by příslušnou třídu problémů řešil v polynomiálním čase (nebo by snad dokonce šlo celou Stewartovu koncepci zachraňovat tím, že takový algoritmus ani nalézt nelze?).
(Navíc – jak by mohl být formálně nerozhodnutelný problém tohoto typu, když by příslušné řešení-algoritmus někde ve "stavovém prostoru" muselo existovat? Leda snad, že by nerozhodnutelnost souvisela se samotnou neúplností – např. – teorie čísel. Ale to už je jen opravdu vaření z vody.)

Ještě souvislost NP/P se slavnou faktorizací. U faktorizace se nepodařilo dokázat, že je to NP úplný problém a převládá přesvědčení, že ani není, je "níže". Řešení faktorizace (včetně kvantového algoritmu, ale i eventuálně v budoucnu objevené řešení klasické) proto nemá vztah k řešení dalších NP úplných problémů a k otázce, zda NP je P. Ne tak ale obráceně. Splnitelnost logické formule je na faktorizaci převoditelná, důkazy o ekvivalenci NP a P by proto šifrovacími technologiemi pořádně otřásly. I z tohoto důvodu je otázkou, co by vlastně formální nerozhodnutelnost NP/P znamenala. To bychom si prostě přidali jeden axiom a pak RSA luštili v polynomiálním čase?

A zcela na okraj, jaký bude mít příslušný důkaz o tom, že NP není P vztah ke kvantovým algoritmům? Bude vylučovat také nalezení kvantového algoritmu, který by třeba obchodního cestujícího řešil v polynomiálně rostoucím čase, nebo se takový důkaz bude vztahovat jen na procedury klasické?

autor Pavel Houser