Wat is de theorie van de computationele complexiteit?

Computational Complexity Theory 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 resourcevereisten van een probleem te bepalen.Sommige problemen zijn mogelijk niet haalbaar op bestaande computersystemen vanwege hun eisen van middelen.Onderzoekers classificeren problemen per moeilijkheid en kunnen berekeningen verdelen in polynoom (P) versus niet -terministische polynoom (NP) problemen.

Het oplossen van een berekening vereist bronnen zoals tijd, opslagruimte en hardware.Een computersysteem kan beperkingen hebben die een probleem functioneel onmogelijk maken om op te lossen omdat het niet de beschikbare bronnen heeft.Naarmate de computertechnologie verbetert, kan een voorheen onoplosbaar probleem oplosbaar worden met behulp van nieuwe technologie en onderzoek op het gebied van theorie van de computationele complexiteit.De oplosbaarheid van een probleem wordt niet noodzakelijkerwijs bepaald door de complexiteit ervan, maar op de algoritmen die worden gebruikt om het op te lossen.

In de theorie van de computationele complexiteit is een P -probleem er een dat in polynomiale tijd kan worden opgelost met een eenvoudig algoritme.Het kan nog steeds substantiële bronnen vereisen, maar het is zowel oplosbaar als checkbaar per computer.Dergelijke problemen kunnen zo snel oplosbaar worden beschouwd, zolang een computer de beschikbare bronnen heeft om de nodige berekeningen aan te kunnen.

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 kan op deze manier oplosbaar zijn, maar het zal aanzienlijk meer middelen vereisen.Dergelijke problemen kunnen gemakkelijker zijn voor menselijke operators die in staat zijn tot geavanceerd logisch denken, omdat het omslagpunt vaak een van logica is in plaats van pure berekeningsproblemen.Het probleem van de reizende verkoper, waarin het doel is om de meest efficiënte route tussen een aantal steden langs een route te vinden, is een klassiek voorbeeld van een NP -probleem in de computationele complexiteitstheorie.

Classificatie van P versus NP -problemen door computationele complexiteitstheorieKan een complexe taak zijn en problemen kunnen over de kloof heen en weer verschuiven.Een kleine reeks rekenproblemen past niet netjes in beide categorieën en worden soms geclassificeerd als geen van beide om dit weer te geven.Het kan uiteindelijk mogelijk 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 die een vergelijkbare structuur hebben.In anderen 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.