Evaluasi sirkuit

Apakah diketahui jika masalah evaluasi rangkaian ada di ? Bagaimana dengan (uniform )? $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$ $\mathsf{NC^1}$

Kita tahu bahwa sirkuit dengan kedalaman dapat dievaluasi dengan sirkuit dengan kedalaman mana adalah konstanta universal. Ini berarti sirkuit kedalaman dapat dievaluasi dengan sirkuit kedalaman . Namun tidak mengandung fungsi yang akhirnya mendominasi semua fungsi di . $k$ $k+c$ $c$ $k\lg n + o(\lg n)$ $O(\lg n)$ $O(\lg n)$ $O(\lg n)$

Kita tahu bahwa masalah evaluasi rumus ada di . Setiap setara dengan rumus Boolean. Tidak bisakah kita menghitung representasi koneksi yang diperluas dari rumus Boolean yang setara dari dalam ? $\mathsf{ALogTime}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{ALogTime}$

The koneksi representasi diperpanjang dari sirkuit termasuk

jumlah gerbang di sirkuit,
jenis masing-masing gerbang, dan
untuk setiap gerbang dan setiap lintasan dalam DAG sirkuit, gerbang mencapai dari mengikuti lintasan . $g$ $\pi$ $g$ $\pi$

Jalur diberikan oleh urutan 0/1 di mana 0 mewakili bergerak ke induk kiri dan 1 mewakili bergerak ke induk kanan. Perhatikan bahwa jumlah lintasan adalah polinomial: panjang lintasan dibatasi oleh kedalaman rangkaian.

cc.complexity-theory reference-request circuit-complexity Kaveh
sumber

Sejauh yang saya tahu,

evaluasi tidak diketahui berada di

, dan menduga berada di luar

. Lihat "Pada teori aritmatika terbatas untuk

", E. Jerabek, Ann. Appl Murni Logika 2011 ( math.cas.cz/~jerabek/papers/vnc.pdf ).

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Iddo Tzameret

@ IddoTzameret Mungkin Anda harus membuat komentar Anda sebagai jawaban.

Dai Le

Apa yang Anda maksud dengan evaluasi sirkuit NC1? Apakah maksud Anda bahwa input yang diberikan kepada evaluator adalah sirkuit

yang kedalamannya dibatasi oleh

untuk beberapa konstanta tetap

, di mana

adalah jumlah input ke

C

$C$

c \log (n)

$c\log(n)$

c

$c$

n

$n$

C

$C$

Igor Shinkar

@ Igor, poin bagus. Saya harus berpikir dan mengklarifikasi.

Kaveh

@igor, saya pikir kita bisa berasumsi kedalaman dari rangkaian tersebut adalah

untuk beberapa sewenang-wenang tetapi tetap konstan

seperti yang sulit untuk

di bawah

pengurangan.

c \lg n

$c \lg n$

c \geq 1

$c\geq 1$

N C^{1}

$\mathsf{NC^1}$

A C^{0}

$\mathsf{AC^0}$

Kaveh

Sejauh yang saya tahu, evaluasi tidak diketahui berada di , dan menduga berada di luar . Lihat $\mathsf{NC^1}$ $\mathsf{NC^1}$ $\mathsf{NC^1}$

Emil Jerabek, " Tentang teori aritmatika terbatas untuk $\mathsf{NC^1}$ ", Ann. Appl Murni Logika 2011

Iddo Tzameret
sumber

Terima kasih iddo. Saya melihat kertas Emil dan itu sangat membantu. Dia menyatakan bahwa masalah tidak diketahui berada di

jika kita menggunakan representasi koneksi langsung tetapi adalah di

jika kita menggunakan representasi koneksi diperpanjang .

N C^{1}

$\mathsf{NC^1}$

N C^{1}

$\mathsf{NC^1}$

Kaveh

Dia melanjutkan dengan menyatakan bahwa masalah berikut adalah kesulitan inti dari komputasi evaluasi sirkuit

(dengan representasi dc): Diberikan grafik pada simpul dengan batas keluar-derajat, simpul , dan angka , tentukan apakah dapat dijangkau dari in paling banyak langkah.

N C^{1}

$\mathsf{NC^1}$ $G$ $n$ $x,y \in G$ $d \leq \log n$ $y$ $x$ $d$

Kaveh

@ Kaveh, Anda juga dapat melihat "Memperkuat Batas Bawah dengan Cara Reducibilitas Sendiri" oleh Allender dan Koucky (JACM 2010). Mereka juga menyatakan masalah evaluasi

tidak diketahui dalam

N C^{1}

$NC^1$

N C^{1}

$NC^1$

Iddo Tzameret

Sebenarnya kalimat itu adalah inspirasi untuk pertanyaan saya. Aku merasa itu harus di

jika kita menggunakan representasi koneksi diperpanjang dan negara-negara kertas Emil yang memang.

N C^{1}

$\mathsf{NC^1}$

Kaveh

Evaluasi sirkuit

Jawaban: