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 bukti antara dan di antara kelas kompleksitas yang akan menandakan DAS teoritis untuk teori kompleksitas?
Membuktikan bahwa salah satu dari kelas-kelas ini tidak setara
Membuktikan bahwa salah satu dari kelas-kelas ini tidak setara
Apa PRI
bukti NNO
antara PPO
dan CCN
di PPO
antara PPO
kelas NNO
kompleksitas NNO
yang PRR
akan TAME
menandakan VBT
DAS NNO
teoritis ADJ
untuk PPO
teori NNO
kompleksitas NNO
? PUN