Clase de complejidad NEXP

11

Tengo un problema que está en NEXP y también se puede resolver con una TM alterna usando tiempo exponencial y solo una alternancia (comenzando en un estado existencial). $^{\text{NP}}$

¿Se sabe algo sobre NEXP ? ¿Es igual a NEXP o alguna otra clase? ¿Hay problemas completos además del genérico (dada una máquina NEXP y una palabra, ¿acepta?). $^{\text{NP}}$ $^{\text{NP}}$

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

2

Vea el trabajo sobre la jerarquía de tiempo exponencial, por ejemplo ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Obsérvese que

tiene otro nombre en la literatura (basado en la caracterización alternancia), a saber

.

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

$\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
fuente

5

$NEXP^{NP}$ $NEXP^{NP}$

domotorp
fuente

N E X P^{E X P}

$NEXP^{EXP}$

N E X P

$NEXP$

N P^{P}

$NP^P$

N P

$NP$

77

@Huck Los polinomios están cerrados bajo polinomios. Los exponenciales no lo son. Entonces, puedo alimentar al oráculo EXP con un argumento exponencialmente largo, y puede funcionar exponencialmente en ese argumento, que es doblemente exponencial en el problema original.

Mark Reitblatt

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}$

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}})$

f (n)

$f(n)$

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

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

3

$NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
fuente

1

$NEXP^{NP}$ $poly(2^{n^k})=O(2^{n^{k+1}})$ $NEXP$

Editado entre paréntesis ...

Aubrey da Cunha
fuente

3

Las MNA no funcionan así. Las MNA se dividen, y si una copia acepta, todo lo acepta. Cuando se divide, no puede ver los resultados de sus copias que no son det. Entonces, si hice una consulta a una máquina NP e inmediatamente devolví la respuesta opuesta, ¿cómo simularía eso?

Mark Reitblatt

1

N P^{N P}

$NP^{NP}$

N P

$NP$

Ah, sí. Al simular una consulta oracle, si el resultado correcto es no, todas las ramas devolverán no. Por otro lado, si el resultado correcto es sí, entonces al menos una rama devolverá sí. En particular, algunos pueden devolver no. Por lo tanto, cuando, como sugiere @Mark, usted niega el resultado de la consulta, es probable que obtenga falsos positivos.

Aubrey da Cunha

Clase de complejidad NEXP

Respuestas: