Sastra di sekitar NP vs EXPTIME

Bahkan jika itu bukan poin penting, saya tidak melihat literatur tentang pertanyaan ini. Apakah ada hasil relativisasi?

Tidakkah cukup mudah untuk membuktikan inklusi yang ketat dengan mengadaptasi teorema hierarki waktu non-deterministik dengan mengeksplorasi semua jalur yang mungkin dari mesin NP?

cc.complexity-theory complexity-classes Ludovic Patey
sumber

Sangat mudah untuk membuktikan pemisahan oracle antara NP dan EXP. Ada teorema hierarki waktu non-deterministik yang memberi tahu kita bahwa NP secara ketat terkandung dalam NEXP. Saya tidak melihat bagaimana itu bisa disesuaikan dengan NP vs EXP.

Robin Kothari

@Robin Ya, tentu saja, sebuah ramalan seperti yang menyiratkan bahwa . Tetapi karena saya tidak menemukan oracle sehingga , maka jika tidak ada, bukti bisa menjadi relatif.

N P^{A} \neq P S P A C E^{A}

$NP^A \neq PSPACE^A$

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

$NP^A \neq EXP^A$

N P^{B} = E X P^{B}

$NP^B = EXP^B$

N P \neq E X P

$NP \neq EXP$

Ludovic Patey

Kebun Binatang Complexity ( qwiki.stanford.edu/index.php/Complexity_Zoo ) mengatakan: ... Ada oracle yang berkaitan dengan [Hel84a], [Hel84b], [Kur85], [Hel86], .. .. Lihat misalnya Dua nubuat yang memaksa krisis besar ( people.cs.uchicago.edu/ ~fortnow / papers / nexp.ps )

E X P = N P = Z P P

$EXP = NP = ZPP$

Marzio De Biasi

@Vor, @Robin, saya pikir ini harus menjadi jawaban

Suresh Venkat

Jawaban:

The Kompleksitas Zoo mengatakan:

... Ada oracle yang berhubungan dengan [Hel84a], [Hel84b], [Kur85], [Hel86], .... $EXP=NP=ZPP$

Lihat misalnya Dua nubuat yang memaksa goncangan besar .

Mungkin oracle asli yang digunakan oleh Dekhtyar kurang kuat (dan lebih sederhana): Tentang relativisasi kelas kompleksitas deterministik dan nondeterministik di Proc. Yayasan Matematika CS 1977 ... tapi saya tidak punya makalahnya.

Marzio De Biasi
sumber

Terima kasih. Nama pasti makalah Dekhtyar adalah Pada relativisasi kelas kompleksitas deterministik dan nondeterministik.

Ludovic Patey