Banyak kelas kompleksitas yang diketahui diduga tidak sama, tetapi ini belum terbukti. Misalnya P ⊆ NP ⊆ PP ⊆ PSPACE, tetapi ada kemungkinan bahwa P = PSPACE. Jika P tidak sama dengan NP, maka P juga tidak sama dengan PSPACE. Karena ada banyak kelas kompleksitas yang diketahui antara P dan PSPACE, seperti RP, BPP, PP, BQP, MA, PH, dll., Mungkin saja semua kelas kompleksitas ini runtuh ke satu kelas. Membuktikan bahwa salah satu dari kelas-kelas ini tidak setara akan menjadi terobosan besar dalam teori kompleksitas.
Apa ungkapan yang bisa digunakan untuk menggambarkan yang dicurigai dalam persamaan kelas kompleksitas?
P ⊆ NP ⊆ PP ⊆ PSPACE
P ⊆ NP ⊆ PP ⊆ PSPACE
Apa PRI
ungkapan NNO
yang PRR
bisa TAME
digunakan VBP
untuk PPO
menggambarkan VBT
yang PRR
dicurigai VBP
dalam PPO
persamaan NNO
kelas NNO
kompleksitas NNO
? PUN