Wat is de computationele complexiteitstheorie?
Computationele complexiteitstheorie is een gebied van wiskunde en informatica dat zich bezighoudt met de middelen die nodig zijn om problemen op een computersysteem op te lossen. Er zijn een aantal technieken beschikbaar om de vereiste middelen voor een probleem te bepalen. Sommige problemen zijn mogelijk niet haalbaar op bestaande computersystemen vanwege de benodigde bronnen. Onderzoekers classificeren problemen per moeilijkheid en kunnen berekeningen verdelen in polynomiale (P) versus niet-terminale polynomiale (NP) problemen.
Het oplossen van een berekening vereist middelen zoals tijd, opslagruimte en hardware. Een computersysteem kan beperkingen hebben die een probleem functioneel onmogelijk oplossen, omdat het niet over de beschikbare bronnen beschikt. Naarmate computertechnologie verbetert, kan een voorheen onoplosbaar probleem oplosbaar worden met behulp van nieuwe technologie en onderzoek op het gebied van computationele complexiteitstheorie. De oplosbaarheid van een probleem wordt niet noodzakelijkerwijs bepaald door de complexiteit ervan, maar door de algoritmen die worden gebruikt om het op te lossen.
In de computationele complexiteitstheorie is een P-probleem een probleem dat in polynoomtijd kan worden opgelost met een eenvoudig algoritme. Het kan nog steeds aanzienlijke middelen vereisen, maar het is zowel oplosbaar als controleerbaar via de computer. Zulke problemen kunnen worden gedacht als snel oplosbaar zolang een computer de beschikbare middelen heeft om de nodige berekeningen te verwerken.
NP-problemen zijn complexer. Het is niet mogelijk om een enkel algoritme toe te passen en het kan nodig zijn om meer geavanceerde opties te gebruiken, zoals parallelle Turing-machines die verschillende opties kunnen verkennen. Het probleem is misschien op deze manier oplosbaar, maar er zijn aanzienlijk meer middelen voor nodig. Zulke problemen kunnen gemakkelijker zijn voor menselijke operatoren die in staat zijn tot geavanceerd logisch denken, omdat het omslagpunt vaak een logica is in plaats van louter berekeningsmoeilijkheden. Het probleem van de reizende verkoper, waarbij het doel is om de meest efficiënte route te vinden tussen een aantal steden langs een route, is een klassiek voorbeeld van een NP-probleem in de computationele complexiteitstheorie.
Classificatie van P versus NP-problemen door middel van computationele complexiteitstheorie kan een complexe taak zijn en problemen kunnen heen en weer schuiven over de kloof. Een klein aantal rekenproblemen past niet netjes in beide categorieën en wordt soms als geen van beide geclassificeerd om dit te weerspiegelen. Het zou uiteindelijk mogelijk kunnen zijn om een algoritme te ontwikkelen om een NP-probleem op te lossen, en in sommige gevallen kan het van toepassing zijn op andere problemen met een vergelijkbare structuur. In andere gevallen kan het echter probleemspecifiek zijn. Het proces van het verkennen van dergelijke programma's en het ontwikkelen van benaderingen om ze op te lossen is een belangrijk gebied van wiskunde en informatica dat bijdraagt aan de ontwikkeling van geavanceerde, krachtige computersystemen.