Polynomiajassa

Polynomiajassa tarkoitetaan, että algoritmin ajoaika kasvaa syötteen koon n mukaan enintään polynomisesti. Käytännössä on olemassa kiinteä kokonaisluku k ja vakio C, jolloin T(n) ≤ C n^k kaikille riittävän suurille n. Tällaiset ratkaisut kuuluvat tyypillisesti P-luokkaan, joka kattaa deterministisellä koneella ratkaistavien päätöksellisten ongelmien polynomiajassa ratkaisut.

Esimerkkejä polynomiajassa ratkaistuista ongelmista ovat useat perusalgoritmit: lajittelu (esimerkiksi mergesortin aikavaativuus O(n log n)), lyhyimpien polkujen etsiminen graafissa (Dijkstra – O((V+E) log V) tai O(V^2) tietyillä toteutuksilla) sekä monet laskennalliset tehtävät. Nämä aikavaativuudet ovat polynomisia, koska ne voidaan ylärajoittaa n^k -tyyppisellä kasvulla.

P- ja NP-luokat: P tarkoittaa päätöksellisiä ongelmia, jotka voidaan ratkaista polynomiajassa deterministisellä laskukoneella. NP tarkoittaa ongelmia, joiden ratkaisu voidaan tarkistaa polynomiajassa nondeterministisellä katselulla. P on aliluokka NP: P ⊆ NP. P vs NP on yksi tietojenkäsittelytieteen keskeisimmistä avoimista kysymyksistä.

Merkitys ja rajoitteet: polynomiajassa ratkaiseminen on tärkeä mittari algoritmisen tehokkuuden kannalta. Kuitenkin polynominen aika ei aina tarkoita käytännössä nopeaa, varsinkin suurille syötteille; teoreettisesti polynominen algoritmi voi silti olla hidasta. Välillä tutkimuksessa on ratkaistavina ongelmia, joiden polynomiajassa ratkaiseminen ei ole vielä varmistettu tai sitä ei ole osoitettu mahdolliseksi.