Apa versi besar dari NC?

$\mathsf{NC}$ menangkap gagasan tentang dapat diparalelkan secara efisien, dan salah satu interpretasinya adalah masalah yang dapat dipecahkan dalam waktu menggunakan prosesor paralel untuk beberapa konstanta , . Pertanyaan saya adalah apakah ada kelas kompleksitas analog di mana waktu adalah dan jumlah prosesor adalah . Sebagai pertanyaan isi-kosong: $O(\log^c n)$ $O(n^k)$ $c$ $k$ $n^c$ $2^{n^k}$

$\mathsf{NC}$ untuk seperti _ _ adalah untuk $\mathsf{P}$ $\mathsf{EXP}$

Secara khusus, saya tertarik pada model di mana kami memiliki jumlah eksponensial komputer yang diatur dalam jaringan dengan derajat terikat polinomi (katakanlah jaringan tidak tergantung pada input / masalah atau setidaknya entah bagaimana mudah dibangun, atau asumsi keseragaman yang masuk akal lainnya) ). Pada setiap langkah waktu:

Setiap komputer membaca jumlah polinomial dari pesan berukuran polinomial yang diterimanya pada langkah waktu sebelumnya.
Setiap komputer menjalankan beberapa komputasi polytime yang dapat bergantung pada pesan-pesan ini.
Setiap komputer mengirimkan pesan (polylength) ke masing-masing tetangganya.

Apa nama kelas kompleksitas yang sesuai dengan model semacam ini? Apa tempat yang baik untuk membaca tentang kelas kompleksitas seperti itu? Apakah ada masalah lengkap untuk kelas seperti itu?

cc.complexity-theory reference-request complexity-classes circuit-complexity dc.parallel-comp Artem Kaznatcheev
sumber

pertanyaan terkait, saya pikir: cstheory.stackexchange.com/q/2788/1037

Artem Kaznatcheev

Kami memiliki , , , . Jadi kelas yang sesuai dengan mungkin sesuatu seperti dan kemudian kelas yang sesuai dengan akan menjadi . Itu hanya beberapa manipulasi aljabar, saya belum memeriksa apakah itu memenuhi kebutuhan Anda, tapi saya pikir itu akan memenuhi tiga kondisi tetapi tidak akan memiliki banyak komputer secara eksponensial. Saya pikir Anda harus membatalkan persyaratan itu jika tidak (lebih)

N C^{k} = A S p a c e T i m e (O (\log n), (\log n)^{k})

$NC^k = ASpaceTime(O(\log n), (\log n)^k)$

N C = A S p a c e T i m e (O (\log n), (\log n)^{O (1)})

$NC = ASpaceTime(O(\log n), (\log n)^{O(1)})$

P = T i m e (n^{O (1)})

$P = Time(n^{O(1)})$

E X P = T i m e (2^{n^{O (1)}})

$EXP = Time(2^{n^{O(1)}})$

N C^{k}

$NC^k$

A S p a c e T i m e (n^{O (1)}, 2^{O (\log n)^{k}})

$ASpaceTime(n^{O(1)}, 2^{O(\log n)^k})$

N C

$NC$

A S p a c e T i m e (n^{O (1)}, 2^{(\log n)^{O (1)}})

$ASpaceTime(n^{O(1)}, 2^{(\log n)^{O(1)}})$

Kaveh

kelas yang dihasilkan akan berisi dan analogi tidak akan terus sebagai .

E X P

$EXP$

N C \subseteq P

$NC \subseteq P$

Kaveh

Saya tidak mengerti dari mana Anda mendapatkan dan kompleksitas ruang. Sejauh yang saya tahu memungkinkan banyak gerbang. Jika kita ingin mengikuti analog Anda maka kita harus melihat sebagai dan kemudian kelas kompleksitas yang saya cari adalah sesuatu seperti . Namun, saya berharap ada karakterisasi yang lebih baik dari ini.

l o g n

$log n$

N C

$NC$

N C

$NC$

P T / W K (l o g^{c} n, n^{k}) / p o l y

$PT/WK(log^c n,n^k)/poly$

P T / W K (n^{c}, 2^{n^{k}}) / p o l y

$PT/WK(n^c ,2^{n^k})/poly$

Artem Kaznatcheev

Itu standar (meskipun tidak di Kebun Binatang Kompleksitas), periksa misalnya Ruzzo, "Pada kompleksitas sirkuit seragam", 1981. Juga saya pikir Anda harus bekerja dengan kelas yang seragam, setiap fungsi memiliki pergantian ukuran eksponensial / kedalaman logis 2 sirkuit (dan ini akan memenuhi tiga kondisi jika kita menggunakan fan-in dan depth dibatasi ). Dan seperti yang saya katakan, jika ada banyak node secara eksponensial maka analoginya tidak berlaku. Juga properti utama dari komputasi paralel adalah menghemat waktu, misalnya itu adalah waktu poly-log dalam kasus . Saya pikir waktu kuasi polinomial akan sesuai dengan waktu poly-log.

\log n

$\log n$

N C

$NC$

Kaveh

Jawaban:

Saya percaya kelas yang Anda cari adalah . Misalkan Anda memiliki prosesor yang memenuhi persyaratan: $PSPACE$ $exp(n^k) = 2^{O(n^k)}$

Setiap komputer membaca jumlah polinomial dari pesan berukuran polinomial yang diterimanya pada langkah waktu sebelumnya.

Setiap komputer menjalankan beberapa komputasi polytime yang dapat bergantung pada pesan-pesan ini.

Setiap komputer mengirimkan pesan (polylength) ke masing-masing tetangganya.

Ini dapat dimodelkan dengan memiliki rangkaian dengan lapisan , di mana setiap lapisan memiliki "gerbang" , dan setiap "gerbang" melakukan perhitungan waktu polinomial (bagian memuaskan 2) dengan kipas-in polinomial ( memuaskan bagian 1), dan memiliki polinomial fan-out (bagian memuaskan 3). $poly(n)$ $exp(n^k)$

Karena setiap gerbang menghitung fungsi waktu polinomial, masing-masing gerbang dapat diganti dengan sirkuit ukuran polinomial (dengan DAN / ATAU / TIDAK) dengan cara biasa. Perhatikan bahwa fan-in dan fan-out polinomial dapat dibuat menjadi 2, dengan hanya meningkatkan kedalaman dengan faktor . Yang tersisa adalah sirkuit seragam kedalaman dengan gerbang DAN / ATAU / BUKAN. Ini adalah waktu polinomial yang bergantian, yang merupakan . $O(\log n)$ $poly(n)$ $exp(n^k)$ $PSPACE$

Ryan Williams
sumber

Ryan, saya tidak tahu bagaimana Anda menempatkan jumlah komputer yang eksponensial dalam banyak lapisan, menurut saya kedalamannya bisa eksponensial, dapatkah Anda menjelaskannya sedikit lagi mengapa ini mungkin? Juga nampak bagi saya bahwa konstruksi sepele dari sirkuit CNF dari fungsi yang diberikan sewenang-wenang sebagai sirkuit fan-in 2 akan memenuhi persyaratan, apakah saya melewatkan sesuatu?

Kaveh

@ Kaveh: Saya tidak mengerti pertanyaan pertama Anda. Tentang yang kedua, meskipun ada sirkuit kedalaman-ukuran eksponensial-2 untuk fungsi apa pun, NC (poli) mengharuskan Anda untuk dapat menghasilkan sirkuit secara seragam, sehingga Anda tidak dapat menghasilkan sirkuit arbitrer untuk setiap ukuran input.

Robin Kothari

@Robin, terima kasih. Mungkin saya membingungkan hal-hal. (Saya merasa bahwa kedalaman rangkaian yang sesuai dengan PSpace harus eksponensial, juga saya pikir PSpace adalah EXP karena L adalah ke P sehingga menyatakan hal yang sama ketika L digantikan oleh NC adalah aneh bagi saya, saya merasa bahwa kelas kita adalah Menjaga harus antara PSpace dan EXP.) Saya harus berpikir sedikit lebih untuk memahami apa yang terjadi di sini.

Kaveh

@ Kaveh, saya menetapkan jumlah lapisan (yaitu kedalaman) sebagai eksponensial, sehingga kedalaman tidak dapat eksponensial, menurut definisi. Ada banyak prosesor secara eksponensial, sehingga CNF Anda akan memerlukan kipas masuk secara eksponensial, melanggar salah satu syarat. Kedalaman sirkuit ukuran eksponensial yang sesuai dengan PSPACE adalah polinomial. Alasan ini benar, dan alasan bahwa kedua analogi itu "valid" dalam arti ("PSPACE adalah EXP sebagaimana L adalah ke P" dan "PSPACE adalah untuk EXP sebagaimana NC adalah ke P") adalah karena PSPACE = Alternating Polynomial Waktu. Kami tidak tahu apakah L = Alternating Logarithmic Time (ini adalah NC1).

Ryan Williams

Saya pikir saya memahami situasi dengan lebih baik setelah membaca komentar Anda dan Robin, terima kasih.

Kaveh

Seperti kata Ryan, kelas ini adalah PSPACE. Kelas ini sering disebut NC (poly) dalam literatur. Berikut adalah kutipan langsung dari makalah QIP = PSPACE :

Kami menganggap varian NC yang ditingkatkan, yang merupakan kelas kompleksitas NC (poli) yang terdiri dari semua fungsi yang dapat dihitung oleh keluarga seragam ruang-polinomial dari sirkuit Boolean yang memiliki kedalaman polinomial. (Notasi NC (2 ^poli ) sebelumnya juga telah digunakan untuk kelas ini [11].) Untuk masalah keputusan, diketahui bahwa NC (poli) = PSPACE [10].

[10] A. Borodin. Terkait waktu dan ruang dengan ukuran dan kedalaman. SIAM Journal on Computing, 6: 733- 744, 1977.

[11] A. Borodin, S. Cook, dan N. Pippenger. Komputasi paralel untuk cincin yang diberkahi dengan baik dan mesin probabilistik yang terbatas ruang. Informasi dan Kontrol, 58: 113–136, 1983.

Salah satu cara untuk melihat ini adalah membuktikan kedua inklusi secara langsung. Untuk melihat bahwa NC (poli) ada di PSPACE, perhatikan bahwa kami dapat menghitung output dari gerbang akhir secara rekursif, dan kami hanya akan membutuhkan tumpukan ukuran yang sama dengan kedalaman rangkaian, yang jumlahnya banyak. Untuk menunjukkan bahwa PSPACE menggunakan NC (poly), perhatikan bahwa QBF, yang merupakan PSPACE-complete, dapat ditulis sebagai rangkaian kedalaman polinomial dengan banyak gerbang secara eksponensial dengan cara yang biasa - quantifier yang ada adalah gerbang OR, forall quantifier adalah gerbang AND. Karena hanya ada banyak penjumlah secara polinomi, ini adalah rangkaian kedalaman polinomial.

Robin Kothari
sumber