Classe de complexidade NEXP

11

Eu tenho um problema que está no NEXP e também pode ser resolvido por uma TM alternada usando tempo exponencial e apenas uma alternância (iniciando em um estado existencial). $^{\text{NP}}$

Existe algo conhecido sobre NEXP ? É igual a NEXP ou alguma outra classe? Existem problemas completos além do genérico (dado uma máquina NEXP e uma palavra, ela aceita?). $^{\text{NP}}$ $^{\text{NP}}$

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

2

Confira o trabalho na hierarquia de tempo exponencial, por exemplo, ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf

5501

3

Observe que tem outro nome na literatura (com base na caracterização da alternância), a saber .

N E X P^{N P}

$NEXP^{NP}$

Σ_{2} E X P

$\Sigma_2 EXP$

Ryan Williams

7

Um problema está decidindo uma sentença aritmética do Presburger com um prefixo de quantidade existente (como aqui ). Problemas completos adicionais relacionados à teoria do banco de dados foram estudados aqui . $\text{NEXP}^{\text{NP}}$ $\exists^*\forall^*\exists^*$

Christoph Haase
fonte

5

$NEXP^{NP}$ é (provavelmente) maior que NEXP, pois podemos fazer perguntas de comprimento exponencial do oráculo. Que NP no poder é praticamente um NEXP lá, então, por exemplo. co-NEXP está contido em . $NEXP^{NP}$

domotorp
fonte

Você argumentou bem, em resposta à resposta de Peter Shor, que provavelmente é estritamente mais poderoso que o . Estou confuso, no entanto. Parece que analogamente isso significa que é maior que , embora (eu acho) sejam iguais. Onde estou errado aqui?

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

Os polinômios do @Huck são fechados em polinômios. Exponenciais não são. Portanto, posso alimentar o oráculo EXP com um argumento exponencialmente longo, e ele pode funcionar exponencialmente nesse argumento, que é duplamente exponencial no problema original.

Re

@domotorp Eu pensei ? Que tal ?

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 ....

O problema é que a entrada do oracle é preenchida, portanto, por exemplo, .

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 Eu não vejo o erro agora, mas parece que com essa lógica poderíamos provar que, para qualquer , temos , o que é um pouco suspeito ... Talvez você deva fazer isso como uma pergunta.

f (n)

$f(n)$

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

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

Domotorp 12/12

3

Expandindo um pouco o meu comentário acima: Se você tiver apenas uma consulta no Oracle (como no seu caso), segue-se do trabalho de Hemaspaandra, que seu problema está em . Isso significa que seu problema é Turing redutível a qualquer problema grave do . Eu acho que não se sabe se isso é verdade para todo o . $NP$ $P^{NE}$ $NE$ $NEXP^{NP}$

5501
fonte

1

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

Editado entre parênteses ...

Aubrey da Cunha
fonte

3

Os MNTs não funcionam assim. Os NTMs se dividem e, se uma cópia aceita, a coisa toda aceita. Quando você se separa, não consegue ver os resultados de suas cópias não det. Então, se eu fizesse uma consulta em uma máquina NP e retornasse imediatamente a resposta oposta, como você simularia isso?

Re

1

N P^{N P}

$NP^{NP}$

N P

$NP$

Ah sim. Ao simular uma consulta oracle, se o resultado correto for não, todas as ramificações retornarão não. Por outro lado, se o resultado correto for sim, pelo menos um ramo retornará sim. Em particular, alguns podem retornar não. Portanto, quando o @Mark sugere, você nega o resultado da consulta, provavelmente obtém falsos positivos.

Aubrey da Cunha

Classe de complexidade NEXP

Respostas: