Vad är den beräknade komplexitetsteorin?

Beräkningskomplexitetsteori är ett område inom matematik och datavetenskap som handlar om de resurser som krävs för att lösa problem på ett datorsystem. Ett antal tekniker finns tillgängliga för att bestämma resursbehovet för ett problem. Vissa problem kanske inte är möjliga på befintliga datorsystem på grund av deras resursbehov. Forskare klassificerar problem efter svårigheter och kan dela beräkningar i polynomiala (P) kontra nonterministic polynomial (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 datatekniken 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. Problemets löslighet bestäms inte nödvändigtvis av dess komplexitet utan av algoritmerna som används för att lösa det.

I beräkningskomplexitetsteorin är ett P-problem ett problem som kan lösas i polynomtid med en enkel algoritm. Det kan fortfarande kräva betydande resurser, men det är både lösbart och kan kontrolleras av datorn. Sådana problem kan tänkas vara lika snabba lösbara så länge en dator har tillgängliga resurser för att hantera nödvändiga beräkningar.

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, till exempel parallella Turing-maskiner som kan utforska flera alternativ. Problemet kan vara lösbart 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 kan avancerat logiskt tänkande, eftersom tipppunkten ofta är en logik snarare än ren beräkningssvårighet. 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 i beräkningskomplexitetsteorin.

Klassificering av P mot NP-problem genom beräkningskomplexitetsteori kan vara en komplex uppgift, och problem kan förskjutas fram och tillbaka över klyftan. En liten uppsättning beräkningsproblem passar inte snyggt i någon kategori och klassificeras ibland som varken för att återspegla 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 med 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, högdrivna datorsystem.