Pemisahan kelas kompleksitas tanpa teorema hierarki

16

Teorema hierarki adalah alat mendasar. Sejumlah besar dari mereka dikumpulkan dalam pertanyaan sebelumnya (lihat Apa hierarki dan / atau teorema hierarki yang Anda ketahui? ). Beberapa pemisahan kelas kompleksitas langsung mengikuti dari teorema hierarki. Contoh pemisahan yang sangat dikenal: LPSPACE , PEXP , NPNEXP , PSPACEEXPSPACE.

Namun, tidak setiap pemisahan mengikuti dari teorema hierarki. Sebuah contoh yang sangat sederhana adalah . Meskipun kita tidak tahu apakah salah satu dari mereka mengandung yang lain, mereka masih berbeda, karena N P ditutup sehubungan dengan transformasi polinomial, sementara E tidak.NPENPE

Manakah beberapa pemisahan kelas kompleksitas yang lebih dalam, tanpa syarat, dan tanpa relativiasi untuk kelas seragam yang tidak secara langsung mengikuti dari beberapa teorema hierarki?

Andras Farago
sumber
2
Saya pikir itu agak tidak biasa untuk menyebut pemisahan. Ketidaksetaraan mereka juga karena alasan sepele dan tidak memberi tahu kami sesuatu yang menarik. AFAIK semua pemisahan kelas kompleksitas yang menarik untuk kelas kompleksitas besar bergantung pada teorema hierarki (dan pada gilirannya diagonalisasi) di beberapa titik. NPE
Kaveh
Benar, memang tidak biasa untuk menyebut pemisahan, karena berlaku untuk alasan sepele. Saya hanya membawanya untuk menunjukkan contoh sederhana di mana tidak ada teorema hierarki yang diperlukan. NPE
Andras Farago
3
Err, bukti NP! = E memang bergantung pada teorema hierarki! Cara kerjanya adalah Anda pertama kali mengasumsikan NP = E, kemudian menggunakan properti penutupan NP untuk menyimpulkan bahwa E = EXP, sehingga melanggar Teorema Hierarki Waktu.
Scott Aaronson
Terima kasih, Scott, kamu benar sekali. bukan contoh yang tepat. Saya memposting yang lebih baik di antara jawaban. NPE
Andras Farago
Jadi, bahkan ketidaksetaraan seperti mengandalkan diagonalisasi: tapi E E X P . Bagaimanapun, bagus dan tidak sepele. ENPAC0NPAC0EEXPEEXP
Kaveh

Jawaban:

13

Saya ingin ditampilkan salah, tetapi saya tidak berpikir saat ini ada batas bawah seragam yang pada akhirnya tidak didasarkan pada salah satu teorema hierarki. Pemahaman kami saat ini tentang bagaimana memanfaatkan keseragaman benar-benar sangat terbatas dalam pengertian itu.

Di sisi lain, ada banyak batas bawah seragam yang tidak mengikuti langsung dari teorema hierarki, tetapi menggunakan teorema hierarki dalam kombinasi dengan trik, teknik, dan hasil pintar lainnya, misalnya:

  • [Hopcroft-Paul-Valiant]. Mereka membuktikan bahwa D T I M E ( n ) D S P A C E ( n / log n ) (bagian non-diagonisasi dari buktinya), dan kemudian menggunakan fakta bahwa C S L = N S P A C E (CSLDTIME(n)DTIME(n)DSPACE(n/logn)CSL=NSPACE(n)dalam kombinasi dengan hierarki ruang. Hasilnya + hirarki ruang juga menyiratkan .DSPACE(n)DTIME(n)
  • Pertukaran ruang-waktu untuk Kepuasan (lihat, misalnya perkenalan Buss-Williams dan referensi di dalamnya)
  • [Paul-Pippinger-Szemeredi-Trotter]. Menggunakan simulasi nontrivial dari setiap mesin super-linear-time deterministik oleh mesin empat-alternasi yang lebih cepat, dalam kombinasi dengan hirarki waktu deterministik.DTIME(n)NTIME(n)
  • Batas bawah seragam yang seragam pada [ Allender , Allender-Gore , Koiran-Perifel ] permanen
  • [Williams] (meskipun secara teknis ini adalah batas bawah yang tidak seragam, ia menggunakan banyak ide cerdas dalam kombinasi dengan hierarki waktu nondeterministik)NEXPACC0
Joshua Grochow
sumber
4

Apakah pemisahan oleh Smolensky adalah sesuatu yang Anda cari?AC0TC0

Arne
sumber
1
Terima kasih, yang merupakan hasil bagus, tapi saya mencari pemisahan kelas, bukan kelas sirkuit. uniform
Andras Farago
2
@AndresFarago: Seragam AC ^ 0 juga termasuk dalam seragam TC ^ 0.
Emil Jeřábek mendukung Monica
2
@ EmilJeřábek: Apakah ada bukti bahwa seragam terkandung dalam seragam T C 0 yang tidak juga sudah membuktikan pernyataan tidak seragam? (Jika tidak, maka akan terlihat contoh Anda jatuh di bawah prinsip umum bahwa batas bawah tidak seragam lebih kuat daripada batas bawah seragam, dan saya pikir OQ mencoba untuk menghindari jawaban seperti itu ...)AC0TC0
Joshua Grochow
2
Saya pikir ketidakseragaman dalam bukti adalah sekunder dari fakta bahwa ini adalah kelas yang agak kecil di mana kita memiliki beberapa pemahaman kombinatorial / aljabar yang bagus tentang mereka. Yaitu kita memahaminya dengan cukup baik untuk langsung membangun objek yang tidak ada di dalamnya. Di mana untuk kelas yang lebih besar tidak ada pemahaman seperti itu dan oleh karena itu satu-satunya metode yang kita tahu adalah melakukan diagonalisasi terhadap seluruh kelas untuk membangun objek seperti itu.
Kaveh
2

Contoh nontrivial lain datang dari bidang kompleksitas kasus rata-rata. Rainer Schuler membuktikan sifat menarik dari kelas dia sebut , lihat [1].PPcomp

adalah kelas bahasa yang diterima dalam waktu polinomial pada μ -average untuksetiapkali dihitung jumlahnya banyak (P-dihitung) distribusi μ . Tentu, P P P - c o m p memegang, karena adanya algoritma polytime deterministik menyiratkan bahwa itu tetap efisien rata-rata, tidak peduli apa distribusi input. Namun, kondisi berjalan dalam waktu polinomial rata-rata untuksetiapdistribusi input P-computable muncul cukup kuat untuk mencurigai P P -PPcompμμPPPcompPPcomp=P

LPPcompE

EPPPcomp()
PPcompP. While the latter also uses the fact EP, which follows from the Time Hierarchy Theorem, the novel part (*) builds on different tools: beyond diagonalization, it employs resource bounded measure and Kolmogorov complexity.

Reference:

[1] R. Schuler, "Penutupan tabel kebenaran dan penutupan Turing dari waktu polinomial rata-rata memiliki ukuran yang berbeda dalam EXP," CCC 1996, pdf

Andras Farago
sumber