Masalah dalam

Masalah apa yang diketahui milik tetapi tidak diketahui milik ? $\mathsf{BPP}$ $\mathsf P$

Lebih tepatnya, saya tertarik pada masalah independen , yaitu derandomisasi yang tidak diketahui setara. Misalnya, diketahui bahwa deritimasi PIT dan faktorisasi polinomial multivariat adalah sama dan saya akan menghitungnya hanya sebagai satu masalah.

Motivasi dari pertanyaan saya adalah bahwa adalah umum untuk mengatakan bahwa "ada beberapa masalah dalam tidak diketahui berada di " $\mathsf{BPP}$ $\mathsf{P}$ , tetapi saya tidak dapat menemukan daftar mereka. Secara khusus, jika saya harus mengutip masalah dalam kategori ini, saya biasanya mengutip faktorisasi polinomial univariat atas bidang terbatas, atau faktorisasi polinomial multivariat. Saya kira ada contoh yang tidak terkait dengan faktorisasi polinomial, misalnya di domain lain seperti teori grafik atau teori bahasa formal.

PS: Saya merasa ingin tahu bahwa pertanyaan serupa belum ada di situs web ini. Saya minta maaf jika saya tidak menemukannya (atau mereka)!

derandomization Bruno
sumber

Jawaban untuk posting ini berisi dua contoh cstheory.stackexchange.com/questions/11425/…

Mohammad Al-Turkistany

Jawaban:

Jika Anda meminta masalah independen, bagaimana:

Temukan bilangan prima dalam interval , Temukan dua bilangan prima yang produknya dalam interval , Temukan tiga bilangan prima yang produknya dalam interval , Temukan empat bilangan prima yang produknya dalam interval , Temukan lima bilangan prima yang produknya berada dalam interval , . $[N, 5N/4]$
$[N, 9N/8]$
$[N, 17N/16]$
$[N, 33N/32]$
$[N, 65N/64]$
$\ldots$

Sangat mungkin bahwa jika Anda benar-benar memiliki algoritma polinomial untuk menyelesaikan yang pertama, Anda akan memiliki algoritma polinomial untuk semuanya. Tapi saya tidak melihat bagaimana secara formal mengurangi semua ini ke yang lain. Tentu saja masalahnya

Temukan bilangan prima dalam interval $[N, N+\log^{17} N ]$

menyelesaikan semua ini.

Peter Shor
sumber

Tepatnya, apa versi keputusan dari masalah ini yang ada dalam pikiran Anda? Terima kasih.

usul

@ Usul: Saya tidak memiliki versi keputusan masalah ini dalam pikiran. Apakah saya perlu? Saya menyadari bahwa secara teknis, BPP hanya terdiri dari masalah keputusan. Sebagian besar waktu, masalah keputusan dan masalah fungsi kurang lebih setara, yang berarti Anda dapat mempertimbangkan hanya masalah keputusan tanpa kehilangan sifat umum. Saya tidak yakin itu benar untuk pertanyaan ini, dan saya tidak tahu apakah OP hanya peduli dengan masalah keputusan atau tidak.

Peter Shor

Saya hanya bertanya karena saya tidak tahu persis kapan kehalusan penting muncul. Saya pikir harus ada beberapa masalah fungsi yang diketahui tanpa syarat berada di "BPP" dan bukan "P", misalnya menghasilkan string kompleksitas Kolmogorov (?). Jadi saya pikir pertanyaan itu akan mengarah ke masalah keputusan, dan bertanya-tanya apakah versi keputusan yang valid dari jawaban Anda (diberikan pengetahuan saat ini) akan menjadi mis. "Apakah ada yang utama dalam ?"

n

$n$

[N, 5 N / 4]

$[N,5N/4]$

usul

@ Usul: Untuk pertanyaan: "apakah ada prima di ?", diketahui bahwa algoritma waktu-konstan ada. Sepertinya: Katakan "ya" ketika dan periksa secara eksplisit ketika . Anda memerlukan sejumlah teori bilangan untuk membuktikannya bekerja.

[N, 5 N / 4]

$[N, 5N/4]$

N > 10^{6}

$N > 10^6$

N \leq 10^{6}

$N \leq 10^6$

Peter Shor

Ok, tentu / baik-baik saja. Saya pikir saya setuju dengan komentar Kaveh dalam pertanyaan ini bahwa masalah keputusan alami yang sesuai adalah, mengingat , adakah yang utama dalam ?

a, b

$a,b$

[a, b]

$[a,b]$

usul

Ada penggunaan tertentu dari keacakan yang cukup umum dalam kompleksitas parameter, yang melibatkan lemma isolasi , atau lemma Schwartz-Zippel . Secara kasar, ini melibatkan pendataan sejumlah besar solusi potensial, dan berdebat bahwa semua non-solusi "berpasangan" (mis., Dihitung dua kali) sedangkan solusi yang diinginkan hanya dihitung satu kali. Kemudian seseorang menggunakan lemma isolasi untuk menghasilkan situasi dengan hanya satu solusi terkecil, atau mendefinisikan polinomial formal bersesuaian besar atas GF dan menggunakan Schwartz-Zippel untuk menguji apakah ada istilah yang tidak berpasangan. (Saya yakin ada ikhtisar atau survei yang bagus di luar sana, tetapi saat ini itu menyelinap di pikiran saya.) $(2^\ell)$

Yang mengatakan, saya hanya bisa memikirkan dua kasus di mana penggunaan ini akan menyebabkan perbedaan antara BPP dan P.

Yang pertama adalah algoritma terbaru untuk dua jalur terputus terpendek ( PDF penulis ), Björklund dan Husfeldt, ICALP 2014.

Yang kedua adalah masalah parameter - menemukan siklus sederhana melalui set K dari elemen yang ditentukan dalam grafik, yaitu, seperti masalah siklus Steiner. Ketika , masalah ini ada di BPP oleh Björklund, Husfeldt, Taslaman, SODA 2012 ( tautan ). (Ada algoritma deterministik sebelumnya, tetapi ketergantungannya pada secara eksponensial lebih buruk.) Jadi, seseorang dapat mendefinisikan masalah "log-Steiner Cycle" (atau apa pun yang Anda ingin menyebutnya), dan itu akan cocok dengan pertanyaan Anda. $|K|=O(\log n)$ $|K|$

Magnus Wahlström
sumber

Saya bukan ahli, tetapi mungkin beberapa contoh (tidak-jadi-alami?) Dapat diturunkan secara langsung menggunakan teknik mengurangi masalah pencarian BPP menjadi masalah keputusan BPP , disajikan dalam:

Oded Goldreich, Dalam Dunia P = BPP. Studi dalam Kompleksitas dan Kriptografi 2011: 191-232

$(R_{yes},R_{no})$ $R$ $R_{yes} \subseteq R \subseteq (\{0, 1\}^∗ \times \{0, 1\}^∗) \setminus R_{no}$ $R$ $\Pi$ $(R_{yes},R_{no})$ $\Pi$ $(R_{yes},R_{no})$

Teorema dapat diperluas ke masalah konstruksi umum, misalnya (lihat wajar 3.9 ) mempertimbangkan masalah menemukan prima dalam interval yang cukup besar:

$c > 7/12$ $N$ $[N, N + N^c]$

Algoritma acak berjalan dalam waktu polinomial yang diharapkan; tidak ada algoritma waktu polinomial deterministik yang diketahui; tetapi jika BPP = P algoritma waktu polinomial deterministik semacam itu harus ada (karena dapat dikurangi menjadi masalah keputusan BPP).

Marzio De Biasi
sumber