Algoritmi, joka voi näyttää erilaisia käyttäytymisiä useissa suorituksissa, vaikka se käyttäisi samaa syöttöä, kutsutaan? Kirjoita edellisen kysymyksen perusteella tekstiyhteys, joka sisältää vastauksen. Se voi olla 1 - 20 lausetta. - Mitä tarkoitat?
Monimutkaisuusluokka P nähdään usein matemaattisena abstraktioona, joka mallintaa niitä laskennallisia tehtäviä, jotka hyväksyvät tehokkaan algoritmin. Tätä hypoteesia kutsutaan Cobham-Edmondsin teesiksi. Monimutkaisuusluokka NP puolestaan sisältää monia ongelmia, joita ihmiset haluaisivat ratkaista tehokkaasti, mutta joiden osalta tehokasta algoritmia ei tunneta, kuten Boolen tyydyttävyysongelma, Hamiltonian polkuongelma ja huippupeiteongelma. Koska deterministiset Turingin koneet ovat erityisiä ei-deterministisia Turingin koneita, on helppo havaita, että jokainen ongelma P:ssä kuuluu myös luokkaan NP.