Gagasan yang lebih kuat tentang penyeragaman?

16

Satu celah yang saya selalu sadar bahwa saya tidak benar-benar mengerti adalah antara kompleksitas komputasi tidak seragam dan seragam di mana kompleksitas sirkuit mewakili versi tidak seragam dan mesin Turing adalah hal-hal yang seragam. Saya kira "seragam" adalah cara untuk menahan kelas algoritma, misalnya tidak mengizinkan rangkaian yang sama sekali berbeda untuk masalah dengan n variabel dibandingkan dengan masalah n +1 variabel.

Pertanyaan saya adalah: 1) Apakah ada deskripsi keseragaman hanya dalam hal rangkaian, dan 2) Apakah mungkin untuk datang dengan bentuk yang lebih kuat dari keseragaman dan dengan demikian memberikan gagasan lebih terbatas tentang apa yang efektif (atau ditahan) algoritma di P apa?

Klarifikasi terlambat: niat saya dalam pertanyaan 2 adalah tentang kelas algoritma yang terbatas yang "secara praktis" memiliki kekuatan yang sama dengan kelas algoritma polinomial.

cc.complexity-theory circuit-complexity Gil Kalai
sumber

Bisakah Anda menguraikan makna "secara praktis memiliki kekuatan yang sama"?

MS Dousti

Maksud saya, semua algoritma dalam P yang kita temui praktis berada dalam kelas terbatas (hipotetis) ini. Jadi saya tidak bermaksud kelas yang dikenal (atau dugaan) untuk menghilangkan algoritma tipe polinomial tertentu seperti AC_0 atau NC ^ i bukan yang saya maksud.

Gil Kalai

2

Untuk pertanyaan 2, kelas fungsi yang dikomputasi oleh LOGSPACE - sirkuit seragam ukuran polinom adalah P. (Dan Anda masih akan mendapatkan P bahkan dengan beberapa kelas kompleksitas yang lebih kecil dari LOGSPACE jika Anda mendefinisikan keseragaman dengan benar.) umumnya mengurangi kekuatan algoritma waktu polinomial.

Peter Shor

8

Saya pikir jawaban untuk pertanyaan pertama Anda adalah negatif: Sebuah sirkuit memiliki sejumlah input tetap, dan dengan demikian, IMO, kita hanya dapat berbicara tentang "keluarga" sirkuit, bukan hanya satu sirkuit yang seragam.

Mengenai pertanyaan kedua Anda, Anda dapat mencatat bahwa ada "keluarga rangkaian yang seragam," yang uraiannya dihasilkan oleh mesin Turing. Yaitu, biarkan menjadi rangkaian keluarga yang seragam, dan biarkan menjadi mesin Turing. Kemudian, untuk setiap , , di mana menunjukkan deskripsi . $\{C_n\}$ $M$ $n$ $[C_n] = M(1^n)$ $[C_n]$ $C_n$

Ada beberapa kelas kompleksitas di bawah P, yang didefinisikan oleh rangkaian keluarga yang seragam. Sebagai contoh:

adalah kelas masalah keputusan yang dapat diputuskan olehsirkuit boolean yangseragamdengan jumlah polinomial gerbang dan kedalaman. $\mathbf{NC}^i$ $O(\log^i n)$

MS Dousti
sumber

7

Menambah jawaban Sadeq di atas, ketika seseorang melihat kelas sirkuit yang terkandung dalam P, orang mungkin juga ingin melihat gagasan keseragaman yang semakin ketat.

Yang paling sederhana dan paling terkenal gagasan adalah P-keseragaman, yang merupakan persyaratan yang ada (deterministik) Mesin Turing M yang menghasilkan sirkuit $C_n$ dalam waktu poli (n) (Suresh juga membicarakan hal ini). Versi keseragaman yang lebih ketat mencoba membatasi kekuatan M lebih jauh. Sebagai contoh, ada juga Logspace-uniformity, di mana M sekarang diperlukan untuk berjalan di ruang O (log (n)).

Gagasan paling ketat yang saya tahu adalah DLOGTIME-uniformity, yang digunakan untuk kelas-kelas sirkuit kecil. Di sini, mesin (sekarang akses acak) M hanya memiliki waktu O (log n) dan karenanya tidak mungkin menuliskan deskripsi dari seluruh rangkaian. Kondisi yang diberlakukan adalah bahwa mengingat i dan n, M dapat menuliskan bit engan uraian rangkaian dalam waktu O (log n).

Untuk lebih lanjut, lihat makalah berikut: David A. Mix Barrington, Neil Immerman, Howard Straubing: Tentang Keseragaman dalam NC¹. J. Comput. Syst. Sci. 41 (3): 274-306 (1990).

Srikanth
sumber

1

Tautan ke surat kabar: dx.doi.org/10.1016/0022-0000(90)90022-D

Suresh Venkat

Jika M akan menulis bit ke-i dari deskripsi sirkuit di O (log n), bukankah itu berarti jika sirkuit berukuran O (n) maka itu sama dengan membiarkan mesin untuk menghasilkan seluruh rangkaian dalam O (n log n)?

M. Alaggan

1

Tampaknya tidak setara. Apa yang telah Anda tunjukkan adalah bahwa gagasan keseragaman di atas (Barrington et. Al.) Setidaknya sekuat gagasan keseragaman yang Anda usulkan. Kebalikannya tidak jelas. Secara khusus, tidak jelas bagi saya jika hal berikut ini benar: diberikan keluarga rangkaian ukuran

yang dapat dihasilkan oleh TM dalam waktu

, muncul dengan TM yang, mengingat

dan

, menghasilkan bit ke-

dari

dalam waktu

. Sebenarnya, saya pikir itu tidak benar.

O (n)

$O(n)$

O (n \log n)

$O(n\log n)$

i

$i$

n

$n$

i

$i$

C_{n}

$C_n$

O (\log n)

$O(\log n)$

Srikanth

Saya setuju, contoh penghitung adalah TM yang, mengingat

dan

, menghasilkan bit ke-

di

, kecuali untuk bit terakhir yang membutuhkan

. Terima kasih atas petunjuknya :)

i

$i$

n

$n$

i

$i$

O (1)

$O(1)$

O (n \log n)

$O(n \log n)$

M. Alaggan

Intinya bukan bahwa keluarga-keluarga rangkaian seragam-X memberikan rangkaian keluarga yang sama untuk X yang berbeda, tetapi bahwa fungsi-fungsi yang dapat dihitung oleh keluarga-keluarga sirkuit-seragam-X adalah sama untuk perbedaan X.

Peter Shor

6

$n$ $C_n$

Suresh Venkat
sumber

Generator LOGSPACE untuk sirkuit juga akan berfungsi dengan baik untuk menangkap P.

Peter Shor

5

Apakah ada deskripsi keseragaman hanya dalam hal sirkuit?

$1$ $f(|x|)$ $f$

Di sisi lain, jika kita diizinkan membatasi sirkuit yang seragam untuk mendefinisikan sirkuit, maka jawabannya jelas positif. Dan kita bisa menggunakan $FO$ (yang sama dengan $DLogTime$ dan seragam $AC^0$ ) untuk mendefinisikan keseragaman. $FO$ secara konseptual sangat dekat dengan sirkuit.

Tampak bagi saya bahwa titik utama di sini adalah bahwa kita memerlukan beberapa model perhitungan seragam untuk mendefinisikan keseragaman untuk rangkaian, jika deskripsi sirkuit diberikan dengan cara yang tidak seragam, sirkuit dapat tidak seragam.

Kaveh
sumber

1

FO tidak sama dengan DLogTime, tetapi untuk mengganti waktu log dengan

O (1)

$O(1)$ alternatif. Namun, untuk banyak kelas alami sirkuit, DLogTime-uniformity dan FO-uniformity bertepatan.

Emil Jeřábek mendukung Monica

@ Emil, Anda benar, terima kasih telah memperhatikan kesalahan, seharusnya begitu

A l t T i m e (O (1), O (\lg n))

$AltTime(O(1),O(\lg n))$ .

Kaveh

4

1) Apakah ada deskripsi keseragaman hanya dalam hal rangkaian?

[Ini adalah versi edit dari jawaban saya untuk pertanyaan yang sama yang Anda tanyakan di blog Dick Lipton. Peringatan: Saya bukan ahli.]

Ya (saya pikir), paling tidak dari dua jenis:

a) Sirkuit dapat dihasilkan oleh mesin Turing dalam waktu polinomial dalam ukuran input masalah (sebagaimana disebutkan dalam beberapa balasan lain). (Saya pikir ini adalah definisi standar dari konsep ini.)

Ini mencakup semua rangkaian keluarga yang ingin kami sebut seragam, tetapi sebagai definisi konsep P-time, ini hanya mengurangi definisi tentang rangkaian keluarga ke definisi pada mesin Turing, yang mungkin bukan yang Anda inginkan.

b) Jika ada otomat seluler 1 dimensi yang berevolusi input masalah ke solusi masalah (untuk masalah keputusan, solusi akan menjadi bit tunggal dalam sel tertentu relatif terhadap sel yang mengandung input, yang merupakan keadaan stabil CA), dalam waktu polinomial dalam ukuran input, maka ini sesuai dengan sirkuit yang periodik dalam 2D dengan cara sederhana (satu unit berulang per sel per unit waktu), dan yang keadaannya hanya penting di wilayah relatif besar secara kuadratik ke waktu solusi.

Ini adalah jenis rangkaian keluarga seragam yang sangat istimewa, tetapi cukup untuk menyelesaikan semua masalah dalam P, karena mesin Turing dapat dengan mudah dikodekan sebagai CA 1D. (Ini juga tampaknya memenuhi definisi keseragaman DLOGTIME yang disebutkan dalam balasan sebelumnya.)

(Ini mirip dengan pengkodean mesin Turing sebagai sirkuit yang disebutkan dalam balasan Gowers di blog Lipton - pada kenyataannya, salah satunya mungkin identik.)

Salah satu cara untuk menyandikan mesin Turing sebagai 1D CA: di setiap sel, kami mewakili keadaan pita pada satu titik, keadaan yang dimiliki kepala mesin turing jika ada di sini sekarang (yang nilainya tidak masalah jika tidak ada di sini) , dan sedikit mengatakan apakah kepala ada di sini sekarang. Jelas, setiap keadaan seperti itu pada waktu t hanya tergantung pada keadaan lingkungan terdekatnya pada waktu t-1, yang kita perlukan agar ini berfungsi sebagai CA.

sumber

Gagasan yang lebih kuat tentang penyeragaman?

Jawaban: