Apakah NP dalam

Jawaban:

22

DTIME(npolylogn) dikenal sebagaiQP (quasi-polinomial).

Dipercaya secara luas bahwa NP⊄QP , meskipun merupakan pernyataan yang lebih kuat dariP≠NP .

Beberapa dugaan umum, seperti Hipotesis Waktu Eksponensial menyiratkan .NP⊄QP

BPR
sumber
6
Anda mengatakan bahwa "Beberapa dugaan umum ...". Apa yang lainnya selain ETH? Saya sangat tertarik karena saya saat ini sedang mengerjakan penghubungan NP dan QP - setidaknya saya harap begitu ...
Matt Groff
19

Alasan lain yang baik untuk meyakini adalah bahwa N P ⊆ Q P menyiratkan E X P = N E X P , dan yang terakhir dianggap sangat tidak mungkin. Implikasi ini dapat dibuktikan dengan argumen padding, lihat, misalnya, dalam bukti Proposisi 2 dalam makalah berikut:NP⊈QPNP⊆QPEXP=NEXP

H. Buhrman dan S. Homer, "Sirkuit superpolinomial , oracle yang hampir jarang dan hierarki eksponensial," Yayasan Teknologi Perangkat Lunak dan Ilmu Komputer Teoretis, Springer LNCS Vol. 652, 1992, hlm. 116-127, pdf

Andras Farago
sumber
8
Saya suka jawaban ini banyak. Mengingat jawaban RB, itu membuat saya bertanya-tanya apa, jika ada, adalah hubungan antara ETH dan asumsi . EXP≠NEXP
Joshua Grochow
1
@ Yosua Saya tidak mencari literatur tentang ini, tetapi, saya pikir, setiap pelanggaran ETH mungkin menyiratkan beberapa keruntuhan pada tingkat yang lebih tinggi. Saya kira, levelnya tergantung pada "seberapa kuat" ETH dilanggar, pelanggaran yang lebih kuat menghasilkan keruntuhan yang lebih dramatis. Seperti yang ditunjukkan dalam jawabannya, pelanggaran ETH kuat menyiratkan E X P = N E X P . Jika kita mengambil pelanggaran ringan, seperti asumsi bahwa N P berada dalam kelas subexponential lebih besar dari Q P , maka keruntuhan mungkin bergeser ke atas (misalnya, menggandakan kelas eksponensial atau bahkan lebih tinggi).NP⊆QPEXP=NEXPNPQP
Andras Farago
2
Thansk, tapi aku bertanya tentang langsung implikasi baik cara antara ETH dan . Kami sekarang memiliki dua jawaban - ETH menyiratkan N P ⊈ Q P dan N E X P ≠ E X P menyiratkan N P ⊈ Q P - dan saya ingin tahu apakah satu merupakan konsekuensi dari yang lain. EXP≠NEXPNP⊈QPNEXP≠EXPNP⊈QP
Joshua Grochow
2
Sayangnya, saya tidak menyadari implikasi langsung. Pada catatan lain, cukup menarik bahwa pelanggaran ETH dapat menghasilkan tidak hanya runtuh, tetapi juga pemisahan, dalam hal batas bawah sirkuit. Sebuah makalah dari Ryan Williams (pdf) membuktikan bahwa bahkan pelanggaran ETH sekecil apa pun akan menyiratkan tertentu sulit untuk membuktikan batas bawah sirkuit.
Andras Farago