Laskennallisen kompleksisuuden teoria
Laskennallisen kompleksisuuden teoria on teoreettisen tietojenkäsittelytieteen alue, jonka pääasiallinen tehtävä on luokitella ja vertailla käytännöllistä vaikeutta ongelmien ratkaisussa. Klassisen laskettavuusteorian mukaan vaikeat ongelmat voidaan ratkaista käyttämällä tarpeeksi "raakaa voimaa", mutta kompleksisuuden teoria erottelee miten ongelma voidaan käytännöllisesti ratkaista.[1] Kompleksisuuden teoria käsittelee algoritmeja. Jotkin laskennalliset ongelmat ovat niin vaikeita, että nopeaa algoritmia ratkaisuun ei ole ja se voidaan todistaa. Joillekin ongelmille on nopea algoritmi vaikka itsestäänselvältä vaikuttava ratkaisu olisi hidas. Usein tutkittavat ongelmat eivät asetu kumpaankaan kategoriaan, jolloin niiden vaikeutta vertaillaan NP-täydellisyyden avulla.[2]
Katso myös
[muokkaa | muokkaa wikitekstiä]Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ Computational Complexity Theory plato.stanford.edu. 27.7.2015. Viitattu 29.4.2024. (englanniksi)
- ↑ Leslie Ann Goldberg: Research seh.ox.ac.uk. 26.6.2019. Viitattu 29.4.2024. (englanniksi)