Apakah ada oracle sehingga SAT tidak sering tanpa batas dalam waktu sub-eksponensial?

Tetapkan $io$ - $SUBEXP$ untuk menjadi kelas bahasa $L$ sedemikian rupa sehingga ada bahasa dan untuk tak terhingga banyaknya , dan menyetujui semua contoh panjang . (Yaitu, ini adalah kelas bahasa yang dapat "dipecahkan secara tak terhingga, dalam waktu subeksponensial".) $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ $n$ $L$ $L'$ $n$

Apakah ada oracle sehingga - ? Jika kita melengkapi SAT dengan oracle dengan cara biasa, dapatkah kita mengatakan bahwa tidak ada di kelas ini? $A$ $NP^A \not\subset io$ $SUBEXP^A$ $A$ $SAT^A$

(Saya mengajukan pertanyaan terpisah di sini, karena kita harus berhati-hati dengan kelas waktu yang tak terbatas-sering: hanya karena Anda memiliki pengurangan dari masalah ke masalah dan dapat dipecahkan secara tak terhingga sering, Anda mungkin tidak benar-benar mendapatkan bahwa dapat dipecahkan) tak terhingga sering tanpa asumsi lebih lanjut tentang reduksi: bagaimana jika reduksi Anda dari "meleset" panjang input yang dapat Anda selesaikan dengan ?) $B$ $C$ $C$ $B$ $B$ $C$

cc.complexity-theory sat oracles Ryan Williams
sumber

sepertinya perpanjangan atau variasi pada gagasan Baker Gill Solovay 1975? Bisakah itu dikontraskan?

vzn

Jawaban:

Anda bisa mengambil oracle A st NP = EXP karena EXP tidak dalam io-subexp. Untuk SAT itu tergantung pada encoding, misalnya jika satu-satunya instance SAT yang valid memiliki panjang genap maka mudah untuk menyelesaikan SAT pada string odd-length. Tetapi jika Anda menggunakan bahasa seperti maka Anda harus baik-baik saja. $^A$ $^A$ $^A$ $L=\{\phi 01^*\ |\ \phi\in SAT^A\}$

Lance Fortnow
sumber

Apakah Anda memiliki referensi untuk konsep io kelas kompleksitas dan pemisahan dalam literatur. Secara khusus, saya tidak yakin mengapa

. Selain itu, apakah kita memiliki (1)

EXP⊈io $EXP \nsubseteq io$

SUBEXP $SUBEXP$

TIME(f(n))⊈io $TIME(f(n)) \nsubseteq io$

untuk fungsi yang sesuai f (n), dan (2)

menyiratkan

(atau setidaknya

)? TIME(f(n)log(f(n))) $TIME(\frac{f(n)}{\log(f(n))})$

NP⊆io $NP \subseteq io$

P $P$

P=NP $P = NP$

NP⊆P/poly $NP \subseteq P/ poly$

Michael Wehar

Saya kira kebingungan utama saya adalah mengapa tidak bisa setiap

masalah memiliki

algoritma yang hanya memecahkan masalah untuk satu set panjang masukan

di mana

adalah

mengatur dirinya sendiri. EXP $EXP$

Complete $Complete$

io $io$

SUBEXP $SUBEXP$

X $X$

EXP $EXP$

Complete $Complete$

Michael Wehar

In other words, the

io $io$ -

SUBEXP $SUBEXP$ algorithm doesn't help us because we would have to decide

X $X$ in order to know how to use the

io $io$ -

SUBEXP $SUBEXP$ algorithm. But, I wouldn't be surprised if existing work from you or others resolves my inquiry.

Michael Wehar

@RyanWilliams Hi Ryan, any thoughts? Thanks for your time. :)

Michael Wehar

@RyanWilliams Terima kasih atas komentarnya! Itu membantu dan saya pikir saya berhasil. Sekarang, sepertinya argumen itu tidak bergantung sama sekali pada EXP dan ini bisa digeneralisasi untuk membuktikan sesuatu seperti (1). Tapi, kuncinya adalah "nilai yang berlawanan pada setidaknya satu input dengan panjang itu ". Dengan kata lain, argumen di kepala saya tergantung pada io yang didefinisikan sebagai menyetujui panjang input yang tak terhingga banyaknya (bukan hanya input yang tak terhingga banyaknya). Saya masih belum memiliki banyak ide tentang sesuatu seperti (2). Terima kasih lagi dan selamat menikmati hari / malam. :)

Michael Wehar

Anda tidak harus melakukan apa yang disarankan Lance. Sebagai contoh, relatif ke oracle acak, menggunakan oracle sebagai fungsi satu arah (katakanlah, dievaluasi pada posisi bit berturut-turut) secara eksponensial sulit untuk membalikkan pada semua panjang tetapi banyak panjang.

Masalah ini secara langsung berkurang menjadi SAT pada input panjang yang sama, sehingga berarti SAT ^ A tidak sering dalam sub-exp.

Russell Impagliazzo
sumber

Saya harus mengatakan jumlah input ke sirkuit adalah sama, bukan ukuran instance total. Namun, jika Anda diizinkan untuk mengukur ukuran sirkuit dengan menambahkan klausa redundan, Anda harus dapat membuat kode ukuran input tetap fungsi satu arah yang terkait.

Russell Impagliazzo