Konsekuensi dari bukti / algoritma sub-eksponensial untuk SAT

14

Apakah akan ada konsekuensi besar jika SAT paling banyak memiliki bukti tidak aman subeksponensial atau bahkan lebih kuat, SAT memiliki algoritma waktu subeksponensial?

Memilih
sumber
4
Ini akan membantah hipotesis waktu eksponensial yang memiliki berbagai konsekuensi (dibahas dalam artikel wikipedia).
Artem Kaznatcheev
1
@ArtemKaznatcheev komentar -> jawab?
Suresh Venkat
1
@SureshVenkat merasa agak canggung untuk memberikan jawaban ketika Ryan Williams dapat memberikan yang lebih baik. Saya memberikan satu untuk saat ini, tetapi saya berharap Ryan dan yang lainnya memberikan sesuatu yang lebih keren.
Artem Kaznatcheev
7
Jika jawabannya benar, tidak masalah siapa yang memberikannya :)
Suresh Venkat
7
Maaf Artem, jawaban saya tidak akan jauh lebih keren dari milik Anda ... Saya kira satu hal untuk ditambahkan adalah bahwa ETH salah menyiratkan sirkuit superlinear baru batas bawah (kertas yang sama).
Ryan Williams

Jawaban:

21

Jika SAT memiliki algoritma waktu subeksponensial, Anda akan membantah hipotesis waktu eksponensial .

npoly(n)2npoly(n)NEXPP/poly

Artem Kaznatcheev
sumber
10
Saya pikir paragraf pertama jawaban Anda hanyalah definisi dari hipotesis waktu eksponensial.
Tsuyoshi Ito