Laskennallinen monimutkaisusteoria on matematiikan ja tietojenkäsittelytieteen ala, joka koskee resursseja, joita tarvitaan tietokonejärjestelmän ongelmien ratkaisemiseen. On olemassa useita tekniikoita ongelman resurssitarpeiden määrittämiseksi. Jotkin ongelmat eivät ehkä ole mahdollisia olemassa olevissa tietokonejärjestelmissä niiden resurssitarpeen vuoksi. Tutkijat luokittelevat ongelmat vaikeuksien mukaan ja voivat jakaa laskelmat polynomi- (P) ja ei -hallinnollisiin polynomi (NP) -ongelmiin.
Laskennan ratkaiseminen vaatii resursseja, kuten aikaa, tallennustilaa ja laitteistoa. Tietokonejärjestelmässä saattaa olla rajoituksia, jotka tekevät ongelman toiminnallisesti mahdottomaksi ratkaista, koska sillä ei ole käytettävissä olevia resursseja. Tietotekniikan kehittyessä aiemmin ratkaisematon ongelma saattaa ratketa uuden tekniikan ja laskennallisen monimutkaisuusteorian tutkimuksen avulla. Ongelman ratkaisukyky ei välttämättä määräydy sen monimutkaisuudesta vaan sen ratkaisemiseen käytetyistä algoritmeista.
Laskennallisen monimutkaisuuden teoriassa P -ongelma on sellainen, joka voidaan ratkaista polynomiajassa yksinkertaisella algoritmilla. Se saattaa silti vaatia huomattavia resursseja, mutta se on sekä ratkaistavissa että tarkistettavissa tietokoneella. Tällaiset ongelmat voidaan ajatella ratkaistaviksi nopeasti, kunhan tietokoneella on käytettävissä resurssit tarvittavien laskelmien käsittelyyn.
NP -ongelmat ovat monimutkaisempia. Yhtä algoritmia ei voi käyttää, ja saattaa olla tarpeen käyttää kehittyneempiä vaihtoehtoja, kuten rinnakkaisia Turingin koneita, jotka voivat tutkia useita vaihtoehtoja. Ongelma voidaan ratkaista tällä tavalla, mutta se vaatii huomattavasti enemmän resursseja. Tällaiset ongelmat voivat olla helpompia ihmisoperaattoreille, jotka kykenevät kehittyneeseen loogiseen ajatteluun, koska käännekohta on usein logiikan sijasta pelkkä laskentavaikeus. Matkava myyjäongelma, jonka tavoitteena on löytää tehokkain reitti useiden kaupunkien välillä reitin varrella, on klassinen esimerkki laskennallisen monimutkaisuusteorian NP -ongelmasta.
P: n ja NP: n ongelmien luokittelu laskennallisen monimutkaisuusteorian kautta voi olla monimutkainen tehtävä, ja ongelmat voivat siirtyä edestakaisin kuilun yli. Pieni joukko laskennallisia ongelmia ei sovi siististi kumpaankaan luokkaan, ja joskus ne luokitellaan kummaksi tämän heijastamiseksi. Lopulta saattaa olla mahdollista kehittää algoritmi NP -ongelman ratkaisemiseksi, ja joissakin tapauksissa se saattaa koskea muita ongelmia, joilla on samanlainen rakenne. Toisissa se voi kuitenkin olla ongelmakohtaista. Tällaisten ohjelmien tutkiminen ja lähestymistapojen kehittäminen niiden ratkaisemiseksi on tärkeä matematiikan ja tietojenkäsittelytieteen alue, joka edistää kehittyneiden, suuritehoisten tietokonejärjestelmien kehittämistä.