Sudah diketahui sejak awal 70-an bahwa dan tidak sama (karena tidak ditutup di bawah polinomial-waktu banyak -satu pengurangan, berbeda dengan ). Sejauh yang saya tahu, masih terbuka apakah satu kelas adalah himpunan bagian dari yang lain, atau mereka tidak dapat dibandingkan, yang berarti bahwa dan keduanya kosong.
Pertanyaan: Manakah masalah (lebih disukai alami) yang merupakan kandidat untuk berada dalam atau , dengan asumsi set masing-masing tidak kosong? Saya khususnya tertarik pada masalah alami dalam yang kemungkinan membutuhkan waktu eksponensial dengan eksponen superlinear , yaitu, mereka berada dalam .
sumber