Quão difícil é a simulação exata de algoritmos e uma operação relacionada em classes de complexidade

Teaser

Como o problema é longo, aqui está um caso especial que captura sua essência.

Problema: Seja A um algoritmo detrminístico para o 3-SAT. É o problema de simular completamente o algoritmo A (em todas as instâncias do problema). Espaço P difícil?

(Mais precisamente, existem razões para acreditar que esta tarefa é difícil no espaço P, faz alguma coisa nessa direção seguir conjecturas CC comuns e há esperança de provar que essa tarefa é difícil no X para alguma classe de complexidade X que se presume ser estritamente acima de NP.)

Perguntas relacionadas : are-pspace-complete-problems-inerentemente-menos tratável-que-np-complete-problems ;

ATUALIZAÇÃO EDITADA : Existem várias interpretações para "Simular completamente A". E pode haver diferentes respostas interessantes de acordo com a interpretação. (Também Ryan Williams propôs uma interpretação para simular um algoritmo não determinístico.) Para uma certa maneira de associar um problema de decisão à tarefa computacional "Simular completamente A", Joe Fitzsimons encontrou um algoritmo A para o qual esse problema de decisão associado ainda está em NP . Se "simular completamente" se refere à capacidade de gerar todo o registro do computador em uma determinada etapa $i$ então, para o algoritmo de Joe, parece que $P^{NP}$ é o necessário. Para esta versão (eu acho, mas não tenho certeza), a resposta de Ryan esboça um $P^{NP}$ argumento de dureza. Joe observou que, se você é obrigado a fornecer todos os registros (o que não é mais um problema de decisão), não é de surpreender que você precise avançar e as classes de complexidade não sejam as mesmas.

De qualquer forma, se precisarmos de saída do estado dos registros em um passo prescrito $i$ , em seguida, as respostas de Ruan e Joe sugere (mas, novamente, eu não tenho certeza sobre isso) que $NP^+$ é essencialmente $P^{NP}$ . Podemos spaculate que por esta interpretação da operação empurra para cima um passo maior no hiearachy polinomial, e que $PH^+ =PH$ .

Em qualquer caso, por essas interpretações, a resposta para minha pergunta inicial é NÃO .

Eu tinha uma interpretação mais drástica para "simular completamente um algoritmo A" em mente. (Mas talvez a interpretação de Joe e Ryan seja mais interessante.) Minha interpretação ao "simular completamente o algoritmo A" é que você supera o estado dos registros a cada passo . Em particular, se o algoritmo não for polinomial, sua saída também não será polinomial. Sob essa interpretação drástica, perguntei-me se deveríamos acreditar que, para todo algoritmo A, é difícil para o P-SPACE, e o que podemos provar. $i$ $C_A$

Motivação:

Esta questão foi motivada por uma palestra de Paul Goldberg ( slides , vídeo , artigo ) descrevendo um artigo com Papadimitriou e Savani. Eles mostraram que o espaço P é completo para encontrar qualquer equilíbrio calculado pelo algoritmo de Lemke-Howson. O problema para encontrar algum ponto de equilíbrio é apenas completo com o PPAD. Essa lacuna é bastante surpreendente e resultados semelhantes já estão descritos no conhecido artigo de Papadimitriu: A complexidade da argumentação de paridade e outras provas ineficientes da existência (1991) . (Sabe-se que os problemas completos do PPAD não podem ser nem NP-difíceis (a menos que coisas terríveis aconteçam, então isso está muito distante no mundo da complexidade em comparação ao espaço P)).

Sobre o que é a pergunta

Minha pergunta é sobre lacunas semelhantes para problemas de complexidade computacional ainda mais antigos e clássicos. (Talvez isso já seja familiar.)

Dado um problema computacional, podemos distinguir entre três questões

a) Resolva o problema algoritmicamente

b) Alcance a mesma solução que um algoritmo específico A

c) Simule todo o algoritmo A

É claro que c) é pelo menos tão difícil quanto b) que é pelo menos tão difícil quanto a). Os resultados mencionados acima mostram uma lacuna entre a dificuldade computacional das tarefas a) eb) para o problema dos equilíbrios computacionais. Gostaríamos de entender a situação (e principalmente a diferença entre a) e c)) para outros problemas computacionais.

A questão:

A forma básica da pergunta com um exemplo

Começamos com um problema computacional, Problema X

Um exemplo pode ser

Problema X: Resolva uma instância do SAT com n variáveis

nós também especificamos

A: um algoritmo que executa o Problema X

e colocamos um novo problema

Problema Y: simule exatamente o algoritmo A

e estamos interessados na dificuldade computacional do Problema Y. Desejamos entender a classe de tais problemas Y para todos os algoritmos A que resolvem o Problema X original. Especialmente, queremos saber quão fácil pode ser o problema Y (ou quão difícil deve ser) be) se for permitido escolher o algoritmo A à vontade.

A operação proposta em classes de complexidade

Comece com uma classe de complexidade descrita por alguma tarefa computacional. Dado um algoritmo A para executar cada instância desta tarefa computacional, considerar uma nova classe de complexidade que é descrito pela tarefa computacional de completamente simular . Então podemos (espero) definir um "ideal" de classes de complexidade $C$ $C_A$ $A$

para todos os algoritmos A}. $C^+ = \{C_A:$

Se permitirmos que descreva o que um computador digital pode fazer em tempo polinomial (portanto, não quero restringir a atenção, por exemplo, a problemas de decisão), é o ideal estendido pelo próprio $P$ $P^+$ $P$

Finalmente, minhas perguntas

Minhas perguntas são:

1) A definição faz sentido (no sentido amplo da palavra sentido). É bem conhecido ou o mesmo que (ou semelhante a) alguma coisa bem conhecida. (Minha formulação foi informal e, em particular, quando passamos de problemas específicos como o SAT para uma classe de complexidade como o NP, precisamos nos preocupar com várias coisas que negligenciei.)

As próximas duas perguntas assumem que a definição pode fazer sentido ou ser recuperada para fazer sentido.

2) Suponha que nos equiparmos com todas as conjecturas padrão em relação à conformidade computacional. Podemos dizer o que deve ser para algumas classes familiares de complexidade. (Por exemplo, , = P-espaço, ..)? EDIT: Várias pessoas apontaram que $C^+$ $C=NP$ $C$ . Então> podemos perguntar o que é ? é ? $PSPACE^+=PSPACE$ $(P^{NP})^+$ $PH^+=PH$

Podemos adivinhar quais são as classes de compexity para que $C$ seja o ideal estendido por ? $C^+$ $C$

Portanto, a questão de quão fácil pode a tarefa computacional de simular um algoritmo A para 3-SAT (quando podemos escolher o algoritmo para torná-lo o mais fácil possível) é um caso especial interessante.

3) Há esperança de provar algo sobre esta operação?

Obviamente, se você provar que todas as classes de complexidade em têm espaço no espaço P, isso mostrará que implica , o que (eu acho) seria um resultado enorme e altamente inesperado . Mas se você mostrar que todas as classes de complexidade em são difíceis de dizer no terceiro nível da hierarquia polinomial (por exemplo, ), isso implicaria apenas coisas que já sabemos, coisas que decorrem do fato de faz com que o PH entre em colapso. $NP^+$ $P=NP$ $P=PSPACE$ $NP^+$ $\Delta_3^{\bf P}$ $P=NP$

cc.complexity-theory big-picture structural-complexity Gil Kalai
fonte

Pergunta interessante! Mas: "É claro que a) é pelo menos tão difícil quanto b) que é pelo menos tão difícil quanto c)." A ordem não deveria ser o contrário?

Bart Jansen

É possível incluir um link ou talvez uma breve descrição do que significa "simular todo o algoritmo A". Como, qual é a diferença entre 'simular' e 'executar' neste caso? É possível simular um algoritmo mais rápido que o tempo de execução?

Artem Kaznatcheev

Caro Artem, simulando um algoritmo em uma instância específica, quero dizer descrevendo toda a evolução do algoritmo. (Talvez seja como "executar" o algoritmo.) Você não pode simular o algoritmo mais rapidamente do que o tempo de execução. Não é uma noção padrão (pelo que sei), por isso não posso fornecer links ou referências (mas espero obter links e referências). A simulação do algoritmo é diferente do que apenas a tarefa computacional de "fornecer a mesma saída que o algoritmo A", que está relacionada à motivação e à tarefa b) descritas na pergunta.

Gil Kalai

Caro Gil, Não estou conseguindo entender por que não podemos simular um algoritmo

com recursos da mesma ordem que

usa. A menos que alguns recursos sejam mais restritos, podemos apenas simular o que

fizer. Deixe-me ver se eu entendi a parte motivação corretamente: Nós temos um problema

na classe

é um algoritmo possivelmente fora

resolver

. Apesar de encontrar uma solução para

A

$A$

A

$A$

A

$A$

Q

$Q$

C

$C$

A

$A$

C

$C$

Q

$Q$

Q

$Q$ pode ser feito em

, encontrar um das soluções que

C

$C$

A

$A$ achados podem ter complexidade fora

C

$C$ . Estou entendendo a parte da motivação da postagem corretamente?

Kaveh

Sim, sim, estamos assumindo que o algoritmo A é determinístico! Não tenho uma intuição clara por que deveríamos esperar que simular todo algoritmo determinístico do 3-SAT seja difícil no espaço P. Esta é a questão! Eu queria ver o que os especialistas pensam.

Gil Kalai

Respostas:

Problema: Seja A um algoritmo determinístico para 3-SAT. O problema de simular completamente o algoritmo A (em todas as instâncias do problema) P-Space é difícil?

Não entendo a afirmação deste problema. Mas acho que existe uma maneira natural de formalizar sua pergunta mais geral que pode lançar um pouco de luz sobre ela. Talvez eu esteja completamente errado, mas espero que você ainda encontre algo interessante para ler aqui.

1) A definição faz sentido (no sentido amplo da palavra sentido). É bem conhecido ou o mesmo que (ou semelhante a) alguma coisa bem conhecida. (Minha formulação foi informal e, em particular, quando passamos de problemas específicos como o SAT para uma classe de complexidade como o NP, precisamos nos preocupar com várias coisas que negligenciei.)

Uma maneira de entender a tarefa simular exatamente o algoritmo $Y$ é a seguinte. Vamos consertar o modelo como sendo máquinas de Turing de uma fita para simplificar; o que direi pode se aplicar a qualquer modelo computacional típico.

Para cada algoritmo de e de entrada , podemos definir a sua história computação : inteiros Dado e que variam de ao tempo de execução de , é igual o conteúdo da ésima célula da fita da máquina de Turing na entrada na etapa de tempo ésima célula da $Y$ $x$ $H_Y(x,i,j)$ $i$ $j$ $0$ $Y$ $H_Y(x,i,j)$ $j$ $Y$ $x$ $i$ . (E se a cabeça da fita estiver lendo $j$ $i$ th passo, incluem que também, juntamente com o estado da máquina.) Claro, histórias de computação vir para cima o tempo todo em teoria da complexidade.

Agora, alguém poderia argumentar que qualquer algoritmo que pode decidir a linguagem

$C_Y = \{(x,i,j,\sigma)~|~H_Y(x,i,j)=\sigma\}$

(ou simular a função em todas as entradas) está resolvendo a tarefa exatamente algoritmo simular , porque tem a capacidade de imprimir cada pequena parte de cada cálculo possível do algoritmo . Certamente, dado um oráculo para poderia-se fazer uma simulação passo a passo de $H_Y$ $Y$ $Y$ $C_Y$ $Y$ .

2) Suponha que nos equipemos com todas as conjecturas padrão em relação à complexidade computacional. Podemos dizer o que C + deve ser para algumas classes familiares de complexidade. (Por exemplo, C = NP, C = P-espaço, ..)? Podemos adivinhar quais são as classes de complexidade C para que C + seja o ideal estendido por C?

Essa ainda é uma pergunta interessante, sob a proposta acima. Para classes de tempo determinísticas, nada muda. é apenas : podemos decidir em polytime, para cada algoritmo polytime. Da mesma forma . Também é ainda . Para classes de complexidade de tempo não determinísticas, a situação se torna mais interessante. Nesse caso, um algoritmo pode ter vários históricos de computação, então $P^+$ $P$ $C_Y$ $EXP^+ = EXP$ $PSPACE^+$ $PSPACE$ $Y$ $H_Y$ não está mais bem definido. No entanto, ainda queremos imprimir um histórico de computação, portanto, nossa "simulação exata" teria que isolar um histórico de cálculo não determinístico específico e, em seguida, imprimir seus valores. Para um algoritmo , pode-se dizer que : podemos usar o oráculo para pesquisar binariamente o "primeiro" histórico de computação que aceita (em ordem lex) e, depois de o ter obtido, imprima os bits relevantes. Para um algoritmo , pode-se dizer $NP$ $Y$ $C_Y \in P^{NP}$ $NP$ $NEXP$ $Y$ $C_Y \in EXP^{NP}$ , por razões semelhantes.

Podemos colocar em uma classe menor? Eu não sei. Observe que não podemos simplesmente redefinir $NP^+$

{existe um tal que $C_Y =$ $(x,i,j,\sigma)~|~$ $H_Y$ $H_Y(x,i,j)=\sigma$ }

tentar colocar em , porque precisamos que a sequência do histórico seja a mesma para todos os quádruplos que envolvem , a fim de "simular exatamente o algoritmo $C_Y$ $NP$ $x$ $Y$ ".

De qualquer forma, esse problema de não ser possível "imprimir uma testemunha" para um cálculo sem ir para surge em algumas situações, como a complexidade do circuito. Se tem circuitos de tamanho polinomiais, em seguida, é-o também o caso em que para cada não-determinístico tempo $NEXP$ $EXP^{NP}$ $NEXP$ $C_Y \in P/poly$ $2^{n^k}$ $Y$ ? Impagliazzo, Kabanets e Wigdersonresponderam afirmativamente a essa pergunta em 2001. A prova deles é extremamente interessante, invocando ferramentas de des randomização e diagonalização (por que a des randomização seria necessária para esse resultado?) e é um teorema muito útil para provar limites inferiores do circuito para Funções $NEXP$

Existe esperança para realmente provar algo sobre esta operação?

Talvez ... isso dependa se você está satisfeito com a formalização da sua pergunta acima. Para um determinista 3-SAT algoritmo , penso que a acima simulação exacta de problema seria -Hard, onde é o tempo polinomial com uma consulta para . (. A sintaxe irritante de Stackexchange exige que write I (1) em vez da alternativa Anteriormente eu disse deve ser -Hard, mas eu não tenho certeza dos detalhes:. Você pode ver como generalizar a seguir) $Y$ $Y$ $P^{NP(1)}$ $P^{NP(1)}$ $NP$ $C_Y$ $P^{NP}$

Damos um polytime redução muitos-ona a partir de cada para . Dada uma tal , deixar ser um reconhecendo máquina que faz um único consulta. WLOG, essa consulta é uma fórmula SAT. Também WLOG, a consulta SAT pode ser "adiada" até a última etapa da computação, no seguinte sentido: existe um algoritmo polinomial de tempo que imprime uma fórmula e o bit , de modo que, para todos os , $L \in P^{NP(1)}$ $C_Y$ $L$ $M$ $L$ $NP$ $A(x)$ $F$ $b$ $x$

aceita sse de tal modo que ( XOR $M(x)$ $A(x)=(F,b)$ $SAT(F)$ $b$ ) = 1.

( pode rejeitar se for satisfatório ou aceitar; o bit $M$ $F$ $b$ captura isso.)

Por uma questão de simplicidade, digamos que quando termina seu cálculo, move sua cabeça de fita para a célula 1, escreve "aceita" ou "rejeita" nessa célula e faz um loop para sempre. Em seguida, perguntando se para suficientemente grande nos dirá se for aceite. (Em geral, precisamos apenas que seja eficiente calcular a instância de que nos dirá.) Observe que isso já mostra que é ambos $Y$ $(F,T,1,accept) \in C_Y$ $T$ $F$ $y$ $C_Y$ $C_Y$ $NP$ -Hard esatisfatório. -Hard; o último é verdadeiro porque se nãofor $coNP$ $(F,T,1,reject) \in C_Y$ $F$

A redução final de para é: dado , execute obtendo . Se então a saída , caso contrário, se saída $L$ $C_Y$ $x$ $A(x)$ $(F,b)$ $b=0$ $(F,T,1,accept)$ $b=1$ $(F,T,1,reject)$ .

Para cada que estamos produzindo (em tempo polinomial) tal que aceite se $x$ $y$ $M(x)$ $y \in C_Y$ .

(Obrigado a Joe por exigir que eu seja mais claro sobre esta parte.)

Mas eu não ver (por exemplo) como obter -hardness. Para reduzir -SAT ao problema, parece que você precisará escrever uma instância SAT 3-CNF que simule seu algoritmo determinístico dentro dela (onde está resolvendo Tautologias em vários subproblemas). Mas como não tem um prazo determinado, esse 3-CNF pode ser enorme, portanto você não obtém necessariamente uma redução no tempo polinomial. A menos que esteja faltando alguma coisa. $\Sigma_2 P$ $\Sigma_2$ $x$ $Y$ $Y$ $Y$ $x$

Ryan Williams
fonte

Ryan, muito obrigado pela sua resposta. Eu sou interessante o quão difícil é simular um algoritmo determinístico Y para 3-SAT. E a questão é se, não importa o que seja Y, isso é difícil no espaço P. (Sua compreensão de simular algoritmos nondeterministic assim também é interessante e talvez seja a pergunta correta, mas eu só considerada simulando um algoritmo determinístico.)

Gil Kalai

Sim, pensei que o último parágrafo da minha resposta fosse abordar esta parte.

Ryan Williams

Entendo. Sim, é verdade. Eu também suspeito que poderia ser comprovadamente

-Hard que é interessante (mas eu não tenho certeza se eu entendo a sua prova). Você espera que

seja a resposta correta? Eu também suspeitava que provar algo além de

seria difícil. Voltando do que podemos provar ao que devemos acreditar, Ryan, qual você acha que é a resposta?

P^{N P}

$P^{NP}$

P^{N P}

$P^{NP}$

P^{N P}

$P^{NP}$

Gil Kalai

Pois bem, a complexidade de

irá variar de acordo com o algoritmo de

. Alguns

pode ser muito difícil e outros podem ser muito mais fácil. Mas acho que, para todo algoritmo

, você provavelmente não se sairá muito melhor do que dizer "

duro". (Eu não acho que para cada

você pode obter

-hardness, pela razão intuitiva que dei acima.)

C_{Y}

$C_Y$

Y

$Y$

C_{Y}

$C_Y$

Y

$Y$

C_{Y}

$C_Y$

P^{N P}

$P^{NP}$

Y

$Y$

Σ_{2} P

$\Sigma_2 P$

Ryan Williams

Ryan, você diz que "há uma redução polinomial de um

linguagem completa ... para

", mas a sua redução parece usar várias instâncias de

. Certamente, esta mostra em vez que há uma redução de um polinómio

problema -completo para

P^{N P}

$P^{NP}$

C_{Y}

$C_Y$

C_{Y}

$C_Y$

P^{N P}

$P^{NP}$

P^{C_{Y}}

$P^{C_Y}$

Joe Fitzsimons

Inicialmente, publiquei uma resposta incorreta, por isso espero que isso melhore.

Vou começar considerando o exemplo 3SAT. Em seu comentário sobre a resposta de Ryan, você diz

Eu sou interessante o quão difícil é simular um algoritmo determinístico Y para 3-SAT. E a questão é se, não importa o que seja Y, isso é difícil no espaço P.

A resposta para isso é que não é difícil para o PSPACE por pelo menos algum Y, assumindo que NP PSPACE, mas que existem outros algoritmos para os quais é difícil para o PSPACE. Mostrar o último é trivial: simplesmente construímos um algoritmo que interpreta a cadeia de bits que representa a fórmula 3SAT como um problema TQBF, que ele resolve antes de resolver a instância 3SAT. Obviamente, não há nada de especial no TQBF nesse caso, portanto o algoritmo pode ser arbitrariamente difícil de simular. Portanto, devemos nos preocupar apenas com limites inferiores na simulação de qualquer algoritmo para um determinado problema, em vez de um algoritmo específico. $\neq$

Com isso em mente, construímos o seguinte algoritmo para resolver o 3SAT:

Pegue um registro de bits (inicialmente definido como 0) para conter uma solução de avaliação, juntamente com um registro contendo a instância 3SAT, um contador de tamanho inicialmente definido como 1 e dois sinalizadores bits (chame-os de sinalizador de falha e de sinalização de aceitação). Aqui é o número de cláusulas. O algoritmo prossegue da seguinte maneira: $n$ $\lceil\log_2 (c + 1)\rceil$ $c$

Se o valor do contador de cláusulas for menor ou igual a e a solução de teste não for , verifique se a cláusula é satisfeita. Caso contrário, defina o bit de falha. Incremente o contador. $k$ $c$ $111......1$ $k$
Se o valor do contador de cláusulas for menor ou igual a , e a solução experimental for , verifique se a cláusula é satisfeita. Caso contrário, defina o sinalizador de falha. Incremente o contador. $k$ $c$ $111......1$ $k$
Se exceder , e a solução de avaliação não for , verifique se o sinalizador de falha está definido. Nesse caso, aumente a solução de teste, redefina o contador para 1 e desative o sinalizador de falha. Se o sinalizador de falha não foi definido, defina o sinalizador de aceitação, defina o contador de cláusulas como zero, defina a solução de avaliação como zero e pare. $k$ $c$ $111......1$ $k$ $k$
Se exceder , e a solução de avaliação for , verifique se o sinalizador de falha está definido. Se o sinalizador de falha não foi definido, defina o sinalizador de aceitação. Defina o contador de cláusulas como zero, defina a solução de teste como zero e pare. $k$ $c$ $111......1$ $k$

Quando o algoritmo é interrompido, o estado do sinalizador de aceitação informa se a fórmula 3SAT pode ou não ser satisfeita.

Agora, se eu quiser calcular o estado do algoritmo no momento, tenho um algoritmo para calcular isso em tempo polinomial com uma única chamada para um oracle NP da seguinte maneira: $i$

Observe que, para qualquer , assumindo que o bit de aceitação ainda não foi definido, o estado dos registradores pode ser calculado em tempo polinomial, uma vez que o valor de e o registro da solução de teste são simplesmente funções de . Determinar se o sinalizador de falha está definido pode ser feito em tempo polinomial, simplesmente verificando se o estado atual do registro da solução de teste satisfaz todas as cláusulas menores ou iguais ao valor atual de . Se e somente se esse não for o caso, o sinalizador de falha será definido. O sinalizador de aceitação está definido como zero. $i$ $k$ $t$ $i$ $k$

Da mesma forma, se o bit de aceitação já tiver sido definido, o estado dos registradores poderá ser calculado com eficiência, pois tudo é zero, exceto o bit de aceitação, que está definido.

Portanto, a única dureza é determinar se o bit de aceitação está definido. Isso é equivalente a determinar se a instância 3SAT fornecida tem uma solução menor que . Caso isso aconteça, o bit de aceitação deve necessariamente ser definido e, caso contrário, o bit de aceitação deve ser necessariamente zero. Claramente, esse problema é NP completo. $t$

Assim, o estado do sistema na etapa pode ser determinado em tempo polinomial com uma única consulta a um oracle NP. $i$

Atualização importante: Inicialmente, eu interpretei mal a formulação exata de Ryan como um problema de decisão e, portanto, minha afirmação de que a versão da decisão estava no NP estava incorreta. Dado o problema de decidir se o bit na etapa da entrada conforme formulado na resposta de Ryans, existem 3 possibilidades: $j$ $i$ $x$

Este bit é constante, independentemente de ser satisfatório. Como existem apenas dois estados possíveis para o sistema no momento (ambos os quais podem ser calculados em P), determinando se esse é o caso e, se for o caso, se o valor é igual a está em P. $F$ $\sigma$
O bit é igual a se e desigual caso contrário. Esse problema está claramente em NP, pois a designação satisfatória de atua como testemunha. $\sigma$ $F\in SAT$ $F$
O bit é igual a se caso em que o problema é, em seguida, em coNP. $\sigma$ $F\in UNSAT$

Claramente decidir qual destes três é o caso pode ser feito em tempo polinomial, simplesmente comparando o valor que toma pouco se e, se . Portanto, o problema exato da simulação está em NP coNP. Assim, como limite inferior de Ryan e meu jogo limite superior, assumindo ambos estiverem correctos, penso que tem uma resposta: . $F\in SAT$ $F\in UNSAT$ $\cup$ $C_Y = NP\cup coNP$

Observe que não há nada de especial no 3SAT nesse caso, e o mesmo pode ser feito para qualquer problema no NP. Além disso, o mesmo truque pode ser usado para qualquer classe de complexidade não determinística, não apenas o NP, que parece ser o mais difícil de simular. Para classes determinísticas, você pode simplesmente executar o melhor algoritmo e parar na etapa . Portanto, com isso em mente, a simulação completa de pelo menos algum algoritmo determinístico para um problema é tão difícil quanto resolver o problema em si. $i$

Joe Fitzsimons
fonte

Você não pode usar a mesma técnica para mostrar que b) Atingir a mesma solução que o algoritmo A já é difícil para o PSPACE? Faça com que o algoritmo escolha entre uma das duas soluções possíveis, dependendo da solução de um problema difícil do PSPACE codificado na entrada.

Peter Shor

@ Peter: Claro, você poderia dificultar arbitrariamente, mas eu pensei que a pergunta interessante era o limite superior minimizado em relação a A, o que torna nosso NP.

Joe Fitzsimons

Pensamento muito interessante! Aqui está um comentário estendido que foi muito longo para ser postado como tal:

Em relação à definição em (1) como tal , ou seja:

Comece com uma classe de complexidade descrita por alguma tarefa computacional. Dado um algoritmo A para executar cada instância desta tarefa computacional, considerar uma nova classe de complexidade que é descrito pela tarefa computacional de completamente simular . Então podemos (esperamos) definir um "ideal" de classes de complexidade: para todos os algoritmos . $C$ $C_A$ $A$ $C^+ = \{C_A:$ $A\}$

Acredito que você vai encontrar rapidamente um problema com indecidibilidade de associação não trivial no . Em particular, dada a descrição de duas MTs e , é sabido que decidir se eles aceitam o mesmo idioma (ou seja, é indecidível em geral pela redução do Problema de Parada. $C^+$ $M$ $M^{\prime}$ $L(M) \stackrel{?}{=} L(M^{\prime})$

$M^*$ $M$ $M$ $M$ $M$ $t(n)$ $M^*$ runs in $O(t(n))$ (whereby "run," I mean "simulates $M$ exactly").

$NP$ is $PSPACE$ -hard, you'll have to rule out the notion of a trivial, linear-time simulation of the $NP$ machines in question.

With respect to the homotopy methods described in the talk/paper and GPS's $PSPACE$ -completeness result, I believe the "gap" you're witnessing between $PPAD$ -completeness and $PSPACE$ -hardness is due to the distinction between finding any NE (in the sense of END OF LINE) and finding a unique NE given a specific, initial configuration (in the sense of OTHER END OF LINE).

Daniel Apon
fonte

Dear Daniel, thanks for your answer. I am not sure I see why undecidability of membership in C^+ (Or even in C itself) is relevant to the question. The questions if :a) based on all our conjectures and beliefs regarding seperations of complexity classes is it the case that for every algorithm A for 3-SAT the computational task of simulating A (for every instance of 3-SAT) is

Δ_{3}^{P}

$\Delta_3^P$ hard. b) Is it possible to actually proves such (or a similar) statement.(Maybe something very basic is wrong with my questions but I am not sure decidability is the issue.)

Gil Kalai

Gil, see if this speaks to your question at all: Fix some (arbitrary) algorithm A for 3-SAT. Consider a new algorithm B. Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs. Since we can view algorithms as Turing machines, we can take the view that A accepts 3-SAT (by the supposition). To prove the claim, it appears to me that we then need to decide the question "Does B (viewed as a TM) accept 3-SAT as well?", which leads into undecidability issues.

Daniel Apon

I should point out that it's specifically the phrase "for all algorithms A" in the definition of

C^{+}

$C^+$ coupled with the notion of saying/guessing (or, presumably, computing or deciding) the elements of the set that gives me pause, if nothing else. Once we start considering computation on properties of arbitrary algorithms or languages or classes/sets of languages, the Halting problem often seems to creep in.

Daniel Apon

Dear Daniel, you wrote "Then we want to claim: B simulates A, in the sense of your (b) -- i.e. that B reaches the same solutions as A on all well-defined inputs." This is not what I mean by "B simulates A". For me B simulates A means that it describes precisely the entire "running" of algorithm A not just reach the same "solutions" (or output).

Gil Kalai

Regarding your second comment. It looks that we can find a reasonable restriction on the algorithms we consider or formulate the question a little differently: E.g. consider the statement "For every algorithm A to solve 3-SAT it is P-space hard to simulate A." I dont see how the halting problem creep in (more than in other questions in computational complexity).

Gil Kalai