Beberapa pertanyaan tentang komputasi paralel dan kelas NC

14

Saya memiliki sejumlah pertanyaan terkait tentang kedua topik ini.

Pertama, sebagian besar teks kompleksitas hanya menutupi kelas . Apakah ada sumber daya yang baik yang mencakup penelitian lebih mendalam? Sebagai contoh, sesuatu yang membahas semua pertanyaan saya di bawah ini. Juga, saya berasumsi bahwa masih melihat cukup banyak penelitian karena kaitannya dengan paralelisasi, tetapi saya bisa saja salah. Bagian di kebun binatang kompleksitas tidak banyak membantu.NCNC

Kedua, perhitungan atas sebuah semi-grup adalah dalam jika kita mengasumsikan operasi semi-grup membutuhkan waktu yang konstan. Tetapi bagaimana jika operasi tidak memakan waktu konstan, seperti halnya untuk bilangan bulat tak terikat? Adakah yang diketahui - masalah lengkap?NC1NCi

Ketiga, karena , apakah ada algoritma untuk mengubah algoritma logspace menjadi versi paralel?LNC2

Keempat, sepertinya sebagian besar orang berasumsi bahwa dengan cara yang sama dengan . Apa intuisi di balik ini?NCPPNP

Kelima, setiap teks yang saya baca menyebutkan kelas tetapi tidak memberikan contoh masalah di dalamnya. Apakah ada?RNC

Akhirnya, jawaban ini menyebutkan masalah dalam dengan waktu eksekusi paralel sublinear. Apa saja contoh dari masalah ini? Apakah ada kelas kompleksitas lain yang berisi algoritma paralel yang tidak diketahui berada di ?PNC

Mike Izbicki
sumber
1
Perhatikan juga pertanyaan serupa ini .
Nicholas Mancuso

Jawaban:

9

Ketiga, sejak , apakah ada algoritma untuk mengubah algoritma logspace menjadi versi paralel?LNC2

Hal ini dapat ditunjukkan (Arora dan Barak buku teks) diberi -waktu TM M , bahwa menyadari TM M ' (yaitu TM yang gerakan kepala independen dari input x ) dapat membangun sebuah sirkuit C n untuk menghitung M ( x ) di mana | x | = n .t(n)MMxCnM(x)|x|=n

Sketsa buktinya ada di sepanjang garis memiliki mensimulasikan M dan mendefinisikan "snapshots" dari keadaannya (yaitu posisi kepala, simbol di kepala) pada setiap langkah waktu t i (pikirkan log perhitungan). Setiap langkah t i dapat dihitung dari x dan status t i - 1 . Karena setiap snapshot hanya melibatkan string berukuran konstan, dan hanya ada jumlah string konstan dari ukuran itu, snapshot pada t i dapat dihitung oleh sirkuit berukuran konstan.MMtitixti1ti

Jika Anda menulis sirkuit konstan berukuran untuk setiap kita memiliki sirkuit yang menghitung M ( x ) . Menggunakan fakta ini, bersama dengan pembatasan bahwa bahasa M dalam L kita melihat bahwa kami sirkuit C n adalah dengan definisi logspace-seragam , di mana keseragaman hanya berarti bahwa sirkuit kami di sirkuit keluarga kami { C n } komputasi M ( x ) semua memiliki algoritma yang sama. Bukan algoritma yang dibuat khusus untuk setiap sirkuit yang beroperasi pada ukuran input n .tiM(x)MLCn{Cn}M(x)n

Sekali lagi, dari definisi keseragaman kita melihat bahwa sirkuit yang memutuskan bahasa apa pun dalam harus memiliki ukuran fungsi ( n ) yang dapat dihitung dalam O ( log n ) . Rangkaian keluarga A C 1 memiliki paling banyak kedalaman O ( log n ) .Lsize(n)O(logn).AC1O(logn)

Akhirnya dapat ditunjukkan bahwa memberikan hubungan yang dimaksud.AC1NC2

Keempat, kedengarannya seperti kebanyakan orang menganggap bahwa dengan cara yang sama bahwa PN P . Apa intuisi di balik ini?NCPPNP

Sebelum kita melangkah lebih jauh, mari kita definisikan apa yang dimaksud dengan Kelengkapan- .P

Bahasa adalah P -lengkap jika L P dan setiap bahasa di P adalah logspace direduksi menjadi itu. Selain itu, jika L adalah P -complete maka yang berikut ini benarLPLPPLP

  1. LNCP=NC

  2. LLP=L

Sekarang kita mempertimbangkan menjadi kelas bahasa efisien diputuskan oleh komputer paralel (sirkuit kami). Ada beberapa masalah dalam P yang tampaknya menolak segala upaya paralelisasi (yaitu Pemrograman Linier, dan Masalah Nilai Sirkuit). Dengan kata lain, masalah tertentu membutuhkan perhitungan yang harus dilakukan secara bertahap.NCP

Misalnya, Masalah Nilai Sirkuit didefinisikan sebagai:

Diberikan sirkuit , input x , dan gerbang g C , berapakah output dari g pada C ( x ) ?CxgCgC(x)

Kita tidak tahu bagaimana untuk menghitung ini lebih baik dari komputasi semua gerbang yang datang sebelum g . Mengingat beberapa dari mereka dapat dihitung secara paralel, misalnya jika mereka semua terjadi di beberapa timestep t i , tapi kita tidak tahu bagaimana menghitung output dari gerbang di timestep t i dan timestep t i + 1 untuk kesulitan yang jelas bahwa gerbang pada t i + 1 membutuhkan keluaran gerbang pada t i !ggtititi+1ti+1ti

Ini adalah intuisi belakang .NCP


Limits to Parallel Computation adalah buku tentang Kelengkapan dalam nada yang sama dari buku N P- Kelengkapan Garey & Johnson .PNP

Nicholas Mancuso
sumber
Terima kasih atas 2 referensi dan jawaban parsial. Buku Limits to Parallel Computation melakukan pekerjaan yang lebih baik daripada buku-buku lain yang pernah saya baca, tetapi masih relatif tua dan tidak selengkap yang saya inginkan.
Mike Izbicki
3

Kelima, setiap teks yang saya baca menyebutkan kelas RNC tetapi tidak memberikan contoh masalah di dalamnya. Apakah ada?

Makalah "Matching semudah Inversi Matrix" oleh Mulmuley, Vazirani, dan Vazirani memiliki beberapa contoh masalah di kelas . Yang utama adalah menemukan pencocokan maksimal, lalu mereka mengurangi masalah lain untuk yang ini.RNC2

Mike Izbicki
sumber