Teorema hierarki dan / atau hierarki apa yang Anda ketahui?

Saat ini saya sedang menulis survei tentang teorema hierarki di TCS. Mencari makalah terkait saya perhatikan bahwa hierarki adalah konsep fundamendal tidak hanya dalam TCS dan matematika, tetapi dalam berbagai ilmu, dari teologi dan sosiologi ke biologi dan kimia. Melihat jumlah informasinya sangat besar, saya berharap dapat meminta bantuan oleh komunitas ini. Tentu saja, saya tidak ingin Anda melakukan pencarian bibliografi untuk saya, tetapi saya meminta dua jenis informasi:

1. Teorema hierarki dan hierarki yang merupakan hasil dari pekerjaan Anda atau karya rekan Anda atau orang lain yang Anda kenal dan Anda pikir itu tidak begitu terkenal. Ini bisa berupa teorema hierarki untuk model perhitungan yang tidak jelas yang Anda minati atau hierarki kelas tertentu, misalnya terkait dengan teori permainan.

2. Teorema hierarki dan hierarki yang Anda anggap benar-benar perlu dimasukkan dalam survei semacam ini. Ini mungkin sudah diketahui oleh saya, tetapi akan bermanfaat untuk melihat hierarki apa yang Anda anggap lebih penting dan mengapa. Ini bisa jadi dari jenis "Saya anggap $PH$ sangat penting karena tanpa itu kita tidak akan dapat melakukan penelitian semacam ini" atau "Meskipun tidak begitu dikenal, dalam TCS berbasis logika kita terus-menerus menggunakan hierarki ini dan saya anggap itu alat yang penting. " . Dan ya saya percaya bahwa orang-orang dari logika memiliki banyak hierarki untuk disebutkan, namun perlu diingat kita berbicara tentang hierarki masalah.

Saya akan menyimpan daftar yang diperbarui di sini:

• $DTIME$ Hierarchy
• $NTIME$ Hierarchy
• $SPACE$Hierarki S P A C E
• Hirarki Aritmetika (juga dikenal sebagai Kleene)
• Hierarki Hiperaritmetika
• Hirarki Analitik
• Hierarki Chomsky
• Grzegorczyk hierarki dan yang terkait: Hirarki Wainer (tumbuh cepat), Hirarki hardy
  (tumbuh lambat) dan hierarki Veblen
• Hirarki Ritchie
• Hirarki Axt (sebagaimana didefinisikan dalam Axt63 )

• Hierarki Lingkaran (didefinisikan dalam MR67 )

• $NC$ ($AC$ ,$ACC$ ) Hierarki

• Hirarki kedalaman, sebagaimana didefinisikan dalam Sipser83
• Hierarki Polinomial ( ) dan hierarki Meyer-Stockmeyer yang kurang disempurnakan (tidak ada dinstinction antara quantifiers)$PH$
• Hierarki Eksponensial ( )$ELEMENTARY$

• -Tingkat hierarki (teorema Ladner) $NP$

• (Arthur-Merlin) yang tidak terlalu kokoh$AM$

• The (Nondeterministic Fixed-Parameter) hirarki dan terkait Alternating W hirarki ( A W -hierarchy) dan W * -hierarchy (W dengan Parameter-Dependent Depth)$W$$AW$$W^{*}$
• Menghitung Hirarki
• Hierarki Fourier
• Hierarki Boolean (lebih dari ), juga sama dengan Heryarki Kueri (lebih dari N P )$NP$$NP$
• Hierarki untuk pengujian properti, seperti yang terlihat di GoldreichKNR09
• Hirarki dot-kedalaman bahasa reguler bebas bintang
• : Kelas-kelas yang dapat dipecahkan oleh program percabangan ukuran polinomial, dengan kondisi tambahan bahwa setiap bit input diuji paling banyak kali, membentuk hierarki untuk nilai$BP_{d}(P)$$d$
• Hirarki waktu untuk Kompleksitas Sirkuit
• Hirarki polinomial dalam kompleksitas komunikasi

Catatan: Jika Anda tidak ingin disebutkan secara eksklusif, silakan katakan demikian. Sebagai patokan, saya akan menyebutkan komunitas dan juga orang tertentu yang membawa informasi baru.

Hierarki Fourier sebagaimana didefinisikan dalam " Yaoyun Shi, Quantum dan pertukaran klasik ."

Dari kebun binatang kompleksitas :

$\mathsf{FH}_k$ adalah kelas masalah yang dapat dipecahkan oleh keluarga seragam dari sirkuit kuantum ukuran polinomial, dengantingkat$k$gerbang Hadamard dan semua gerbang lain yang mempertahankan dasar komputasi.

• $\mathsf{FH}_0 = \mathsf{P}$
• $\mathsf{FH}_1 = \mathsf{BPP}$
• $\mathsf{FH}_2$ mengandung faktorisasi karenaalgoritma estimasi fase Kitaev.

Ini adalah masalah terbuka untuk menunjukkan bahwa hirarki Fourier relatif terbatas ke oracle (yaitu, $\mathsf{FH}_k$ ketat terkandung dalam $\mathsf{FH}_{k+1}$ ).

- Di sepanjang garis "anti-hierarki", teorema kesenjangan Borodin mungkin layak disebutkan.

$f : {\mathbb N} \rightarrow {\mathbb N}$$f(n) = \Omega(n)$$g : {\mathbb N} \rightarrow {\mathbb N}$${\sf TIME}[g(n)] = {\sf TIME}[f(g(n))]$

$g$

- Ada juga penguatan menarik dari hierarki waktu yang biasa, seperti:

(ada masalah dalam waktu tidak dapat berhasil diselesaikan oleh mesin waktu kapan saja menggunakan bit nasihat, bahkan untuk pada panjang input yang tak terhingga banyaknya). Buktinya mudah: biarkan daftar mesin waktu yang mengambil bit saran sebagai input kedua. Tentukan yang membagi menjadi mana, menjalankan , dan menampilkan jawaban yang berlawanan. Kemudian .$n^k$$n^{k-1}$$n-\log n$$\{M_i\}$$n^{k-1}$$n-\log n$$M'(x)$$x$$x=yz$$|z|=\log |x|$$M_z(x,y)$$L(M') \notin i.o.{\sf -TIME}[n^{k-1}]/(n-\log n)$

- Kurangnya hierarki waktu yang diketahui dalam situasi tertentu harus dipertimbangkan (sebagai masalah terbuka). Misalnya, apakah ?${\sf BPTIME}[n] = {\sf BPP}$

Kompleksitas Zoo memberi Anda beberapa hierarki . Di antara mereka, Hierarki Penghitungan dan Hierarki Boolean belum dikutip.

[EDIT] Untuk membuat jawaban saya lebih informatif, definisi cepat tentang Hirarki Penghitungan.

• ${\sf C_0P} = {\sf P}$
• ${\sf C_1P} = {\sf PP}$
• ${\sf C_{k+1}P} = {\sf PP^{C_kP}}$

Kemudian, seperti untuk hierarki polinomial, didefinisikan sebagai .$\sf CH$$\bigcup_k {\sf C_kP}$

Hirarki penghitungan didefinisikan oleh Wagner [Wag86]. Tautan ke teori sirkuit ambang batas ditemukan oleh Allender & Wagner [AW93]. Baru-baru ini, Bürgisser [Bür09] juga menggunakan hierarki penghitungan untuk menghubungkan model Valiant dengan conjecture dari Shub and Smale. Secara khusus, ia membuktikan bahwa -conjecture menyiratkan batas bawah superpolynomial untuk permanen.$\tau$$\tau$

[Wag86] KW Wagner. Kompleksitas masalah kombinatorial dengan representasi input yang ringkas . Acta Mathematica 23 (3), 325-356, 1986.
[AW93] E. Allender & KW Wagner. Hitung hierarki: waktu polinom dan sirkuit kedalaman konstan . Tren saat ini dalam Ilmu Komputer , 469-483, 1993.
[Bür09] P. Bürgisser. Pada mendefinisikan bilangan bulat dan membuktikan rangkaian aritmatika batas bawah . Kompleksitas Komputasi 18 (1), 81-103, 2009.

Goldreich et. Al. memiliki teorema hierarki untuk pengujian properti:

• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg: Teorema Hierarki untuk Pengujian Properti. Pengujian Properti , Catatan Kuliah dalam Ilmu Komputer, Vol. 6390, hlm. 289-294, Springer, 2010.

Juga di ECCC .

Sipser menunjukkan hierarki kedalaman dalam , yaitu, bahwa kedalaman sirkuit ukuran poli lebih kuat daripada sirkuit kedalaman ukuran poli:$AC^0$$d+1$$d$

Sipser, M. Borel set dan kompleksitas sirkuit . STOC 1983.

Dieter van Melkebeek dan rekan penulis memiliki hierarki waktu dan ruang untuk model semantik dengan saran, termasuk pengacakan.

• Dieter van Melkebeek, Konstantin Pervyshev: Hierarki Waktu Generik dengan One Bit of Advice . Kompleksitas Komputasi 16 (2): 139-179 (2007)
• Jeff Kinne, Dieter van Melkebeek: Hasil Hirarki Ruang untuk Acak dan Model Semantik lainnya . Kompleksitas Komputasi 19 (3): 423-475 (2010)

Berikut adalah lebih banyak hierarki untuk kelas semantik dengan saran. Khususnya untuk ZPTIME dan RTIME.

Lance Fortnow, Rahul Santhanam, Luca Trevisan. Hierarki untuk Klasifikasi Semantik . Dalam STOC'05.

Ada hierarki Zheng-Weihrauch untuk bilangan real

X. Zheng dan K. Weihrauch. Hierarki aritmatika bilangan real . Matematika Quarterly Quarterly.Vol. 47 (2001), no.1 51 - 65.

Ada kelas , didefinisikan dalam makalah tahun 1975 oleh L. Adelman dan K. Manders, yang merupakan analog diophantine dari kelas . Bahasa terkandung dalam jika ada polinom sehingga Apakah sama dengan adalah masalah terbuka. Kesetaraan ini akan menunjukkan hubungan antara teori bilangan dan ilmu komputer.$\mathsf{D}$$\mathsf{NP}$$L$$\mathsf{D}$$P$

Ada analog diophantine dari hierarki polinomial, yang disebut "hierarki diophantine". Hirarki polinomial dan diofantin saling terkait:

Hirarki ketat lainnya: program percabangan yang hanya menguji setiap bit dalam jumlah terbatas. Semakin banyak tes diizinkan, semakin besar kelas program percabangan. Biasanya program percabangan juga dibatasi untuk ukuran polinomial. BP _d (P) adalah kelas program percabangan ukuran polinomial yang dapat menguji setiap bit hingga kali.$d$

L / poli adalah penyatuan BP _d (P) di atas semua d , sedangkan BP _d-1 (P) BP _d (P) untuk setiap d .$\subsetneq$

Dalam teori kompleksitas parameterisasi ada beberapa hierarki meskipun hanya hirarki yang telah disebutkan yang sering muncul dalam publikasi. Lainnya adalah:$\mathsf{W}$

• $\mathsf{A}$ -hierarchy
• $\mathsf{AW}$ -hierarchy
• $\mathsf{EW}$ -hierarchy
• $\mathsf{LOG}$ -hierarchy
• $\mathsf{M}$ -hierarchy
• $\mathsf{S}$ -hierarchy
• $\mathsf{W^∗}$ -hierarchy
• $\mathsf{W^{func}}$ -hierarchy

Mereka semua dijelaskan dalam teori kompleksitas Parameterized, Flum and Grohe, Birkhäuser, 2006 .

Tidak yakin apakah ini cocok dengan kriteria Anda, tetapi ada hirarki dot-depth dari bahasa reguler bebas bintang.

Hirarki untuk ukuran sirkuit, lihat pertanyaan sebelumnya .

Teori bahasa reguler pohon tak terbatas memunculkan beberapa hierarki, yang saat ini dipelajari, dengan banyak pertanyaan yang masih terbuka.

Ketika menggunakan automata pada pohon tak terbatas, kondisi paritas (atau kondisi Mostowski) menjadi perhatian khusus, karena paritas automati non-deterministik dapat mengekspresikan semua bahasa reguler pohon tak terbatas, dan struktur kondisi penerimaan lebih sederhana daripada yang lain seperti Rabin atau Müller .

Setiap robot paritas memiliki peringkat mana dan , menggambarkan struktur kondisi penerimaan. Oleh karena itu, jika bahasa dikenali oleh otomat (det / ND / alt) dari peringkat kita mengatakan bahwa milik tingkat dari (masing-masing):i ∈ { 0 , 1 } i ≤ j L [ i , j ] L [ i , j $[i,j]$$i\in\{0,1\}$$i\leq j$$L$$[i,j]$$L$$[i,j]$

• deterministik hierarki Mostowski (tidak semua bahasa reguler)
• hierarki Mostowski nondeterministic
• bergantian hierarki Mostowski

Level dari hierarki bolak-balik (yaitu adalah Büchi dan co-Büchi dapat didefinisikan) berhubungan dengan level lemah dan ditandai oleh automata bolak-balik yang lemah, yang menyebabkan mereka naik ke hierarki:$\Sigma_2\cap \Pi_2$$L$

• hierarki indeks lemah (tidak semua bahasa biasa)

Untuk semua hierarki ini (kecuali yang deterministik), kepesertaan keanggotaan dalam level untuk bahasa reguler yang diberikan adalah masalah terbuka. Tautan antara hierarki ini dan klasifikasi topologi (juga disebut hierarki Wadge dan hierarki Borel) juga menimbulkan beberapa masalah terbuka. Misalnya diduga bahwa hierarki indeks yang lemah dan hirarki Borel bertepatan. Semua hierarki ini dikenal ketat, dan beberapa kasus khusus dalam menentukan level (terutama level rendah, atau dengan input deterministic automaton) telah diselesaikan baru-baru ini.$L$

Ada hierarki dalam kompleksitas bukti proposisional yang mirip dengan kompleksitas sirkuit. Misalnya sistem atap proposisional mirip dengan , sistem bukti C-Frege untuk mirip dengan kelas kompleksitas sirkuit , dan seterusnya.P H C ⊂ P$G_i$$\mathsf{PH}$$C \subset \mathsf{P}$$C$

Ada juga hierarki dalam aritmatika terbatas, misalnya , dll.$\mathsf{S^i_j}$

Berikut adalah hierarki baru untuk bahasa bebas konteks oleh Tomoyuki Yamakami.

Dia memperkenalkan mekanisme oracle dalam automata pushdown nondeterministic dan konsep Turing dan banyak-satu reducibilities. Kemudian hierarki baru dibangun untuk bahasa bebas konteks (CFL) yang mirip dengan hierarki polinomial. Misalnya, , , dll. Bagian yang menarik dari semua ini adalah bahwa keruntuhan dalam hierarki CFL terjadi jika dan hanya jika hierarki polinomial runtuh.C F L C F $CFL$$CFL^{CFL}$

Menguraikan salah satu poin utama yang disebutkan oleh OP (GoldreichKNR09): ada beberapa teorema hierarki dalam pengujian properti dan bukti kedekatan, terkait dengan kompleksitas kueri, adaptifitas, atau kemampuan uji sehubungan dengan jumlah putaran (untuk bukti dari kedekatan). Lihat, misalnya,

• Teorema Hierarki untuk Pengujian Properti , Oded Goldreich, Michael KrivelevichIlan Newman, dan Eyal Rozenberg, 2012. https://link.springer.com/article/10.1007/s00037-011-0022-4 [disebutkan oleh OP]
• Teorema Hirarki untuk Bukti Interaktif Kedekatan , Tom Gur dan Ron Rothblum, 2017. http://drops.dagstuhl.de/opus/volltexte/2017/8153/
• Teorema Hierarki untuk Pengujian Properti dalam Kompleksitas Kueri yang Tidak Disadari Ukuran , Oded Goldreich, 2018. https://eccc.weizmann.ac.il/report/2018/098/
• Teorema hierarki adaptifitas untuk pengujian properti , Clément Canonne dan Tom Gur, 2018. https://link.springer.com/article/10.1007%2Fs00037-018-0168-4

Dari pertanyaan ini di cs.stackexchange , saya menjadi sadar akan hierarki genus bahasa reguler . Pada dasarnya, Anda dapat mengkarakterisasi bahasa biasa berdasarkan pada permukaan genus minimum di mana grafik DFA mereka dapat disematkan. Hal ini ditunjukkan dalam [1] bahwa ada bahasa dengan genus besar yang sewenang-wenang dan bahwa hierarki ini sesuai.

1. Bonfante, Guillaume, dan Florian Deloup. " Genus bahasa reguler. " Struktur Matematika dalam Ilmu Komputer 28.1 (2018): 14-44.

Menghitung Hirarki Polinomial, #PH singkatnya. Level pertama adalah #P lalu #NP ... dll.

$^{cc}$

$D_{p}$

$NC^{k}$$AC^{k}$$P$$PSPACE$$P$$UP$

Terkait untuk studi lebih lanjut tentang konektifitas Boolean, dan Graph Isomorphism adalah Hierarki Rendah, dan Tinggi , juga referensi wikipedia .

Lebih lanjut tentang sisi yang tidak jelas: teorema heirarki orde kedua saya untuk logika titik tetap dalam teori model hingga. Lihat Teorema Hirarki Lain .