Konsekuensi dari bukti / algoritma sub-eksponensial untuk SAT

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

cc.complexity-theory sat proof-complexity Memilih
sumber

Ini akan membantah hipotesis waktu eksponensial yang memiliki berbagai konsekuensi (dibahas dalam artikel wikipedia).

Artem Kaznatcheev

@ArtemKaznatcheev komentar -> jawab?

Suresh Venkat

@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

Jika jawabannya benar, tidak masalah siapa yang memberikannya :)

Suresh Venkat

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:

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

$n$ $poly(n)$ $2^n poly(n)$ $NEXP \not\subseteq P/poly$

Artem Kaznatcheev
sumber

Saya pikir paragraf pertama jawaban Anda hanyalah definisi dari hipotesis waktu eksponensial.

Tsuyoshi Ito