Problemas que são decidíveis, mas não podem ser verificados em tempo polinomial

Enquanto trabalhava em um projeto não relacionado para a Suresh, deparei-me recentemente com alguns trabalhos realizados por Page e Opper sobre sistemas compostos pelo usuário e uma parte de seu trabalho discutiu brevemente problemas que não podem ser verificados em tempo polinomial. Não consegui encontrar muita informação sobre outros problemas que não podem ser verificados no tempo polinomial ou na análise de um problema desse tipo. Fiquei imaginando se algum de vocês conhecia algum desses problemas e / ou como analisá-los.

Como afirmado nos comentários, a melhor maneira de formular esta pergunta é: que problemas são decidíveis, exceto fora do NP?

cc.complexity-theory complexity-classes Scott R
fonte

Problemas fora de

N P

$\mathsf{NP}$ ?

Hsien-Chih Chang,

Sim, especificamente aqueles que podem ser verificados, mas não em tempo polinomial.

Scott R

Você pode ver esses problemas completos do

N E X P

$\mathsf{NEXP}$ e fornecer reduções a partir deles. cstheory.stackexchange.com/questions/3297/…

Hsien-Chih Chang #: 29710

O problema não hamiltoniano não pode ser verificado no tempo polinomial, a menos que coNP = NP.

Mohammad Al-Turkistany 29/11

@turkistany @ Hsien-Chih Chang, por que não postar seus comentários acima como respostas.

Kaveh

Respostas:

O mais importante a ser percebido do ponto de vista teórico é que o NP é na verdade uma classe relativamente pequena de todas as linguagens decidíveis. Dito isto, muitos dos problemas interessantes da ciência da computação estão dentro do NP, para que eles recebam muita atenção.

$NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$

As classes PH, PSPACE e EXP contêm muitos dos problemas "interessantes" no , que é o que suponho que você esteja perguntando nesta pergunta. Até agora, o NEXP recebeu toda a atenção porque é o único confinamento adequado que podemos provar (pelo teorema da hierarquia de tempo não determinístico, como mencionei acima). $R \setminus NP$ $NP \subsetneq NEXP$

Aqui estão alguns exemplos concretos interessantes de problemas em algumas dessas outras classes:

Determinar se um jogador tem uma estratégia vencedora no xadrez ou no Go (adaptado aos tabuleiros nxn) é EXP-completo.
MAJ-SAT, o problema de determinar se mais da metade das atribuições para as variáveis em uma fórmula booleana satisfazem essa fórmula, está no PSPACE. Também é completo para a classe menor PP.
CLIQUE EXATO, o problema de determinar se a maior clique em um gráfico é de tamanho exatamente k, está em , parte do segundo nível da hierarquia polinomial. $\Sigma_2^P$

Huck Bennett
fonte

Por curiosidade, a classe de problemas recursivos é o significado "padrão" para R? Isso é o que o Zoo parece indicar, mas eu vi R como sinônimo de RP, muitas vezes o suficiente para que essa foi a minha leitura instintiva quando vi R \ NP ...

Steven Stadnicki

Eu acho que é notação padrão. Ele se encaixa muito bem com "RE" e "co-RE".

Huck Bennett 30/11

O xadrez e o Go geralmente são EXPTIME completos devido a regras de repetição.

Geoffrey Irving

@GeoffreyIrving: Você está certo, obrigado. Fixo. Não tenho certeza do que eu (por engano) tinha em mente quando escrevi isso, mas há "subproblemas" do Go, como LADDERS, que são completos no PSPACE: link.springer.com/chapter/10.1007%2F3-540 # 45579-5_16

Huck Bennett

Bem, se você tivesse um oráculo do PSPACE em mãos, provavelmente poderia jogar bastante bem. :)

Geoffrey Irving

Estendendo o comentário de Hsien-Chih Chang, todos os problemas difíceis da NEXP não podem estar no NP, portanto, por definição, não podem ser verificados no tempo polinomial.

Pode-se usar o teorema da hierarquia de tempo não determinístico para ver que NP está estritamente contido no NEXP. Portanto, podemos ter certeza de que, dado qualquer problema difícil da NEXP, ele não está no NP ou seríamos levados a uma contradição.

chazisop
fonte

Observe que Buhrman, Fortnow e Santhanam constroem um oráculo em relação ao qual NEXP é infinitamente frequentemente contido em NP (no entanto, dx.doi.org/10.1007/978-3-642-02927-1_18 ). Em outras palavras, existe um oráculo em relação ao qual, para cada problema NEXP L, existe um problema L 'em NP, de modo que L é igual a L' em infinitos comprimentos de entrada. Portanto, embora inúmeras instâncias de um problema completo de NEXP não possam ser verificadas no tempo da poli, não podemos (de forma relativável) descartar a possibilidade de que inúmeras outras instâncias possam ser verificadas no tempo da poli.

21810 Joshua Grochow