Kelas Kompleksitas NEXP

11

Saya memiliki masalah yang ada di NEXP dan juga dapat diselesaikan dengan TM bergantian menggunakan waktu eksponensial dan hanya satu pergantian (mulai dalam keadaan eksistensial). $^{\text{NP}}$

Adakah yang diketahui tentang NEXP ? Apakah setara dengan NEXP atau kelas lain? Apakah ada masalah lengkap selain yang umum (diberi mesin NEXP dan sebuah kata, apakah itu menerimanya?). $^{\text{NP}}$ $^{\text{NP}}$

cc.complexity-theory reference-request complexity-classes nexp Hsien-Chih Chang 張顯之
sumber

2

Lihatlah karya pada hierarki waktu eksponensial, misalnya ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Perhatikan bahwa memang memiliki nama lain dalam literatur (berdasarkan karakterisasi pergantian), yaitu .

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

Sebuah alam masalah -Lengkap adalah memutuskan hukuman Presburger aritmatika dengan -quantifier awalan (seperti yang ditunjukkan di sini ). Masalah lengkap lebih lanjut terkait dengan teori database telah dipelajari di sini . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
sumber

5

adalah (mungkin) lebih besar dari NEXP, karena kita dapat mengajukan pertanyaan panjang eksponensial dari oracle. NP dalam kekuasaan itu praktis NEXP di sana, jadi mis. co-NEXP terkandung dalam . $NEXP^{NP}$ $NEXP^{NP}$

domotorp
sumber

Anda berpendapat baik dalam menanggapi jawaban Peter Shor yang

kemungkinan ketat lebih kuat daripada

. Tapi saya bingung. Tampaknya analog ini harus berarti bahwa

lebih besar dari

, meskipun (saya pikir) mereka sama. Di mana saya salah di sini?

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

Huck Bennett

7

@Huck Polinomial ditutup di bawah polinomial. Eksponensial tidak. Jadi, saya bisa memberi makan EXP oracle argumen panjang yang eksponensial, dan itu bisa melakukan eksponensial dalam argumen itu, yang dua kali lipat eksponensial dalam masalah aslinya.

Mark Reitblatt

@domotorp Saya pikir

? Bagaimana dengan

?

N E X P^{N P} \subseteq N E X P^{E X P} = N E X P

$NEXP^{NP}\subseteq NEXP^{EXP}=NEXP$

E X P^{E X P}

$EXP^{EXP}$

T ....

Masalahnya adalah input dari oracle akan diisi, jadi misalnya

.

D T I M E (2^{n})^{D T I M E (2^{n})} = D T I M E (2^{2^{n}})

$DTIME(2^n)^{DTIME(2^n)}=DTIME(2^{2^{n}})$

domotorp

@ Turbo Saya tidak melihat kesalahan sekarang tetapi sepertinya dengan logika ini kita bisa membuktikan bahwa untuk setiap

kita punya

, yang merupakan agak mencurigakan ... Mungkin Anda harus menanyakan ini sebagai pertanyaan.

f (n)

$f(n)$

D T I M E (f (n)) \subset P / p o l y

$DTIME(f(n))\subset P/poly$

domotorp

3

Memperluas komentar saya di atas sedikit: Jika Anda hanya memiliki satu query ke -oracle (seperti dalam kasus Anda), maka berikut dari karya Hemaspaandra, bahwa masalah Anda di . Ini berarti bahwa masalah Anda adalah Turing dapat direduksi ke masalah -hard. Saya pikir itu tidak diketahui apakah ini benar untuk semua . $NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
sumber

1

Query terbesar sebuah mesin dapat membuat oracle adalah eksponensial dalam panjang input. Kekuatan oracle hanya polinomial dalam hal ini, yang juga harus eksponensial. Dengan kata lain, . Oleh karena itu, mesin harus dapat mensimulasikan mesin Anda serta oracle. $NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Diedit untuk tanda kurung ...

Aubrey da Cunha
sumber

3

NTM tidak berfungsi seperti itu. NTM terpecah, dan jika satu salinan menerima semuanya menerima. Ketika Anda berpisah, Anda tidak bisa melihat hasil salinan non-det Anda. Jadi, jika saya membuat satu permintaan ke mesin NP, dan segera mengembalikan jawaban yang berlawanan, bagaimana Anda mensimulasikan itu?

Mark Reitblatt

1

N P^{N P}

$NP^{NP}$

N P

$NP$

Ah iya. Saat mensimulasikan permintaan oracle, jika hasil yang benar adalah tidak, maka semua cabang akan mengembalikan no. Di sisi lain, jika hasil yang benar adalah ya, maka setidaknya satu cabang akan mengembalikan ya. Secara khusus, beberapa mungkin mengembalikan no. Jadi, ketika seperti yang disarankan @Mark, Anda meniadakan hasil kueri, Anda cenderung mendapatkan hasil positif palsu.

Aubrey da Cunha

Kelas Kompleksitas NEXP

Jawaban: