Hvad er beregningskompleksitetsteorien?

Computational complexity theory er et område i matematik og datalogi, der beskæftiger sig med de ressourcer, der er nødvendige for at løse problemer på et computersystem. Der er en række teknikker til rådighed for at bestemme ressourcekravene til et problem. Nogle problemer er muligvis ikke gennemførlige på eksisterende computersystemer på grund af deres ressourcebehov. Forskere klassificerer problemer ved hjælp af vanskeligheder og kan opdele beregninger i polynomiale (P) versus ikke-terministiske polynomiske (NP) problemer.

Løsning af en beregning kræver ressourcer som tid, lagerplads og hardware. Et computersystem kan have begrænsninger, der gør et problem funktionelt umuligt at løse, fordi det ikke har de tilgængelige ressourcer. Når computerteknologien forbedres, kan et tidligere uløseligt problem blive løseligt ved hjælp af ny teknologi og forskning inden for beregningskompleksitetsteori. Problemets opløselighed bestemmes ikke nødvendigvis af dets kompleksitet, men af ​​algoritmerne, der bruges til at løse det.

I beregningskompleksitetsteori er et P-problem et problem, der kan løses i polynomisk tid med en ligetil algoritme. Det kræver muligvis stadig betydelige ressourcer, men det kan både løses og kontrolleres af computeren. Sådanne problemer kunne tænkes på så hurtigt at kunne løses, så længe en computer har de tilgængelige ressourcer til at håndtere de nødvendige beregninger.

NP-problemer er mere komplekse. Det er ikke muligt at anvende en enkelt algoritme, og det kan være nødvendigt at bruge mere avancerede indstillinger, såsom parallelle Turing-maskiner, der kan udforske flere muligheder. Problemet kan muligvis løses på denne måde, men det vil kræve betydeligt flere ressourcer. Sådanne problemer kan være lettere for menneskelige operatører, der er i stand til avanceret logisk tænkning, fordi vippepunktet ofte er et af logik snarere end ren beregningsproblemer. Det rejsende sælgerproblem, hvor målet er at finde den mest effektive rute mellem et antal byer langs en rute, er et klassisk eksempel på et NP-problem inden for beregningskompleksitetsteori.

Klassificering af P versus NP problemer gennem beregningskompleksitetsteori kan være en kompleks opgave, og problemer kan skifte frem og tilbage over kløften. Et lille sæt beregningsproblemer passer ikke pænt i nogen kategori og klassificeres undertiden som ingen af ​​dem for at afspejle dette. Det kan i sidste ende være muligt at udvikle en algoritme til at løse et NP-problem, og i nogle tilfælde kan det muligvis gælde for andre problemer, der har en lignende struktur. I andre kan det dog være problemspecifikt. Processen med at udforske sådanne programmer og udvikle tilgange til at løse dem er et vigtigt område i matematik og datalogi, der bidrager til udviklingen af ​​avancerede, højdrevne computersystemer.