Apakah L memiliki definisi dalam hal rangkaian?

Banyak kelas kompleksitas yang didefinisikan dengan mesin Turing memiliki definisi dalam hal sirkuit yang seragam. Sebagai contoh, P juga dapat didefinisikan menggunakan sirkuit ukuran polinom yang seragam, dan juga BPP, NP, BQP, dll. Dapat didefinisikan dengan sirkuit yang seragam.

Jadi, apakah ada definisi L berbasis sirkuit?

Gagasan yang jelas adalah untuk memungkinkan sirkuit ukuran polinom dengan batasan kedalaman, tetapi ini ternyata menentukan hierarki NC.

Saya sudah memikirkan pertanyaan ini sejak lama, tetapi tidak menemukan jawaban. Jika saya ingat dengan benar, motivasi saya adalah untuk memahami seperti apa analog kuantum L.

cc.complexity-theory complexity-classes circuit-complexity Robin Kothari
sumber

Apakah sirkuit berukuran logaritmik mengandung

L

$L$

Mohammad Al-Turkistany

@Turkistany: Tidak, saya rasa tidak, karena sirkuit ukuran log paling banyak dapat memiliki kedalaman log, dan dengan demikian terkandung dalam NC_1, yang didefinisikan sebagai kedalaman log, sirkuit ukuran poli. NC_1 terkandung dalam L, dan tidak diketahui sama dengan L.

Robin Kothari

Jawaban:

$L = SC^1$ $SC^1$ $O(\log n)$

$NL$

Kristoffer Arnsfelt Hansen
sumber

Kita perlu sirkuitnya seragam, kan?

Hsien-Chih Chang 張顯之

Benar, mereka harus seragam.

Kristoffer Arnsfelt Hansen

S C^{1}

$SC^1$ didefinisikan menggunakan Mesin Turing sebagai

D T i m e S p a c e (p o l y, l o g)

$DTimeSpace(poly,log)$ jadi sudah seragam.

Kaveh

@KristofferArnsfeltHansen: Sudah lama sejak Anda menjawab ini, tetapi apakah Anda memiliki referensi di mana kesetaraan antara rangkaian dan definisi L dari TM terbukti?

Robin Kothari

@Robin, aku tidak bisa memikirkannya, sebenarnya. Mungkin Vinay tahu?

Kristoffer Arnsfelt Hansen

Lihatlah makalah McKenzie, Reinhardt, Vinay ini . Kami menggunakan gerbang pilih-multipleks untuk mengkarakterisasi kelas-kelas di antaranya $NC^1$ dan $LOGCFL$ , termasuk $L$ , $LOGDCFL$ dll. Misalnya, $L = MWidth, Size(log,poly).$

$NL$ memiliki karakterisasi berbasis sirkuit alami menggunakan Skew Circuits. Ini hanyalah representasi rangkaian dari program percabangan yang mewakili $NL$ . Sirkuit miring disebabkan oleh Venkateswaran.

V Vinay
sumber