Vad är beräkningskomplexitetsteorin?

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 resurskraven för ett problem.Vissa problem kanske inte är möjliga på befintliga datorsystem på grund av deras resurskrav.Forskare klassificerar problem efter svårigheter och kan dela upp beräkningar i polynom (P) kontra icke -terministiska polynomiska problem (NP).

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.Solvabiliteten hos ett problem bestäms inte nödvändigtvis av dess komplexitet utan på algoritmerna som används för att lösa den.

I beräkningskomplexitetsteorin är ett P -problem ett som kan lösas under polynomtid med en enkel algoritm.Det kan fortfarande kräva betydande resurser, men det är både lösbart och kontrollerbart med dator.Sådana problem kan betraktas så snabbt 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 enklare för mänskliga operatörer som kan avancerat logiskt tänkande, eftersom tipppunkten ofta är en av logik snarare än ren beräkningssvårigheter.Det resande säljarproblemet, där målet är att hitta den mest effektiva vägen mellan ett antal städer längs en rutt, är ett klassiskt exempel på ett NP -problem i beräkningskomplexitetsteorin.

Klassificering av P kontra NP -problem genom beräkningskomplexitetsteorikan vara en komplex uppgift, och problem kan växla fram och tillbaka över klyftan.En liten uppsättning beräkningsproblem passar inte snyggt i någon av kategorin 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 att utforska sådana program och utveckla tillvägagångssätt för att lösa dem är ett viktigt område inom matematik och datavetenskap som bidrar till utvecklingen av avancerade, högdrivna datorsystem.