monimutkaisuusluokat

Monimutkaisuusluokat ovat laskennan teoreettisessa perustassa käytettyjä luokitteluja laskennallisten ongelmien vaikeusasteen mukaan. Ne perustuvat resurssien, kuten ajan ja muistin, määrään, jonka tietokone tarvitsee ongelman ratkaisemiseen. Tärkeimpiä monimutkaisuusluokkia ovat P ja NP.

Luokka P sisältää ne päätösongelmat, jotka voidaan ratkaista polynomisessa ajassa. Tämä tarkoittaa, että ongelman ratkaisemiseen kuluva aika kasvaa enintään syötteen koon polynomina. Ongelmat, jotka kuuluvat P-luokkaan, ovat yleisesti ottaen "helppoja" tai tehokkaasti ratkaistavissa olevia.

Luokka NP puolestaan sisältää ne päätösongelmat, joiden ratkaisun oikeellisuus voidaan tarkistaa polynomisessa ajassa, jos ratkaisu on annettu. NP-luokan ongelmien löytäminen voi olla vaikeaa, mutta annetun ehdotetun ratkaisun varmistaminen on helppoa. Suuri avoin kysymys tietojenkäsittelytieteessä on, onko P=NP. Jos P=NP, kaikki NP-luokan ongelmat olisivat ratkaistavissa polynomisessa ajassa.

NP-täydelliset ongelmat ovat NP-luokan vaikeimpia ongelmia. Jos jokin NP-täydellinen ongelma voidaan ratkaista polynomisessa ajassa, niin kaikki NP-luokan ongelmat voidaan ratkaista polynomisessa ajassa. Siksi NP-täydellisten ongelmien tehokas ratkaiseminen olisi merkittävä läpimurto.