Turing-machine: de grenzen van berekenbaarheid

P =? NP

In de theoretische informatica noemen we een probleem oplosbaar als we voor een deterministische Turing-machine een algoritme - een finite state machine dus - kunnen verzinnen, dat eindig is voor alle mogelijke input strings op de tape. De laatste state van onze finite state machine is het antwoord voor de betreffende input-string, maar er kan tijdens het uitvoeren van het algoritme ook nog output naar de tape worden geschreven.

Daarmee zijn we aanbeland bij een van de belangrijkste kwesties in de complexiteitstheorie. Problemen waarvoor een algoritme gevonden kan worden dat in redelijke tijd kan worden uitgevoerd, zitten in de complexiteitsklasse P. De maximaal benodigde rekentijd kan dan aan de hand van de lengte van de invoerstring worden bepaald met een polynoomfunctie.

Problemen waarvoor nog geen efficiënt algoritme is gevonden, zitten in de NP-klasse. Deze Niet-deterministisch Polynomiale problemen zijn alleen op te lossen met algoritmen waarvan de rekentijd sneller dan polynomiaal toeneemt als de invoerstring langer wordt. Dat betekent dat de rekentijd voor langere invoerstrings al snel onwerkbaar groot wordt.

Is er voor een probleem helemaal geen algoritme te vinden, dan heet dat probleem onbeslisbaar. Het bekendste onbeslisbare probleem is het Halting-probleem: er is geen algoritme te bedenken dat kan vaststellen of een algoritme - of een Turing-machine - aan de hand van een eindige invoer ook daadwerkelijk een antwoord zal geven. Dit probleem staat model voor een hele zwik onbeslisbare problemen. Voor de wiskundeliefhebbers: volgens het theorema van Rice is het bepalen van een algoritme een onbeslisbaar probleem voor elke partiële functie met niet-triviale eigenschappen. Dat heeft enorme consequenties voor programmeertools die proberen de correctheid of de eindigheid van programma's aan te tonen.

NP-Compleet

Dat voor een willekeurig NP-probleem nog geen polynomiaal algoritme is gevonden, wil nog niet zeggen dat een dergelijk algoritme niet bestaat. Het zou dus kunnen dat er alsnog een efficiënt algoritme voor zo'n NP-probleem wordt verzonnen. Sterker nog, van een aantal NP-problemen is bewezen dat als daar een P-algoritme voor kan worden gevonden, dat dan voor álle NP-problemen een dergelijk algoritme bestaat. Deze klasse van de moeilijkste problemen binnen het NP-domein heet NP-Compleet.

De vraag of uiteindelijk voor alle problemen in de klasse NP een polynomiaal algoritme kan worden gevonden, waarmee die problemen dus in de klasse P terecht komen, wordt door de theoretici P =? NP genoemd. Het vermoeden is echter dat er problemen zijn waarvoor helemaal geen P-algoritme kan bestaan, maar dat bewijzen is vers twee. Dit is niet voor niets een van de zeven Millennium-vraagstukken, waar een geldprijs van een miljoen dollar aan is verbonden.

Bovendien lijken er problemen te zijn die wel in NP zitten maar niet in P of NP-Compleet. Omdat dat laatste betekent dat ze niet kunnen worden gereduceerd naar een NP-Compleet probleem, zijn deze zogenaamde open problemen weer anders van aard dan de problemen in P en NP-Compleet.

Lees meer