Model Komputasi dalam SETH

Impagliazzo, Paturi dan Calabro, Impagliazzo, Paturi memperkenalkan Hipotesis Eksponensial-Waktu (ETH) dan Hipotesis Eksponensial- Kuat (SETH). Secara kasar, SETH mengatakan bahwa tidak ada algoritma yang memecahkan SAT dalam waktu . $1.99^n$

Saya bertanya-tanya apa artinya menghancurkan SETH. Kita pasti perlu menemukan algoritma yang memecahkan SAT dalam kurang dari langkah, tapi saya tidak begitu mengerti model komputasi apa yang harus kita gunakan. Sejauh yang saya tahu, hasil berdasarkan SETH (lihat, misalnya, Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, Wahlstrom ) tidak perlu membuat asumsi tentang model perhitungan yang mendasarinya.$2^n$

Asumsikan, misalnya, bahwa kami menemukan sebuah algoritma yang memecahkan SAT dalam waktu menggunakan ruang 1,5 n . Apakah itu secara otomatis menyiratkan bahwa kita dapat menemukan Mesin Turing yang memecahkan masalah ini dalam waktu 1,99 n ? Apakah itu merusak SETH?$1.5^n$$1.5^n$$1.99^n$

SETH mengatakan bahwa untuk semua ada k sehingga k -SAT membutuhkan 2 δ n waktu untuk diselesaikan dalam kasus terburuk. Model komputasi umumnya dianggap sebagai mesin akses-acak atau model mesin penunjuk, yang memungkinkan akses waktu O ( log N ) ke penyimpanan item N , dan secara umum diasumsikan juga probabilistik dengan kesalahan terikat.$\delta < 1$$k$$k$$2^{\delta n}$$O(\log N)$$N$

Sejauh yang saya tahu, itu terbuka apakah waktu algoritma pada model seperti itu dapat diterjemahkan ke dalam Turing mesin dua-tape berjalan di 2 δ n ⋅ p o l y ( n ) waktu. Namun demikian, membuktikan bahwa terjemahan semacam itu tidak mungkin akan memisahkan mesin Turing multitape dari mesin akses acak, yang akan memiliki beberapa implikasi yang sangat menarik. Untuk satu, itu akan membuktikan bahwa SAT tidak dapat dipecahkan dalam waktu kuasi-linear pada mesin Turing multitape (karena, jika SAT dapat diselesaikan dengan mesin multitape tersebut, maka mesin akses acak dapat$2^{\delta n}$$2^{\delta n} \cdot poly(n)$disimulasikan secara efisien dengan mesin Turing multitape). Perhatikan bahwa banyak primitif komputasi (seperti penyortiran, evaluasi sirkuit, pemrograman dinamis sederhana) dapat diimplementasikan secara efisien pada mesin Turing multitape. Salah satu referensi yang relevan untuk masalah ini adalah Regan, "Tentang Perbedaan Antara Waktu Mesin Turing dan Waktu Mesin Akses-Acak."

Untuk menjawab pertanyaan spesifik Anda: tidak, mesin multitape Turing tidak secara otomatis tersirat di sini, tapi ya, "algoritma" untuk SAT (di bawah model akses acak biasa) akan merusak SETH.