Jeden zo šiestich problémov, za ktorých vyriešenie ponúka Clayov matematický inštitút odmenu milión dolárov, je takzvaný P verzus NP problém. Ak zanedbáme niektoré podstatné technikality, jeho zadanie je prekvapivo jednoduché: Úlohou je rozhodnúť, či sa problémy, ktorých riešenie vieme jednoducho overiť, dajú aj jednoducho vyriešiť. Problémy, kde vieme riešenie jednoducho overiť, spadajú do triedy nazývanej NP. Problémy, ktoré vieme jednoducho vyriešiť, patria do triedy P. Otázka teda znie: platí P = NP?
Peknú ilustráciu poskytuje hlavolam Sudoku [1]. Predstavme si, že máme pred sebou jeden taký hlavolam. Ak vám niekto vyplní prázdne políčka nejakými číslami, je ľahké overiť, či toto vyplnenie spĺňa podmienky riešenia. Ak však hlavolam riešime sami od začiatku, je pomerne ťažké nájsť riešenie. V skutočnosti nepoznáme jednoduchý postup [2], ktorým vieme Sudoku vyriešiť. To samozrejme neznamená, že taký algoritmus nemôžeme niekedy v budúcnosti objaviť – väčšina zainteresovaných vedcov však predpokladá, že taký algoritmus neexistuje. Sudoku preto patrí do triedy NP (lebo vieme ľahko overiť, či máme v rukách správne riešenie), avšak predpokladá sa, že nepatrí do triedy P (čiže veríme, že neexistuje jednoduchý spôsob vyriešenia).
Čo sa presne myslí pod „jednoduchosťou“? Predstavme si, že riešime Sudoku, ktoré nemá „veľkosť“ 3, ale N. Inak povedané, máme veľký štvorec rozdelený mriežkou na N × N menších štvorcov, každý z nich je opäť rozdelený na N × N malých štvorčekov a dopĺňame čísla od 1 do N². Ak si vezmeme postupne väčsie a väčšie N, dostaneme tak stále ťažší a ťažší hlavolam. Teraz predpokladajme, že máme počítačový program, ktorým takéto Sudoku riešime a zapisujeme si, ako dlho mu to trvá pre jednotlivé N. Dostaneme tak akúsi závislosť času vyriešenia (povedzme v minútach) od veľkosti Sudoku. Ak má táto závislosť tvar mocniny – napríklad N³, N⁵ alebo N⁹ alebo dačo podobné, povieme, že problém riešenia Sudoku patrí do triedy P, teda do triedy jednoducho vyriešiteľných problémov [3].
Namiesto čísel väčších ako 9 sú použité písmená.
Skratka P pochádza od slova polynóm (mnohočlen, t.j. výraz typu N³ + 2 N² – 3 N + 6) – ide totiž o funkciu, ktorá s rastúcim N rastie relatívne pomaly, na rozdiel od iných funkcií, napríklad exponenciály alebo faktoriálu. Dôležité je povedať, že pre veľké množstvo problémov poznáme iba také riešiace algoritmy, ktoré bežia v exponenciálnych, faktoriálových, atď. časoch. Idú teda oveľa pomalšie.
V probléme P verzus NP sa teda pýtame, či je pravda, že každý problém, ktorého riešenie vieme overiť v polynomiálnom čase, vieme aj vyriešiť v polynomiálnom čase. Väčšina vedcov predpokladá negatívnu odpoveď, dôkaz nám však dodnes uniká. Ide však o veľmi dôležitú otázku, ktorej rozriešenie môže mať potenciálne veľký dopad na matematiku a informatiku. Ak by sa napríklad dokázalo P = NP, mohlo by to znamenať, že vieme zostrojiť programy, ktoré budú efektívne prelamovať dnes používané šifry. Čo je však ešte zásadnejšie, mohli by sme vedieť zostrojiť programy, ktoré by do istej miery nahradili prácu matematikov, menovite by boli schopné dokazovať (mnohé) matematické vety [4].
[Frico]Zdroj: wiki (P versus NP problem, Mathematics of Sudoku, Glossary of Sudoku), https://www.claymath.org/millennium-problems
P.S. Použitý príklad Sudoku neplní len ilustratívnu funkciu. Dnes totiž vieme, že riešenie Sudoku je takzvaný NP úplný problém. Znamená to, že ľuboboľný NP problém vieme previesť na riešenie tohoto hlavolamu (prípadne na hocijaký iný NP úplný problém). Na plné rozhodnutie toho, či P = NP preto stačí ukázať, či Sudoku patrí alebo nepatrí do triedy P (t.j. či existuje alebo neexistuje jednoduchý algoritmus na vyriešenie).
[1] Popis Sudoku pre tých, ktorí tento hlavolam nepoznajú: Rozdeľme štvorec mriežkou na 9 menších štvorcov a každý z týchto štvorcov opäť na 9 menších štvorcov. Dostaneme tak 9 × 9 = 81 maličkých štvorčekov. Do niektorých týchto štvorčekov máme vpísané niektoré čísla s hodnotami od 1 do 9. Cieľom je doplniť všetky zvyšné prázdne štvorčeky číslami tak, aby sa v každom riadku, stĺpci i každom z 9 stredných štvorcov vyskytli všetky čísla od 1 do 9 práve raz.[2] O tom, čo myslíme pod jednoduchosťou, si povieme v ďalšom odseku.
[3] Presnejšie povedané, do triedy P patria problémy, ktoré vieme vyriešiť programom bežiacim najviac v čase A × Nᴮ, pre nejaké čísla A, B. Treba tiež povedať, že žiaden takto rýchlo bežiaci program pre riešenie Sudoku nepoznáme.
[4] Totiž overenie správnosti dôkazu matematickej vety je relatívne jednoduché. Ak by teda platilo P = NP, znamenalo by to, že existuje aj jednoduchý (a automatizovateľný) spôsob nájdenia správneho dôkazu.