Door Aad Offerman

Freelancer

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.

Tweakers maakt gebruik van cookies

Tweakers plaatst functionele en analytische cookies voor het functioneren van de website en het verbeteren van de website-ervaring. Deze cookies zijn noodzakelijk. Om op Tweakers relevantere advertenties te tonen en om ingesloten content van derden te tonen (bijvoorbeeld video's), vragen we je toestemming. Via ingesloten content kunnen derde partijen diensten leveren en verbeteren, bezoekersstatistieken bijhouden, gepersonaliseerde content tonen, gerichte advertenties tonen en gebruikersprofielen opbouwen. Hiervoor worden apparaatgegevens, IP-adres, geolocatie en surfgedrag vastgelegd.

Meer informatie vind je in ons cookiebeleid.

Sluiten

Toestemming beheren

Hieronder kun je per doeleinde of partij toestemming geven of intrekken. Meer informatie vind je in ons cookiebeleid.

Functioneel en analytisch

Deze cookies zijn noodzakelijk voor het functioneren van de website en het verbeteren van de website-ervaring. Klik op het informatie-icoon voor meer informatie. Meer details

janee

    Relevantere advertenties

    Dit beperkt het aantal keer dat dezelfde advertentie getoond wordt (frequency capping) en maakt het mogelijk om binnen Tweakers contextuele advertenties te tonen op basis van pagina's die je hebt bezocht. Meer details

    Tweakers genereert een willekeurige unieke code als identifier. Deze data wordt niet gedeeld met adverteerders of andere derde partijen en je kunt niet buiten Tweakers gevolgd worden. Indien je bent ingelogd, wordt deze identifier gekoppeld aan je account. Indien je niet bent ingelogd, wordt deze identifier gekoppeld aan je sessie die maximaal 4 maanden actief blijft. Je kunt deze toestemming te allen tijde intrekken.

    Ingesloten content van derden

    Deze cookies kunnen door derde partijen geplaatst worden via ingesloten content. Klik op het informatie-icoon voor meer informatie over de verwerkingsdoeleinden. Meer details

    janee