[informatica] Is P=NP (; vervolg; slot)

[op=op]

Een beroemd onopgelost probleem is: Is P=NP?

Wat is P?

P staat voor "Polynomial time". Voorbeeld:
Stel ik heb een programma geschreven om decimalen van

\(\pi = 3,14159\cdots\)

te berekenen.
Voor de 1-ste decimaal heeft de computer a_1 berekeningen nodig.
Voor de eerste 2 decimalen a_2 en voor de eerste 3 decimalen a_3 berekeningen.
We zetten het in een rijtje:

\(a_1, a_2, a_3, a_4, \cdots\)

.
Het is ondoenlijk en ook niet nodig om die waarden exact uit te rekenen. We kunnen het aantal berekeningen die nodig zijn grof schatten en dat is normalerwijze voldoende.

Het rijtje stijgt naar oneindig. Om die stijging te temperen delen we de termen als in het volgende rijtje:

\(\frac{a_1}{1}, \frac{a_2}{2}, \frac{a_3}{3}, \cdots\)

.
Blijkt dat dit rijtje nog steeds naar oneindig gaat, dan doen we er een schepje bovenop:

\(\frac{a_1}{1^2}, \frac{a_2}{2^2}, \frac{a_3}{3^2}, \cdots\)

.
Dit rijtje zal nu minder snel stijgen. Stijgt het nog steeds naar oneindig, dan bekijken we

\(\frac{a_1}{1^3}, \frac{a_2}{2^3}, \frac{a_3}{3^3}, \cdots\)

.
Stel dat dit rijtje niet meer naar oneindig gaat. Dan is de rij begrensd en dus is zeker dat

\(\lim_{n\to\infty}\frac{a_n}{n^k} = 0\)

voor k>3.

P is de verzameling van alle computerprogramma's (algoritmen) die te temperen zijn tot uiteindelijk een naar 0 convergerende rij.

Niet P

Als een algoritme niet in P zit, dan geldt:

\(\lim_{n\to\infty}\frac{a_n}{n^k} = \infty\)

voor elk natuurlijk getal k.
Dit soort algoritmen hebben een groot probleem zoals we zo zullen zien.
Voorbeeld: We willen een computerprogramma schrijven om te bepalen of een schaak- of dampartij altijd te winnen is voor wit.
Zoals iedereen wel weet zijn de huidige computers daar niet toe in staat.
Voor een dambord van 4 bij 4, 5 bij 5 of 6 bij 6 heeft de computer geen enkel probleem. Voor een 8 bij 8 bord kun je een supercomputer dagenlang bezighouden. Voor een 10 bij 10 bord wordt het de computer te veel. Als er straks quantumcomputers zijn is het schaak- en damprobleem mogelijk wel te kraken. Maar het aantal berekeningen voor een 10 bij 10 bord is vrijwel niets vergeleken bij een 12 bij 12 bord. Daarvoor zal ook de quantumcomputer zijn hoofd moeten buigen.
Kortom, in het begin lijken het aantal berekeningen nog wel mee te vallen, maar al snel exploderen het aantal berekeningen.

Er zijn heel veel problemen die tot deze katagorie behoren, zoals het handelsreizigers probleem (en ook het oplossen van een Sudoku is een niet P probleem. Voor een 9 bij 9 bord nog goed te doen, maar al snel daarna onmogelijk)
Wordt vervolgd.

[op=op]

Het handelsreizigers probleem: Een handelsreiziger wil te voet een aantal klanten bezoeken. In welke volgorde moet hij die klanten bezoeken opdat de totale wandelroute zo kort mogelijk is.
Het handelsreizigers probleem korten we af tot HRP.

Voor het HRP zijn talloze algoritmen bedacht. Ze bleken allemaal niet in P te zitten. Maar misschien bestaat er wel een algoritme in P, maar is nog niemand in staat geweest zo'n slim algoritme te bedenken.

Wat is NP?

NP staat voor "Nondeterministic Polynomial time".
Om een algoritme in P voor het HRP te bedenken bied ik je een speciale functie aan; de functie MIRAKEL. Deze functie accepteert een eindig aantal argumenten en geeft er één van terug. "b.v. x = MIRACLE(a,b,c); nu is x=a of b of c".
Hij geeft niet zomaar een van de argumenten terug; hij geeft de beste terug.
In geval van het HRP geef je als argumenten alle plaatsen die de handelsreiziger nog niet bezocht heeft. MIRAKEL geeft dan terug een van de plaatsen die hij vervolgens moet bezoeken om een kortste route te krijgen.
Kijk, dat is nog eens een functie waar je wat aan hebt.
Een probleem zit in NP als er een algoritme bestaat in P waarbij je gebruik mag maken van de functie MIRAKEL.
Het HRP zit in NP.
Het damprobleem zit ook in NP. Bij elke zet kiest MIRAKEL voor jou de zet uit die uiteindelijk naar winst zal voeren (of remise, als dat het hoogst haalbare is).

Nu de vraag: Is P=NP?
Met andere woorden, als een probleem in NP zit (dus een algoritme kent in P met gebruikmaking van MIRAKEL), bestaat er dan ook een algoritme voor dat probleem in P zonder MIRAKEL.
Volgens mij gelooft niemand dat P=NP al heeft dat nog niemand kunnen bewijzen.
Het is wel heel belangrijk om te weten, want er geldt
HRP

\(\in\)

P

\(\Leftrightarrow\)

P=NP.
(M.a.w. Voor het HRP bestaat een algoritme in P precies dan als P=NP).

Na deze ontdekking is het zoeken naar een efficiënt algoritme voor het HRP gestaakt. En zo is het ook vergaan met veel van dit soort problemen.
Voor men tegenwoordig naar efficiente (i.e. in P) algoritmen gaat zoeken onderzoekt men eerst of daarvoor moet gelden dat P=NP.

[op=op]

Als een probleem

\(X\)

NP complete wordt genoemd, dan geldt

\(X\in \mbox{ P }\Leftrightarrow \mbox{ P = NP}\)

Een graadje erger nog zijn de NP hard problemen.
Een probleem heet NP hard als het NP complete is en als bovendien voor elk algoritme geldt dat het m.b.v. NP complete algoritmen in polynomial time (P) oplosbaar is m.b.v. een MIRAKEL functie. (Voorbeeld van een NP hard probleem is het oplossen van een Sudoku).

Een lijst met meer dan 200 problemen waarvan men aangetoond heeft dat ze NP complete zijn:
http://www.csc.kth.se/~viggo/problemlist/