Kompleksitas kelas P sering dilihat sebagai abstraksi matematis yang memodelkan tugas-tugas komputasi yang mengakui algoritma yang efisien. Hipotesis ini disebut tesis Cobham-Edmonds. NP kelas kompleksitas, di sisi lain, mengandung banyak masalah yang orang ingin selesaikan secara efisien, tetapi yang tidak diketahui algoritma yang efisien, seperti masalah kepuasan Boolean, masalah jalur Hamiltonian, dan masalah penutup simpul. Karena mesin Turing deterministik adalah mesin Turing non-deterministik khusus, mudah diamati bahwa setiap masalah dalam P juga anggota NP kelas.
Hipotesis apa yang dikaitkan dengan kelas kompleksitas P yang dipandang sebagai abstraksi matematis dengan fungsionalitas algoritmik yang efisien?
Tesis Cobham – Edmonds
tesis Cobham-Edmonds
Hipotesis NNO
apa PRI
yang PRR
dikaitkan VBP
dengan PPO
kelas NNO
kompleksitas NNO
P NNO
yang PRR
dipandang VBP
sebagai PPO
abstraksi NNO
matematis ADJ
dengan PPO
fungsionalitas NNO
algoritmik NNO
yang PRR
efisien ADJ
? PUN