Apa kompleksitas dari subset SAT berikut?

Asumsikan $P \neq NP$

Mari gunakan notasi berikut ${}^ia$ for tetration (mis. ${}^ia = \underbrace{a^{a^{\cdot^{\cdot^{\cdot^{a}}}}}}_{i \mbox{ times}}$ ).

| x | adalah ukuran instance x.

Biarkan L menjadi bahasa, $L|_{f(i)\leq |x| < g(i)} := \{ x \in L \mbox{ | } \exists i \in \mathbb{N}\mbox{, } f(i) \leq |x| < g(i) \}$

Apa kompleksitas dari bahasa-bahasa berikut:

$L_1 = SAT|_{{}^{2i}2 \leq |x| < {}^{2i+1}2}$ $L_2 = SAT|_{{}^{2i+1}2 \leq |x| < {}^{2i+2}2}$

Sebagai , mereka tidak dapat baik di P di bawah asumsi bahwa . Karena keduanya memiliki lubang eksponensial, saya tidak berpikir SAT dapat dikurangi menjadi satu. $L_1 \sqcup L_2 = SAT$ $P \neq NP$

Karena itu intuisi mereka adalah keduanya di NPI, tetapi saya tidak dapat menemukan bukti atau disproof.

Dua bahasa lainnya adalah $L_3 = SAT|_{|x|={}^{2i+1}2}$ $L_4 = SAT|_{|x|={}^{2i}2}$

Jika salah satu dari keduanya berada di NPC, yang lain di P karena untuk setiap contoh dari satu, itu tidak dapat diubah menjadi contoh yang lebih besar dari yang lain karena ukurannya eksponensial, dan contoh yang lebih kecil memiliki ukuran logaritmik. Masih dengan intuisi, tidak ada alasan mengapa mereka akan memiliki kompleksitas yang berbeda. Akan seperti apa kompleksitasnya?

Bukti Ladner tentang masalah NPI berdasarkan asumsi menggunakan bahasa seperti atau , tetapi dan tidak dibangun oleh diagonalisasi. $P \neq NP$ $L_1$ $L_2$ $L_1$ $L_2$

cc.complexity-theory np-hardness complexity-classes Ludovic Patey
sumber

Bahasa Anda memiliki banyak contoh yang diisi dengan penambahan klausa tambahan yang tidak saling berinteraksi. Karena itu, mereka tampak seperti NPI oleh argumen diagonalisasi Schöning? dx.doi.org/10.1016/0304-3975(82)90114-1

András Salamon

Setelah "mereka tidak bisa keduanya dalam P", seharusnya dikatakan "dengan asumsi bahwa P

NP ..."

\neq

$\ne$

Emil

Saya menambahkan "di bawah asumsi" bahkan jika saya sudah menetapkan asumsi ini sebelumnya.

Ludovic Patey

Jika salah satu L1 atau L2 adalah NP-lengkap, maka Isomorphism Conjecture gagal, karena baik L1 maupun L2 adalah sebuah silinder (memiliki fungsi bantalan). Jadi membuktikan bahwa salah satunya adalah NP-complete membutuhkan teknik non-relativizing. Saya belum melihat adanya hambatan untuk menunjukkan bahwa salah satu dari mereka tidak menyelesaikan NP.

Joshua Grochow

Saya mungkin agak tidak jelas dengan bilangan saya. Izinkan saya menambahkan tanda kurung: tidak ada mesin oracle poli-waktu

sehingga [untuk semua

[

memecahkan

]]. Artinya, untuk setiap

, mungkin bahwa untuk beberapa X,

memecahkan salah satu bahasa, tetapi tidak mungkin benar untuk semua

. Jadi, misalnya,

tanpa oracle mungkin menyelesaikan

(tidak terkait), tetapi tidak peduli apa

M

$M$

X

$X$

M^{X}

$M^X$

L_{1}^{X} o r L_{2}^{X}

$L_1^X or L_2^X$

M

$M$

M^{X}

$M^X$

X

$X$

M

$M$

L_{1}

$L_1$

M

$M$ adalah, akan ada beberapa ramalan sedemikian rupa sehingga tidak menyelesaikan kedua bahasa.

Joshua Grochow

Jawaban:

Saya pikir keduanya adalah NPI dengan asumsi yang lebih kuat (tapi jelas benar) bahwa NP tidak dalam "tak terhingga sering P" - yaitu, setiap algoritma waktu polinomial A dan setiap n cukup besar, A gagal menyelesaikan SAT pada input panjang n.

Dalam hal ini, bahasa-bahasa tersebut tidak dalam P, tetapi mereka juga tidak dapat melengkapi NP, karena jika tidak, pengurangan dari SAT ke bahasa L dengan lubang besar akan memberikan algoritma untuk SAT yang berhasil pada lubang ini.

Asumsi semacam itu juga diperlukan, karena kalau tidak bahasa bisa dalam P, atau NP-lengkap, tergantung di mana "panjang input mudah" berada.

Boaz Barak
sumber

@ Boas: Saya agak mengerti apa yang Anda maksud dengan "asumsi seperti itu perlu," tapi saya mengalami kesulitan memformalkan kebutuhan. Saya pikir satu membangun oracle

, tanpa terlalu banyak kesulitan, sehingga

, ada mesin poly-time

sehingga

memutuskan

pada panjang input yang tak terhingga banyaknya, namun

dan

adalah

-intermediate.

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

M

$M$

M^{X}

$M^X$

S A T^{X}

$SAT^X$

L_{1}^{X}

$L_1^X$

L_{2}^{X}

$L_2^X$

N P^{X}

$NP^X$

Joshua Grochow

Apa yang saya maksudkan adalah bahwa asumsi

tidak cukup dengan sendirinya untuk menunjukkan bahasa-bahasa ini adalah NP-intermediate, karena kita tidak dapat mengesampingkan kasus bahwa

tetapi ada algoritma yang memecahkan SAT tepat pada input bahwa

adalah non-sepele, dalam hal

akan di

dan

akan NPC.

N P \neq P

$NP\neq P$

N P \neq P

$NP\neq P$

L_{1}

$L_1$

L_{1}

$L_1$

P

$P$

L_{2}

$L_2$

Boaz Barak

@ Boas: Ah, tentu saja. Salah satu formalisasi dari ini adalah oracle

sehingga

tetapi

(yang saya percaya, mirip dengan oracle lainnya yang saya sebutkan, tidak terlalu sulit untuk dibangun). (PS - Dengan menggunakan @nama, itu memastikan bahwa pengguna lain diberitahu tentang komentar Anda.)

X

$X$

P^{X} \neq N P^{X}

$P^X \neq NP^X$

L_{1}^{X} \in P

$L_1^X \in P$

Joshua Grochow

@ Yosua: Jika

membiarkan

menjadi mesin waktu-Poli untuk

, maka

juga akan memecahkan

karena kasing tanpa permintaan ke oracle hanyalah kasing khusus. Jadi jika Anda dapat membuat

seperti yang Anda gambarkan, Anda membuktikan bahwa

maka saya benar-benar tidak mengerti bagaimana Anda bisa melakukannya.

L_{1}^{X} \in P

$L_1^X\in P$

M

$M$

L_{1}^{X}

$L_1^X$

M

$M$

L_{1}

$L_1$

X

$X$

P_{1} \in P

$P_1\in P$

Arthur MILCHIOR

@Joshua: tentang komentar pertama Anda di bawah Boaz Barak, jika

memecahkan

(pada tak terhingga banyaknya panjang input) maka saya kira Anda ingin Anda

setidaknya menjadi oracle untuk

. Tapi karena Anda dapat memiliki query untuk

di Anda rumus #, maka sebenarnya Anda bahkan perlu

menjadi oracle untuk

. Bagaimana Anda dapat menunjukkan bahwa definisi rekursif seperti itu benar? Sepertinya tidak jelas sama sekali bagi saya. (#Saya rasa SAT ^ X adalah SAT di mana X dapat juga ada dalam klausa)

M \in P^{X}

$M\in P^X$

S A T^{X}

$SAT^X$

X

$X$

S A T

$SAT$

X

$X$

X

$X$

S A T^{X}

$SAT^X$

Arthur MILCHIOR