[informatica] Is P=NP (; vervolg; slot)
Geplaatst: 12 mei 2010, 09:30
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
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:
.
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:
.
Blijkt dat dit rijtje nog steeds naar oneindig gaat, dan doen we er een schepje bovenop:
.
Dit rijtje zal nu minder snel stijgen. Stijgt het nog steeds naar oneindig, dan bekijken we
.
Stel dat dit rijtje niet meer naar oneindig gaat. Dan is de rij begrensd en dus is zeker dat
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:
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.
Wat is P?
P staat voor "Polynomial time". Voorbeeld:
Stel ik heb een programma geschreven om decimalen van
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:
.
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:
.
Blijkt dat dit rijtje nog steeds naar oneindig gaat, dan doen we er een schepje bovenop:
.
Dit rijtje zal nu minder snel stijgen. Stijgt het nog steeds naar oneindig, dan bekijken we
.
Stel dat dit rijtje niet meer naar oneindig gaat. Dan is de rij begrensd en dus is zeker dat
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:
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.