Berapa banyak oracle SAT akan membantu mempercepat algoritma waktu polinomial?

Akses ke oracle akan memberikan percepatan super-polinomial besar untuk semua yang ada di (dengan asumsi set tidak kosong). Hal ini kurang jelas, bagaimanapun, berapa banyak akan manfaat dari akses oracle ini. Tentu saja, percepatan dalam tidak bisa super polinomial, tetapi masih bisa polinomial. Misalnya, dapatkah kita menemukan jalur terpendek lebih cepat dengan oracle , daripada tanpa itu? Bagaimana dengan beberapa tugas yang lebih canggih, seperti minimisasi fungsi submodular atau pemrograman linier? Akankah mereka (atau masalah alam lainnya dalam ) mendapat manfaat dari oracle ?N P - P P P S A T P S A $SAT$${\bf NP}-{\bf P}$$\bf P$$\bf P$$SAT$$\bf P$$SAT$

Secara lebih umum, jika kita dapat mengambil masalah apa pun di , dan menggunakan oracle untuk itu, lalu mana dari masalah di bisa melihat percepatan?${\bf NP}-{\bf P}$$\bf P$

Sebenarnya, penerimaan mesin Turing nondeterministik dalam waktu adalah - waktu dapat direduksi menjadi SAT (konstruksi ini melalui simulasi yang tidak diketahui, lihat Arora-Barak), jadi biasanya setiap kali mesin nondeterministik jauh lebih cepat daripada deterministik. satu, kita akan melihat setidaknya beberapa speedup dengan oracle SAT.O ( t log t $t$$O(t \log t)$

Agar lebih konkret, pengujian primality muncul di pikiran, karena varian terbaik dari algoritma AKS muncul untuk menguji primality dari nomor bit dalam waktu . Tetapi jika kita pergi "sekolah tua", Pratt memberikan TM nondeterministic untuk memutuskan keutamaan dalam waktu . Penerimaan mesin ini dapat dikurangi (secara deterministik) dalam waktu menjadi instance SAT.O ( n $n$O ( n $O(n^6 \; \text{polylog}\; n)$O ( n $O(n^3 \; \text{polylog}\; n)$$O(n^3 \; \text{polylog}\; n)$

Masalah 3SUM dapat menjadi contoh lain, karena sepertinya seseorang dapat menebak solusi dan memeriksanya dalam waktu subquadratic, dan kemudian penerimaan mesin seperti itu dapat dikurangi menjadi SAT dalam waktu subquadratic.

Secara lebih umum, jika kita dapat mengambil masalah apa pun di NP − P, dan menggunakan oracle untuk itu, lalu masalah mana di P yang bisa melihat percepatan?

Pertanyaan ini menjadi lebih langsung pada representasi dan waktu yang diperlukan untuk mengurangi satu masalah ke masalah lain ....

Jawaban utama yang ada dalam pikiran saya adalah oracle Integer / Linear Programming. Versi keputusan dari masalah itu adalah NP-complete. Ada "pengurangan" sepele dari pemrograman linear karena ini adalah kasus khusus. Tetapi sebuah ramalan untuk pemrograman linier saja (apalagi ILP) mempercepat banyak masalah yang segera dipecahkan oleh pemrograman linier. Mereka dapat dikurangi menjadi waktu linier dengan menulis ulang masalah sebagai LP. Misalnya, jalur terpendek dan masalah aliran lainnya, kecocokan.

Tapi saya tidak berpikir ILP adalah satu-satunya dengan cara apa pun, mungkin lebih karena orang belum banyak berpikir tentang misalnya mengurangi jalur terpendek ke TSP atau lebih.

Pada catatan terkait (lebih dari komentar, posting sebagai jawaban atas permintaan), jika alih-alih oracle satu memungkinkan oracle , maka itu dapat digunakan untuk menemukan sirkuit minimal untuk masalah apa pun di (Ini mengikuti ide yang sama dengan bukti Karp-Lipton). Ini akan memberikan biaya diamortisasi yang hampir optimal untuk masalah apa pun; alasan itu hanya diamortisasi adalah bahwa jika Anda hanya menggunakan ini sekali, maka ukuran rumus Anda tulis pada dasarnya adalah runtime dari algoritma waktu-poli asli Anda, tetapi setelah langkah itu Anda kemudian memiliki rangkaian optimal untuk semua contoh ukuran .Σ 2 S A T P Σ 2 S A T ≤ $SAT$$\Sigma_2 SAT$$\mathsf{P}$$\Sigma_2 SAT$$\leq n$