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 yang tidak akan menjadi terobosan besar dalam teori kompleksitas?
Membuktikan bahwa salah satu dari kelas-kelas ini tidak setara
Membuktikan bahwa salah satu dari kelas-kelas ini tidak setara
Apa PRI
yang PRR
tidak NEG
akan TAME
menjadi VBI
terobosan NNO
besar ADJ
dalam PPO
teori NNO
kompleksitas NNO
? PUN