Yang

Gambar Dunia yang terkenal dari Neil Immerman adalah sebagai berikut (klik untuk memperbesar):

Kelasnya "Benar-benar layak" tidak termasuk kelas lain; pertanyaan saya adalah:

Apa masalah AC ⁰ yang dianggap tidak taktis, dan mengapa?

cc.complexity-theory circuit-complexity Michaël Cadilhac
sumber

Mungkin masalah yang membutuhkan rangkaian kedalaman 10 ^ {10 ^ 100}?

Tsuyoshi Ito

@Ross: Saya tidak berpikir begitu karena dia tidak menyebutkan "dunia nyata" dan dia bertanya "mengapa"; Saya pikir komentar saya sebelumnya menjawab setidaknya bagian “mengapa”. Namun, diakui saya tidak memiliki contoh masalah "alami" yang ada di AC0 dan membutuhkan rangkaian kedalaman 10 ^ {10 ^ 100}.

Tsuyoshi Ito

Ada banyak masalah dunia nyata yang menarik yang dapat dipecahkan dalam waktu dan ruang konstan (dalam hampir semua model perhitungan), namun sekarang orang sudah tahu bagaimana menyelesaikannya dalam praktik. Contoh ekstrem menghitung konstanta tertentu; kita bisa membuat kode jawaban yang benar (mis. 0 atau 1), tetapi kita belum tahu jawabannya.

Jukka Suomela

Jukka: itu adalah contoh masalah. Persamaan diophantine (seperti Fermat) tidak dapat dipastikan sebagai sebuah kelas, bahkan jika instance individual yang telah kami putuskan benar-benar memiliki sirkuit kedalaman konstan.

András Salamon

@ András: Jika Anda lebih suka masalah keputusan dengan banyak contoh "ya" dan "tidak" yang tak terhingga: Misalkan

terdiri dari semua angka genap dan

, di mana

jika pemain putih memiliki strategi kemenangan dalam catur dan sebaliknya

. Secara sepele, ada keluarga sirkuit yang sangat sederhana yang memutuskan

, tetapi saya masih mengklaim bahwa itu "tidak taktis". Bukan karena sirkuit akan sangat besar, tetapi karena mendesain sirkuit akan menjadi upaya komputasi yang sangat besar ... Berselingkuh? -)

L

$L$

x

$x$

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Jukka Suomela

Jawaban:

Jika Anda menginginkan contoh fungsi AC ⁰ yang membutuhkan kedalaman , dan tidak dapat dihitung oleh sirkuit AC ⁰ kedalaman , maka coba fungsi Sipser . Superscript adalah kedalaman yang dibutuhkan untuk sirkuit AC ⁰ ukuran polinomial . Dengan kedalaman , rangkaian akan membutuhkan banyak gerbang secara eksponensial. $d$ $d-1$ $S^{d,n}$ $d$ $d-1$

Jadi menghitung untuk tidak akan "benar-benar layak." $S^{d,n}$ $d = 10^{10^{100}}$

EDIT: Pertanyaan Anda juga bertanya mengapa ini tidak layak. Saya kira alasannya adalah bahwa lebih dari jumlah atom di alam semesta yang terlihat. $10^{10^{100}}$

Robin Kothari
sumber

Bagus, terima kasih! Mungkin Anda dapat menambahkan definisi informal dari fungsi Sipser? Saya tidak tahu tentang nama itu.

Michaël Cadilhac

@ Michaël: Sayangnya saya tidak memiliki definisi intuitif yang bagus untuk fungsi Sipser. Idenya adalah untuk membuat fungsi d quantifier sehingga tidak ada kedalaman d-1 yang dapat menghitungnya. Jadi kami ingin penjumlah d untuk mengukur lebih banyak variabel. Ada artikel yang bagus dari Iddo Tzameret, berjudul "Pemisahan Håstad tentang Sirkuit Kedalaman-Konstan Menggunakan Fungsi Sipser" ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ) yang mendefinisikan fungsi secara formal di halaman 7.

Robin Kothari

Semua hierarki ini sengaja kuat di bawah perubahan polinomial ukuran input. Dengan demikian, setiap kelas di dalamnya dapat berisi fungsi-fungsi yang kompleksitasnya disebut n ^ {1000000000} yang secara teori "layak" tetapi tentu saja tidak demikian. Namun ini kemungkinan besar akan menjadi masalah yang sangat artifisial. Khususnya dengan argumen penghitungan terdapat keluarga rumus DNF (= AC ^ 0 kedalaman 2 sirkuit) ukuran n ^ 1000000 yang tidak dapat dihitung oleh algoritma mana pun yang waktu operasinya kurang dari n ^ 999999. (Dalam pengaturan seragam kami mengharapkan sesuatu yang serupa tetapi tidak dapat membuktikannya.)

Noam
sumber

Masalah penghentian ketika input diwakili di unary adalah di AC ^ 0 dan pada kenyataannya cukup tidak layak. Saya tidak yakin ini yang Anda maksud, tapi bisa jadi itu yang dimaksud Immerman.

Elad
sumber

Saya kira kelas-kelas dalam diagram didefinisikan dengan pengertian keseragaman? Kalau tidak, arah ke atas tidak akan mewakili pengungkungan, karena P tidak mengandung AC ^ 0 yang tidak seragam.

Robin Kothari

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Poin diambil dengan baik. Sebagai alternatif, mengikuti Erdos, orang bisa menyarankan masalah bahwa untuk input apa pun, mengeluarkan nomor Ramsey untuk enam merah dan enam biru.

Elad