Problemas completos com NEXP

31

Existem toneladas de problemas completos de NP e fontes que os coletam, por exemplo, consulte o livro de Garey e Johnson. Eu também estaria interessado em ver uma lista dos problemas completos do NEXP. Existe um disponível? Como suponho que não exista, abro esta pergunta (é suposto ser um wiki da comunidade? Não conheço essas coisas).

Idealmente, a lista deve abranger os diferentes "tipos" de problemas completos da NEXP, talvez com alguma redundância saudável para obter uma visão geral, mas sem se repetir demais. Por exemplo, é bom ter duas ou três versões sucintas diferentes do mesmo problema NP-completo como exemplos, se as codificações sucintas vierem em formas ligeiramente diferentes. Nem uma dúzia. Uma maneira limpa de adicionar a redundância é adicionando cláusulas do formulário "Também NEXP-complete se BLAH". Cláusulas do formulário "Permanece NEXP-completo se o gráfico de entrada tiver no máximo BLAH" também são bem-vindas.

Por fim, deixe-me adicionar uma preferência pessoal. Estou acima de tudo interessado em problemas completos de sabor "algébrico", se houver algum. Por exemplo, meu problema favorito # P-complete é o permanente pelo seu sabor algébrico. Espero que a igualdade NEXP = MIP também possa fornecer um bom problema algébrico completo de NEXP que eu não conheço.

slimton
fonte
2
Wiki da comunidade!
Dave Clarke
Como alguém o transforma em um wiki da comunidade?
slimton
Sinalize a postagem para obter atenção do moderador e peça para que ela se torne CW.
Kaveh
5
porquê NEXP? ou seja, por que não outra classe?
Suresh Venkat
1
Observe que a classe NEXP às vezes também é chamada de NEXPTIME. Isso pode revelar resultados adicionais ao usar mecanismos de pesquisa.
Hermann Gruber

Respostas:

26

Para alguns problemas de NP-complete, há uma variante SUCCINCT que é NEXP-complete.

Um exemplo é SUCCINCT HAMILTON PATH:

  • Um circuito booleano com 2 n entradas e uma saída representa um gráfico em 2 n vértices. Para determinar se existe uma aresta entre os vértices i e j , codificam i e j em n bits cada, e alimentar a concatenação para o circuito: existe uma aresta entre estes vértices sse a saída do circuito é verdadeiro. Dado tal circuito, existe um caminho de Hamilton no gráfico representado pelo circuito?

Da mesma forma, há SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Referência

  • Hana Galperin e Avi Wigderson (1983), "Succinct representations of graphs", Information and Control 56: 3, pp. 183–198.
Gareth Rees
fonte
17

Veja http://arxiv.org/abs/0905.2419 de Gottesman e Irani. Este é um exemplo interessante. Basicamente, todos estamos acostumados à idéia de que a satisfação com restrições pode ser um problema completo de NP (dependendo da geometria, etc ...). No entanto, eles consideram uma situação em que todas as restrições são dadas antecipadamente e a única coisa que você tem permissão variar é o tamanho do sistema. No entanto, isso ainda será difícil se você codificar o problema no tamanho do sistema. Ou seja, o problema é especificado fornecendo uma sequência de N bits, fornecendo o tamanho do sistema de 0 a 2 ^ N-1. Portanto, o tamanho do sistema é exponencialmente maior que o tamanho da entrada. Eles mostram que isso é completo para NEXP (e que o analógico quântico é completo para QMA_EXP).

hastings mate
fonte
15

Deixe-me começar com o canônico:

Dada uma máquina de Turing não determinística e um número inteiro n escrito em binário, existe um caminho de computação de M que aceita a cadeia vazia em no máximo n etapas?MnMn

Também NEXP-complete se for escrito em unário e solicitamos no máximo 2 n etapas.n2n

Slimton
fonte
15

2

Uma expressão regular é

  • 0 0
  • 1
  • ef
  • ef
  • e2

Essas expressões representam os conjuntos

  • eu(0 0)={0 0}
  • eu(1)={1}
  • eu(ef)=eu(e)eu(f)
  • eu(ef)={umabumaeu(e),beu(f)}
  • eu(e2)=eu(ee)

respectivamente.

Observe que, se permitirmos a estrela Kleene (zero ou mais cópias de uma expressão) como o quarto operador (além de união, concatenação e quadratura), o problema de reconhecer se duas expressões regulares representam idiomas diferentes se torna EXPSPACE completo .

LJ Stockmeyer, AR Meyer, " Problemas de palavras que requerem tempo exponencial ", 5ª STOC, 1973.

Sadeq Dousti
fonte
14

SCHÖNFINKEL – BERNAYS SAT

  • x1x2...y1y2...φφ

Referência

Gareth Rees
fonte
O inverso (insatisfação) é coNEXP-completo?
gigabytes
Eu sempre pensei que uma fórmula lógica de primeira ordem φ sem quantificadores é uma fórmula booleana. Não é? Mas, para uma fórmula booleana, seria ^ P_2 completa. As variáveis ​​em uma fórmula de Schönfinkel-Bernay podem ter outros valores além de verdadeiro e falso?
BeniBela
φ