Apa artinya keras kepala dalam praktek terbuka untuk diperdebatkan. Mengatakan bahwa suatu masalah tidak dalam P tidak berarti bahwa semua kasus besar dari masalah itu sulit atau bahkan sebagian besar dari mereka adalah masalah. Sebagai contoh, masalah keputusan dalam aritmatika Presburger telah ditunjukkan tidak berada dalam P, namun algoritma telah ditulis yang memecahkan masalah pada waktu yang wajar dalam banyak kasus. Demikian pula, algoritma dapat memecahkan masalah knapsack NP-lengkap pada berbagai ukuran dalam waktu kurang dari kuadratik dan pemecah SAT secara rutin menangani contoh besar masalah kepuasan-Boolean NP-lengkap.
Apa contoh dari masalah yang algoritma yang efektif telah memberikan solusi terlepas dari tingkat kepraktisan yang terkait dengan luasnya ukuran?
Masalah ransel NP-lengkap
masalah knapsack NP-lengkap
Apa PRI
contoh NNO
dari PPO
masalah NNO
yang PRR
algoritma NNO
yang PRR
efektif ADJ
telah TAME
memberikan VBT
solusi NNO
terlepas VBP
dari PPO
tingkat NNO
kepraktisan NNO
yang PRR
terkait VBP
dengan PPO
luas ADJ
nya PRK
ukuran NNO
? PUN