Įtaisas, kuris gali naudoti taisyklių rinkinį ir įvestį, kad nustatytų rezultatą, nors minėtas įrenginys yra hipotetinis, vadinamas kuo? Atsižvelgiant į ankstesnį klausimą, parašykite kontekstą, kuriame būtų atsakymas. Tai gali būti nuo 1 iki 20 sakinių. Kontekstas:
Sudėtingumo klasė P dažnai laikoma matematine abstrakcija, modeliuojančia tuos skaičiavimo uždavinius, kurie pripažįsta efektyvų algoritmą. Ši hipotezė vadinama Cobham-Edmonds teze. Kompleksumo klasėje NP, kita vertus, yra daug problemų, kurias žmonės norėtų išspręsti efektyviai, tačiau kurių nėra žinomas veiksmingas algoritmas, pavyzdžiui, Boole'io patenkinamumo problema, Hamiltono kelio problema ir viršūnės uždengiamumo problema. Kadangi deterministinės Turingo mašinos yra specialios nedeterministinės Turingo mašinos, lengva pastebėti, kad kiekviena P problema taip pat priklauso NP klasei.