Mengapa keacakan memiliki efek yang lebih kuat pada reduksi daripada pada algoritma?

Dugaan bahwa keacakan tidak memperpanjang kekuatan algoritma waktu polinomial, yaitu, diperkirakan untuk ditahan. Di sisi lain, keacakan tampaknya memiliki efek yang sangat berbeda pada pengurangan waktu polinomial . Dengan hasil Valiant dan Vazirani yang terkenal, berkurang menjadi melalui pengurangan waktu polinomial secara acak. Kecil kemungkinan bahwa pengurangan tersebut dapat diderandomisasi, karena akan menghasilkan , yang dianggap tidak mungkin. S A T U S A T N P = U ${\bf P}={\bf BPP}$$SAT$$USAT$${\bf NP}={\bf UP}$

Saya bertanya-tanya, apa yang bisa menjadi alasan untuk situasi asimetris ini: derandomisasi tampaknya sangat mungkin dalam algoritma waktu polinomial probabilistik, tetapi tidak dalam pengurangan waktu polinomial probabilistik?

Pertama, izinkan saya mengomentari kasus spesifik pengurangan Valiant-Vazirani; Saya harap ini akan membantu memperjelas situasi umum.

Pengurangan Valiant-Vazirani dapat dilihat / didefinisikan dalam beberapa cara. Penurunan ini "mencoba" untuk memetakan satisfiable rumus Boolean ke unik-satisfiable F ' , dan unsatisfiable F ke unsatisfiable F ' . Semua formula output selalu diperoleh dengan membatasi F lebih lanjut , sehingga ketidakpuasan selalu dipertahankan. Pengurangan dapat didefinisikan baik sebagai keluaran tunggal F ' , atau sebagai keluaran daftar F ' 1 , ... , F ' t . Dalam kasus terakhir, "sukses" dalam kasus F $F$$F'$$F$$F'$$F$$F'$$F'_1, \ldots, F'_t$ didefinisikan sebagai memilikipaling tidak satu F ′ i yang memuaskan secara unikdalam daftar. Sebut kedua varian ini masing-masing "reduksi tunggal" dan "reduksi daftar" (ini bukan terminologi standar).$F \in SAT$$F'_i$

Poin pertama yang penting untuk dicatat adalah bahwa probabilitas keberhasilan dalam pengurangan tunggal cukup kecil, yaitu mana n adalah jumlah variabel. Kesulitan dalam meningkatkan probabilitas keberhasilan ini dieksplorasi dalam makalah ini$\Theta(1/n)$$n$

"Apakah Kemungkinan Isolasi Valiant-Vazirani Dapat Diperbaiki?" oleh Dell et al.

http://eccc.hpi-web.de/report/2011/151/#revision1

Dalam daftar-reduksi, probabilitas keberhasilan dapat dibuat besar, katakanlah, dengan daftar ukuran poli ( n ) . (Misalnya, seseorang dapat mengulangi pengurangan singleton berkali-kali).$1 - 2^{-n}$$(n)$

Sekarang, sama sekali tidak jelas atau intuitif bahwa kita harus dapat secara langsung derandomisasi pengurangan yang hanya memiliki probabilitas keberhasilan . Memang, tidak ada hasil kekerasan-vs-keacakan memberikan hipotesis di mana kita dapat melakukannya dalam kasus ini. Adalah jauh lebih masuk akal bahwa reduksi-daftar dapat diderandomisasi (dengan daftar yang agak lebih besar). Namun perlu dicatat bahwa ini tidak akan menyiratkan N P = U P : daftar output formula kami mungkin memiliki banyak formula yang memuaskan secara unik, dan mungkin beberapa dengan banyak tugas yang memuaskan, dan tampaknya sia-sia untuk mencoba menentukan perhitungan yang menerima secara unik atas suatu daftar. $1/n$$NP = UP$

Bahkan jika kita bisa memberikan pengurangan daftar di mana memuaskan selalu menginduksi daftar F ′ 1 , ... , F ′ t di mana sebagian besar F ′ j memuaskan secara unik, tidak ada cara yang jelas untuk mengubahnya menjadi pengurangan singleton deterministik untuk isolasi. Kesulitan yang mendasari sebenarnya adalah bahwa kita tidak tahu dari setiap "operasi perkiraan mayoritas untuk formula unik-satisfiable", yaitu, pengurangan R ( F ' 1 , ... , F ' t$F$$F'_1, \ldots, F'_t$$F'_j$$R(F'_1, \ldots, F'_t)$yang outputnya memuaskan secara unik jika sebagian besar memuaskan secara unik, dan tidak memuaskan jika sebagian besar F ′ j tidak memuaskan. Ini juga tampak seperti fenomena umum: reduksi menghasilkan objek yang lebih kompleks daripada algoritme keputusan, dan properti dari objek ini lebih sulit untuk diperiksa, jadi lebih sulit untuk menggabungkan banyak objek ini menjadi objek tunggal yang mewarisi beberapa properti mayoritas.$F'_j$$F'_j$

Untuk kasus Valiant-Vazirani, tampaknya bahkan tidak mungkin dalam asumsi derandomisasi yang masuk akal bahwa kita akan dapat memperoleh , yaitu, untuk secara deterministik mengurangi formula yang memuaskan menjadi formula yang memuaskan dengan ≤ poli ( n ) solusi. Secara intuitif ini berasal dari fakta bahwa prosedur pengisolasian tidak tahu bahkan ukuran kasar dari rangkaian larutan formula F yang diberikan.$NP = FewP$$\leq$$(n)$$F$

Di dunia oracle, mudah untuk memberikan contoh di mana keacakan memberi kita lebih banyak kekuatan. Pertimbangkan, misalnya, masalah menemukan nol fungsi Boolean yang seimbang. Algoritma acak mencapai bahwa menggunakan query dengan probabilitas keberhasilan konstan, sedangkan algoritma deterministik membutuhkan setidaknya n / 2 query.$O(1)$$n/2$

Berikut adalah situasi lain di mana diduga bahwa pengacakan membantu. Misalkan kita ingin memaksimalkan fungsi submodular monoton di atas batasan matroid. Ada dua algoritma berbeda yang memberikan perkiraan , dan ini optimal dalam model ini dengan hasil dari Vondrák. Kedua algoritma perlu menghitung fungsi dari bentuk E x ∼ X f ( x ) , di mana $1-1/e$$\mathbb{E}_{x \sim X} f(x)$$X$adalah distribusi dengan dukungan eksponensial. Komputasi fungsi ini sebenarnya terlalu mahal, tetapi dapat diperkirakan dengan pengambilan sampel, dan hasilnya adalah algoritma acak. Sebaliknya, algoritma deterministik dikenal, algoritma serakah, memberikan pendekatan.$1/2$

Situasi serupa terjadi dalam maksimisasi submodular tanpa kendala (di sini fungsinya tidak harus monoton). Algoritma terobosan baru-baru ini memberikan optimal pendekatan, tapi versi deterministik yang hanya memberikan 1 / 3 pendekatan. Di sini pengacakan memanifestasikan dirinya baik dengan cara yang persis sama seperti dalam kasus monoton, atau (dalam versi algoritma yang berbeda) dengan membuat beberapa pilihan acak di sepanjang jalan.$1/2$$1/3$

Salah satu penulis dari dugaan kertas terakhir yang adalah yang terbaik yang algoritma deterministik dapat mencapai, dan kami sama bisa berspekulasi bahwa 1 / 2 adalah yang terbaik yang dapat dicapai dalam masalah sebelumnya. Jika dugaan ini benar, maka ini adalah situasi yang sangat alami di mana pengacakan terbukti dapat membantu.$1/3$$1/2$

Baru-baru ini, Dobzinski dan Vondrák menunjukkan bagaimana mengubah nilai batas bawah oracle (untuk algoritma acak) menjadi hasil kekerasan, tergantung pada NP berbeda dari RP (bahan utama adalah daftar decoding). Kita harus menyebutkan bahwa transformasi bergantung pada metode spesifik yang digunakan untuk membuktikan batas bawah oracle. Mungkin benar bahwa nilai deterministik oracle batas bawah juga diterjemahkan ke dalam hasil kekerasan.

Salah satu alasan mengapa mungkin tampak aneh bagi Anda, bahwa kita tampaknya berpikir ada lebih jelas (atau menduga) kekuasaan di pengurangan acak dari ke U P daripada yang sebanding dari B P P ke P , karena Anda mungkin tergoda untuk menganggap keacakan sebagai sesuatu yang kuat (atau tidak kuat) terlepas dari "mesin" yang Anda tambahkan (jika kita karikatur kelas kompleksitas ini sebagai kelas yang muncul dari model mesin).$\mathsf{NP}$$\mathsf{UP}$$\mathsf{BPP}$$\mathsf P$

Namun, pengurangan kekuatan yang berbeda ini ada. Bahkan, sumber daya komputasi seperti keacakan tidak selalu memiliki jumlah daya komputasi yang tetap, yang bisa "signifikan" atau "tidak signifikan".

Kita dapat mempertimbangkan kelas kompleksitas apa pun yang rendah untuk dirinya sendiri - misalnya, , P , B P P , B Q P , ⊕ P , atau P S P A C E E - untuk dapat menerima model mesin yang jenisnya mesin selalu memiliki keadaan yang terdefinisi dengan baik yang dapat Anda ajukan pertanyaan kapan saja, sembari juga memungkinkan perhitungan berlanjut melampaui pertanyaan yang Anda tanyakan: pada dasarnya, mesin tersebut dapat mensimulasikan satu algoritma sebagai subrutin untuk lain. Mesin yang melakukan perhitungan mungkin tidak terlalu realistis$\mathsf L$$\mathsf P$$\mathsf{BPP}$$\mathsf{BQP}$$\mathsf{\oplus P}$$\mathsf{PSPACE}$jika kita membatasi diri kita pada batasan praktis pada sumber daya ( mis.  secara fisik dapat diwujudkan dan mampu menghasilkan jawaban dalam waktu polinomial derajat rendah untuk masalah yang menarik), tetapi tidak seperti kelas-kelas seperti - yang kita tidak tahu bagaimana mesin nondeterministik dapat menghasilkan jawaban untuk masalah lain di N P dan menggunakan jawabannya dengan cara apapun selain dari (iterasi) penghubung dan ketidaksinambungan pengurangan kebenaran-meja - membayangkan kelas rupa yang diwujudkan oleh mesin dengan negara yang terdefinisi dengan baik yang kita dapat menyelidiki apakah tidak menyesatkan kita.$\mathsf{NP}$$\mathsf{NP}$

Jika kita mengambil posisi ini, kita dapat bertanya apa yang terjadi jika kita memberikan model komputasi dengan fasilitas tambahan seperti keacakan atau nondeterminisme. (Fasilitas tambahan ini tidak serta-merta menjaga sifat dapat ditafsirkan oleh model mesin, terutama dalam kasus nondeterminisme, tetapi mereka menimbulkan kelas 'baru'.) Jika fasilitas tambahan ini memberi model lebih banyak kekuatan, menimbulkan kenaikan untuk kelas C , ini berlaku setara dengan mengatakan bahwa ada pengurangan dari C ke M menggunakan fasilitas itu, misalnya  pengurangan acak dalam kasus keacakan.$\mathsf M$$\mathsf C$$\mathsf C$$\mathsf M$

Alasan mengapa saya menggambarkan ini dalam hal kelas yang rendah untuk diri mereka sendiri adalah bahwa jika kita menganggap serius bahwa mereka adalah "model kemungkinan perhitungan di dunia lain", pertanyaan Anda tentang pengurangan acak sesuai dengan fakta bahwa tampaknya bahwa keacakan secara dramatis meningkatkan kekuatan beberapa model tetapi tidak yang lain .

$\mathsf{NP}$$\mathsf{UP}$$\mathsf{PH}$$\mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{PH} \subseteq \mathsf{BP\cdot\oplus P}$$\mathsf{\oplus P}$$\mathsf{\oplus P}$

$\mathsf{BPP} = \mathsf{P}$$\mathsf{BPP} \subseteq \Sigma^{\mathsf p}_2 \cap \Delta^{\mathsf p}_2$$\mathsf{NP}$$\mathsf{coNP}$

$\mathsf{PH}$$\mathsf{\oplus P}$$\mathsf{BPP} \approx \mathsf{P}$$\mathsf{BPP} = \mathsf{P}$bukan bahwa "keacakan tidak memiliki kekuatan", tetapi keacakan itu saja (atau lebih tepatnya, ditambah hanya dengan perhitungan waktu polinomial dan disediakan untuk model komputasi yang ditentukan deterministik) tidak kuat. Tetapi ini tidak berarti bahwa tidak ada kekuatan secara acak, yang dapat dikatalisis oleh sumber daya komputasi lainnya.