Kelas besar yang berisi LOGSPACE yang inklusi ketatnya tidak diketahui

Halaman wikipedia di PSPACE menyebutkan bahwa inklusi tidak dikenal ketat (sayangnya tanpa referensi). $NL\subset PH$

T1: Bagaimana dengan dan - apakah ini dikenal ketat? $L\subset PH$ $L\subset P^{\#P}$

T2: Jika tidak, adakah kelas yang mapan yang berisi dan yang tidak diketahui jika inklusi ketat? $C$ $P^{\#P}$ $L\subset C$

T3: Apakah inklusi seperti itu dibahas dalam literatur?

cc.complexity-theory complexity-classes logspace Łukasz Grabowski
sumber

Saya kira untuk Q2 maksud Anda benar-benar terkandung dalam PSPACE?

Sasho Nikolov

AFAIK, satu-satunya pemisahan tahu untuk adalah teorema hierarki ruang. Saya tidak berpikir itu diketahui jika ada kelas yang disebutkan dalam pertanyaan dapat mensimulasikan ruang super-logaritmik sehingga mereka juga tidak dikenal ketat. (Tidak mengetahui pemisahan bukanlah hasil sehingga mungkin alasannya tidak ada referensi.)

L

$\mathsf{L}$

Kaveh

Bahkan untuk kelas yang lebih kecil dari , seperti uniform , inklusi Q1 tidak dikenal ketat. Saya pikir, mengingat keadaan pengetahuan saat ini, pada dasarnya setiap kelas antara dan benar-benar terkandung dalam adalah jawaban positif untuk Q2.

L

$\mathsf{L}$

{N C}^{1}

$\mathsf{NC}^1$

C

$C$

P^{# P}

$\mathsf{P}^{\mathsf{\# P}}$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

Judul pertanyaan Anda mengatakan "Kelas terbesar". Bukankah maksud Anda "kelas terkecil"?

Shaull

Bahkan tidak diketahui apakah secara ketat termasuk dalam PH. berisi TC ^ 0 oleh argumen hierarki, tetapi seperti yang sudah disebutkan oleh Joshua Grochow, ini tidak dikenal untuk NC ^ 1. Untuk Q2, Anda dapat mengambil CH.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Emil Jeřábek 3.0

Jawaban:

Ini pertanyaan favorit saya.

Fortnow menunjukkan, dalam makalahnya "Time-Space Tradeoffs for Satisfiability" , bahwa terkandung dalam , di mana adalah fungsi yang tidak terikat. Artinya, ruang log nondeterministic benar terkandung dalam waktu polinomial bergantian dengan alternatif. $NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

Menunjukkan bahwa tidak dalam untuk konstanta tetap akan menyiratkan bahwa . (Untuk melihat ini, pertimbangkan alat kontrasepsi.) $NL$ $\Sigma_k P$ $k$ $NL \neq NP$

Terbuka apakah . Terakhir kali saya serius berusaha membuktikan ini, itu menghasilkan makalah "Time-Space Tradeoffs untuk Menghitung Solusi NP Modulo Integers" . Saya mencoba untuk menemukan beberapa simulasi setiap bahasa di logspace yang akan mengambil waktu untuk beberapa tetap ketika salah satu memiliki akses ke oracle untuk menghitung memuaskan tugas untuk formula yang diberikan. (Ini akan menyiratkan .) Pendekatan saya tidak berhasil, tetapi saya akhirnya menggunakan pendekatan yang sama untuk membuktikan batas waktu ruang yang lebih rendah untuk memecahkan dan hasil terkait lainnya. $NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ $Mod_6 SAT$

Uniform- terkandung dengan benar dalam . Buktinya ada di Allender, "The Permanent Membutuhkan Sirkuit Ambang Seragam Besar" . Setiap perbaikan pada pemisahan ini terbuka. (Misalnya, membuktikan seragam- terbuka, dan membuktikan seragam- juga terbuka.) $TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Ryan Williams
sumber

Keren! (BTW, mengenai kalimat non-parenthetical terakhir Anda: Koiran dan Perifel arxiv.org/abs/0902.1866 meningkatkan hasil Allender ke seragam poli-ukuran sirkuit dengan kedalaman - tapi saya rasa ada perbaikan pada itu terbuka.)

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Joshua Grochow

Ya, saya tahu tentang itu juga, dan referensi lain juga. Tetapi saya tetap pada ringkasan jawaban yang tidak akan memakan waktu lebih dari 10 menit untuk menulis.

Ryan Williams