36
9.4.2003
Teemu Kerola, Copyright 2003
Laskennan teoriasta ja algoritmianalyysistä
todistettuja lauseita (3)
todistettuja lauseita (3)
•Valitaanpa mikä
tahansa aikaraja tai muistin koko, niin aina on olemassa sellainen ongelma, että
–(1) siihen on olemassa ratkaisu ja
–(2) kaikki ongelman ratkaisevat ohjelmat vievät enemmän aikaa tai muistitilaa kuin ennalta annettu
raja
•On olemassa sellaisia ongelmia, että niitä ei voi ratkaista millään tietokoneella
•On olemassa suuri joukko tunnettuja vaikeita ongelmia, joista ei vielä tiedetä, kuinka
vaikeita ne oikeastaan ovat
vaikeita ne oikeastaan ovat
P = NP
?