Apa yang salah dengan argumen

Berikut ini tidak diyakini benar:

$\mathsf{L} \subseteq \mathsf{L}-\mbox{uniform } \mathsf{NC}^1$

Bisakah Anda membantu saya melihat di mana argumennya rusak?

Masalah reachability yang diarahkan selesai untuk . Saya berpendapat bahwa ini adalah dalam seragam . $\mathsf{L}$ $\mathsf{L}$ $\mathsf{NC^1}$

Masalah reachability diarahkan lebih grafik konfigurasi deterministik log-ruang Turing Machine selesai untuk . $\mathsf{L}$

Masalah keterjangkauan yang diarahkan adalah dalam : $\mathsf{MSO}_2$

diberikan dan , biarkan mewakili bebas variabel untuk tepi di jalan. Kita perlu memverifikasi bahwa berisi lintasan terarah dari ke yang dapat dilakukan dengan memverifikasi bahwa derajat-dan-derajat (dalam ) dari setiap insiden titik pada tepi dalam adalah kecuali untuk dan yang memiliki in-degree, out-degree = dan masing-masing. $s$ $t$ $P$ $\mathsf{MSO}$ $P$ $s$ $t$ $P$ $P$ $1$ $s$ $t$ $0,1$ $1,0$

Setiap hutan adalah grafik lebar pohon . Secara khusus, grafik konfigurasi dari mesin Turing ruang log deterministik adalah struktur lebar pohon yang dibatasi. $1$

Dari versi Teorema Bodlaender dan Courcelle versi Elberfeld, Jakoby, dan Tantau :

rumus atas struktur pohon-lebar dibatasi dapat dievaluasi dalam log-ruang. $\mathsf{MSO}$

Buktinya berlangsung seperti ini: Untuk ukuran struktur diberikan , sebuah terikat di pohon-lebar struktur , dan rumus dengan kosakata , membangun (dalam ) membangun sirkuit . $n$ $w$ $\mathsf{MSO}$ $\varphi$ $\tau$ $\mathsf{L}$ $\#\mathsf{NC}^1$ $C$

Rangkaian diberi struktur ukuran dan pohon-lebar paling , menghitung jumlah "memuaskan" tugas dari pada . $C$ $M$ $n$ $w$ $\varphi$ $M$

(Histogram menabulasi jumlah penugasan ke variabel urutan kedua bebas di parameter pada ukuran set nilai yang diambil oleh variabel). $\varphi$

Saya pikir sirkuit hanya tergantung pada kosakata , batas lebar pohon , dan ukuran struktur . $C$ $\tau$ $d$ $n$

Buktinya berlanjut dengan mengevaluasi rangkaian di tetapi kita tidak membutuhkan bagian itu. $\#\mathsf{NC}^1 \subseteq \mathsf{L}$

Bagi kami cukup untuk mengamati bahwa dari Nondeterministic Computation $\mathsf{NC^1}$ oleh Caussinus-Mackenzie-Therien-Vollmer:

setiap sirkuit dapat diartikan sebagai penghitungan jumlah pohon bukti dari sirkuit . $\#\mathsf{NC}^1$ $\mathsf{NC}^1$

Dengan demikian sesuai sirkuit output jika dan hanya jika memenuhi struktur input rumus. $1$ $\mathsf{MSO}$

Dari penjelasan di atas, nampaknya log-space setidaknya dalam logspace-uniform $\mathsf{NC}^1$

cc.complexity-theory graph-algorithms complexity-classes descriptive-complexity finite-model-theory SamiD
sumber

Argumen keterjangkauan MSO Anda tidak sepenuhnya benar: argumen ini hanya akan berfungsi jika subgraf yang diinduksi oleh simpul

adalah jalur terarah, yang bukan merupakan kasus pada umumnya (contoh tandingan trivial adalah pasangan simetris dari tepi terarah). Cara yang benar untuk melakukan reachability dalam MSO adalah dengan menyatakan bahwa setiap set simpul yang berisi

dan ditutup di bawah relasi tepi juga termasuk

P

$P$

s

$s$

t

$t$

David Richerby

@SamiD Saya memberikan contoh-counter terkecil, yang kebetulan merupakan grafik simetris. Tapi 3-simpul graph dengan tepi diarahkan

bekerja sama dengan baik: jalan diarahkan unik dari

adalah

tapi set

tidak memuaskan rumus Anda karena, dalam subgraph yang diinduksi oleh

(yang merupakan keseluruhan grafik),

a \to b

$a\to b$

b \to c

$b\to c$

c \to a

$c\to a$

a

$a$

c

$c$

a b c

$abc$

{a, b, c}

$\{a,b,c\}$

{a, b, c}

$\{a,b,c\}$

a

$a$ tidak memiliki derajat nol dan

tidak memiliki derajat nol.

c

$c$

David Richerby

@ David Titik dibuat dengan baik - formulasi asli saya adalah kereta - Saya berharap satu ini ok: Saya menganggap satu set tepi bukannya simpul dan melihat tingkat simpul wrt ke tepi ini - mereka harus sama seperti sebelumnya. Terima kasih untuk contohnya.

SamiD

@ Kaveh Terima kasih atas perubahan - mereka membuat pertanyaan lebih mudah dibaca. Saya mengklarifikasi masalah yang Anda angkat - dalam pemahaman saya EJT membuat rangkaian aritmatika log-kedalaman di L dan kemudian masalahnya jatuh di L karena penahanan CMTV # NC1 \ subseteq L. Tapi kami berhenti pada titik sirkuit dibuat dan secara sintaksis mengubahnya menjadi sirkuit NC ^ 1. Konversi dll dapat dilakukan dengan mudah. Saya mengonversi NC ^ 1 / poli ke L-uniform NC ^ 1 juga karena lebih akurat.

SamiD

@ Kaveh: 1. Mengubah setiap

dari

-circuit

dan

akan membuat sirkuit

sehingga

menghitung jumlah pohon bukti

+

$+$

# N C^{1}

$\#NC^1$

C

$C$

\lor

$\vee$

*

$*$

\land

$\wedge$

N C^{1}

$NC^1$

C^{'}

$C'$

C

$C$

C^{'}

$C'$

SamiD

Apa yang salah dengan argumen

Jawaban: