Beräkningskomplexitetsteori är ett område inom matematik och datavetenskap som handlar om de resurser som krävs för att lösa problem i ett datorsystem. Ett antal tekniker finns tillgängliga för att fastställa resurskraven för ett problem. Vissa problem kanske inte är genomförbara på befintliga datorsystem på grund av deras resursbehov. Forskare klassificerar problem efter svårighetsgrad och kan dela upp beräkningar i polynom (P) kontra icketerministiska polynom (NP) problem.
Att lösa en beräkning kräver resurser som tid, lagringsutrymme och hårdvara. Ett datorsystem kan ha begränsningar som gör ett problem funktionellt omöjligt att lösa eftersom det inte har tillgängliga resurser. När datortekniken förbättras kan ett tidigare olösligt problem bli lösbart med hjälp av ny teknik och forskning inom området beräkningskomplexitetsteori. Lösbarheten av ett problem bestäms inte nödvändigtvis av dess komplexitet utan av de algoritmer som används för att lösa det.
I beräkningskomplexitetsteori är ett P-problem ett som kan lösas i polynomtid med en enkel algoritm. Det kan fortfarande kräva avsevärda resurser, men det är både lösbart och kontrollerbart med dator. Sådana problem kan tänkas vara så snabbt lösbara så länge en dator har de tillgängliga resurserna för att hantera de nödvändiga beräkningarna.
NP-problem är mer komplexa. Det är inte möjligt att tillämpa en enda algoritm, och det kan vara nödvändigt att använda mer avancerade alternativ, som parallella Turing-maskiner som kan utforska flera alternativ. Problemet kan kanske lösas på detta sätt, men det kommer att kräva betydligt mer resurser. Sådana problem kan vara lättare för mänskliga operatörer som är kapabla till avancerat logiskt tänkande, eftersom vändpunkten ofta är en logik snarare än ren beräkningssvårigheter. Det resande säljarproblemet, där målet är att hitta den mest effektiva rutten mellan ett antal städer längs en rutt, är ett klassiskt exempel på ett NP-problem inom beräkningskomplexitetsteorin.
Klassificering av P kontra NP-problem genom beräkningskomplexitetsteori kan vara en komplex uppgift, och problem kan skifta fram och tillbaka över klyftan. En liten uppsättning beräkningsproblem passar inte in i någon av kategorierna och klassificeras ibland som varken för att spegla detta. Det kan så småningom vara möjligt att utveckla en algoritm för att lösa ett NP-problem, och i vissa fall kan det gälla andra problem som har en liknande struktur. I andra kan det dock vara problemspecifikt. Processen att utforska sådana program och utveckla metoder för att lösa dem är ett viktigt område inom matematik och datavetenskap som bidrar till utvecklingen av avancerade, kraftfulla datorsystem.