Problemas 2-NEXPTIME-complete

Temos um problema e encontramos um algoritmo que parece ser 2-nexptime.

Eu gostaria de encontrar problemas conhecidos de 2 nexptime-complete para encontrar um limite inferior.

Encontrei na literatura principalmente dois desses problemas:

• se o PCP como uma solução de tamanho menor que$2^{2^n}$
• e o problema do cultivo de um quadrado de tamanho$2^{2^n}$

No entanto, não consegui codificar esses problemas nos meus. Então, eu gostaria de conhecer outros problemas com 2 NEXPTIME-complete, primeiro para ter mais intuição nessa classe e, em segundo lugar, na melhor das hipóteses, provar um limite inferior.

Não forneço aqui o problema de propósito para ter uma visão geral ampla do 2-NEXPTIME.

obrigado

O problema óbvio do N2Exp é, obviamente, o problema de aceitação de palavras para máquinas de Turing não determinísticas com limite de tempo de 2exp. Usar isso pode ser tão difícil / fácil quanto a telha 2exp, porque a simulação de uma máquina de Turing em essência também exige que você defina uma grade dupla exponencialmente grande (2exp: muitas configurações de fitas de memória de 2exp cada) que são preenchidas de uma maneira não determinística. Na prática, mostrar limites inferiores do N2Exp geralmente se resume a construir uma grade (e garantir que ela não seja uma árvore ou algo com estrutura insuficiente). O "N" (não determinismo) geralmente é uma parte inerente do problema e não é tão difícil de obter quando você tem uma grade grande o suficiente (se não, talvez seja possível disparar para 2exp no início).

Outro problema prático completo do N2ExpTime é o raciocínio na lógica de descrição expressiva (DL). Em particular, o DL que está subjacente ao padrão W3C OWL 2 Web Ontology Language é N2ExpTime-complete (Yevgeny Kazakov: RIQ e SROIQ são mais difíceis que o SHOIQ. KR 2008: 274-284). Agora, esse provavelmente não é um problema que você deseja usar nas reduções, pois a definição da lógica é um pouco difícil de usar devido a seus muitos recursos. A prova de limite inferior real para também foi feita pela redução para a telha de 2 exp. No entanto, dependendo do seu problema, a construção dada para pode ser inspiradora para ver como criar grades tão grandes.$\mathcal{SROIQ}$$\mathcal{SROIQ}$$\mathcal{SROIQ}$

O lado a lado também mostra outro padrão geral: o N2Exp realmente é como o NP, você só precisa encontrar uma maneira de codificar instâncias de problemas ainda maiores com muita eficiência. Em princípio, você pode tentar ampliar qualquer problema de NP. A razão pela qual a telha é boa é que você só precisa dimensionar o tamanho da grade nesse caso (que é bastante uniforme).

Por outro lado, se o seu problema possivelmente só estiver completo em 2ExpTime, você poderá obter uma simulação de máquina de Turing alternada com espaço exponencial . Se você tiver problemas para criar uma grade 2exp, mas conseguir tamanhos exponenciais, vale a pena tentar.