Kelas kompleksitas P sering kali dilihat sebagai sebuah abstraksi matematika model-model yang komputasi tugas-tugas yang mengakui algoritma yang efisien. Hipotesis ini disebut tesis Cobham Edmonds. NP kelas kompleksitas, di sisi lain, berisi banyak masalah yang orang ingin memecahkan efisien, tetapi untuk yang tidak ada algoritma efisien dikenal, seperti Boolean satisfiabilitas masalah, masalah jalur Hamiltonian dan masalah penutup vertex. Karena mesin Turing deterministik adalah mesin khusus non-teteristik Turing, mudah diamati bahwa setiap masalah di P juga merupakan anggota dari NP kelas.
Apa yang sering dianggap sebagai sebuah abstraksi ilmiah model tugas komputasi yang mengakui algoritma yang efisien?
Kelas kompleksitas P