Classe de complexidade NEXP
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).NPNP
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?).NPNPNPNP
Confira o trabalho na hierarquia de tempo exponencial, por exemplo, ecommons.library.cornell.edu/bitstream/1813/6617/1/86-777.pdf
Observe que tem outro nome na literatura (com base na caracterização da alternância), a saber . NEXPNPNEXPNPΣ2EXPΣ2EXP
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 .NEXPNPNEXPNP∃∗∀∗∃∗∃∗∀∗∃∗
NEXPNPNEXPNP é (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 .NEXPNPNEXPNP
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? NEXPEXPNEXPEXPNEXPNEXPNPPNPPNPNP
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.
@domotorp Eu pensei ? Que tal ? NEXPNP⊆NEXPEXP=NEXPNEXPNP⊆NEXPEXP=NEXPEXPEXPEXPEXP
O problema é que a entrada do oracle é preenchida, portanto, por exemplo, . DTIME(2n)DTIME(2n)=DTIME(22n)DTIME(2n)DTIME(2n)=DTIME(22n)
@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)DTIME(f(n))⊂P/polyDTIME(f(n))⊂P/poly
— Domotorp 12/12
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 .NPNPPNEPNENENENEXPNPNEXPNP
NEXPNPNEXPNPpoly(2nk)=O(2nk+1)poly(2nk)=O(2nk+1)NEXPNEXP
Editado entre parênteses ...
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?
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.