Teori Kompleksitas Struktural
Kita tahu bahwa L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} dan L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , di mana L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Kita juga tahu bahwa...
Banyak hasil penting dalam teori kompleksitas komputasi, dan khususnya teori kompleksitas "struktural", memiliki sifat menarik yang dapat dipahami secara mendasar mengikuti (seperti yang saya lihat ...) dari hasil algoritmik yang memberikan algoritma atau protokol komunikasi yang efisien untuk...
Penggoda Karena masalahnya gondrong di sini adalah kasus khusus yang menangkap esensinya. Masalah: Misalkan A menjadi algoritme detrministik untuk 3-SAT. Apakah masalah sepenuhnya mensimulasikan algoritma A (pada setiap contoh masalah). P-Space keras? (Lebih tepatnya, apakah ada alasan untuk...
Latar Belakang Hal ini diketahui bahwa ada sebuah ramalan AAA seperti itu, PSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A . Bahkan diketahui bahwa pemisahan relatif terhadap oracle acak. Secara informal, seseorang mungkin menafsirkan ini berarti bahwa ada banyak nubuat yang PSPACEPSPACEPSPACE dan...
Hal ini tidak diketahui apakah grafik isomorfisma (GI) untuk grafik sangat teratur (SRGs) dalam P . Apakah ada petunjuk bahwa itu mungkin atau mungkin tidak GI -Lengkap? Adakah konsekuensi kuat dalam kasus-kasus seperti itu? (Mirip dengan keyakinan bahwa GI mungkin tidak
Dalam karya terbaru kami, kami menyelesaikan masalah komputasi yang muncul dalam konteks kombinatorial, dengan asumsi bahwa , di mana ⊕EXP≠⊕EXPEXP≠⊕EXP\mathsf{EXP} \ne \mathsf{\oplus{}EXP} adalah versi E X P dari ⊕⊕EXP⊕EXP\mathsf{\oplus{}EXP}EXPEXP\mathsf{EXP} . Satu-satunya kertas di...
Dua makalah yang akan saya sertakan adalah: D. Kozen, "Pengindeksan kelas subkursif" , STOC, 1978. R. Ladner, "Tentang Struktur Pengurangan Waktu Polinomial" , JACM,
Untuk setiap bahasa lengkap NP yang sewenang-wenang, adakah selalu superset polytime yang komplemennya juga tidak terbatas? Versi sepele yang tidak menetapkan superset memiliki pelengkap tak terbatas telah diminta di /cs//q/50123/42961 Untuk keperluan pertanyaan ini, Anda dapat mengasumsikan...
Apakah menyiratkan E = N E ?E X P = N E X PEXP=NEXP\mathsf{EXP}=\mathsf{NEXP}E = N
Biarkan menjadi kelas bahasa yang diputuskan dengan bergantian mesin Turing yang berhenti dalam waktu menggunakan spasi . Biarkan menjadi kelas bahasa yang diputuskan dengan bergantian mesin Turing yang berhenti menggunakan bergantian dan spasi .ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n),...
The isomorfisma Dugaan dari Berman dan Hartmanis menyatakan bahwa semua -Lengkap set waktu polinomial isomorfik satu sama lain. Ini berarti bahwa masalah lengkap dapat direduksi secara efisien satu sama lain melalui waktu polinomial yang dapat dihitung dan biopsi yang tidak dapat dibalik. Dugaan...