Os limites de tempo de execução em P são decidíveis? (resposta: não)

64

A pergunta é se a seguinte pergunta é decidível:

Problema   Dado que um número inteiro e uma máquina de Turing prometeu estar em P, o tempo de execução de com relação ao comprimento de entrada ?M M O ( n k ) nkMM O(nk)n

Uma resposta restrita de "sim", "não" ou "aberto" é aceitável (com referências, esboço de prova ou uma revisão do conhecimento atual), mas respostas mais amplas também são muito bem-vindas.

Responda

Emanuele Viola postou uma prova de que a pergunta é indecidível (veja abaixo).

fundo

Para mim, essa pergunta surgiu naturalmente ao analisar a resposta de Luca Tevisan à pergunta Os tempos de execução de P exigem recursos de EXP para o limite superior? … Exemplos concretos são conhecidos?

A pergunta também se refere a uma pergunta do MathOverflow: Quais são os problemas indecidíveis de Turing mais atraentes da matemática? , em uma variação na qual a palavra "matemática" é alterada para "engenharia", em reconhecimento de que a estimativa em tempo de execução é um problema de engenharia onipresente associado a (por exemplo) teoria de controle e projeto de circuitos.

Portanto, o objetivo geral de fazer essa pergunta é obter uma melhor apreciação / intuição sobre quais aspectos práticos da estimativa de tempo de execução na classe de complexidade P são viáveis ​​(ou seja, requerem recursos computacionais em P para estimar), versus inviáveis ​​(ou seja, requerem recursos computacionais no EXP para estimar), versus formalmente indecidível.

--- editar (pós-resposta) ---

Eu adicionei o teorema de Viola para o MathOverflow comunidade wiki "Attractive problemas Turing-indecidíveis". É a primeira contribuição desse wiki associada à classe de complexidade P; isso atesta a novidade, a naturalidade e o amplo escopo do teorema de Viola (e IMHO também sua beleza).

--- editar (pós-resposta) ---

Monografia de Juris Hartmanis Cálculos viáveis ​​e propriedades de complexidade comprovável (1978) cobrem praticamente o mesmo material que a prova de Emanuele Viola.

John Sidles
fonte
Em resposta às perguntas feitas no blog de Lance Fortnow e Bill GASARCH, sob o tópico "75 Anos de Ciência da Computação", começando com "Sempre desejei que Turing tivesse perguntado com sobriedade:" Quais são os processos verificáveis ​​que podem ser realizados na computação de um computador? número? ”... em vez de Turing fazer a pergunta fatalmente mais difícil:“ Quais são os processos possíveis que podem ser realizados na computação de um número? ”, a próxima pergunta feita será (aproximadamente)" Existem máquinas de Turing que são comprovadamente em NP, cuja participação no P é indecidível "Isso é para mostrar que eu ainda estou pensando sobre isso :)?!
John sidles
2
Embora a prova de que eu Emanuele Viola é mais claro, uma pergunta muito semelhante foi feita e respondida em Mathoverflow: mathoverflow.net/questions/28056/...
Alex ten Brink
Várias das respostas e idéias desse tópico se mostraram relevantes para um ensaio / conjunto de perguntas que Dick Lipton postou em seu blog Godel's Lost Letter ; esse ensaio / conjunto de perguntas é "Getting On Base With P = NP". URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
John Sidles
Embora os limites em P sejam indecidíveis, ele não impede que alguém tente (restringindo-se ainda mais). Um exemplo se for dado nesta resposta cstheory
Artem Kaznatcheev
11
Esta pergunta inspirou o seguinte artigo: arxiv.org/abs/1307.3648
David G

Respostas:

83

O problema é indecidível. Especificamente, você pode reduzir o problema de parada da seguinte maneira. Dada uma instância do problema de parada, construa uma nova máquina que funcione da seguinte maneira: nas entradas de comprimento , ele simula em para etapas. Se aceitar, faça um loop para etapas e pare; caso contrário, faça um loop para etapas e pare.H ' n M x N H N 2 n 3(M,x)MnMxnMn2n3

Se parar em ele fará isso em etapas , então o tempo de execução de seria . Se nunca parar, o tempo de execução de será pelo menos .x t = O ( 1 ) M O ( n 2 ) M M n 3Mxt=O(1)MO(n2)MMn3

Portanto, você pode decidir se aceita decidindo se o tempo de execução de é ou .x M O ( n 2 ) O ( n 3 )MxMO(n2)O(n3)

Manu
fonte
4
por que M precisa parar em x (se houver) nas etapas O (1)?
Suresh Venkat
10
M e são fixados independentemente de . xn
Manu
2
Prova muito inteligente, é uma variação de algum resultado conhecido ou você acabou de inventar?
Antonio E. Porreca
3
@Raphael: Essa é uma área delicada, que acho que não resolvemos. Alguns sites de troca de pilhas incentivam a edição das respostas de outras pessoas. Não temos uma política contra isso, mas, por uma questão prática, quase nunca vi isso acontecer. Um ponto técnico: se uma resposta for editada demais, ela se tornará um wiki da comunidade e o @Emanuele não obteria mais pontos de representação se sua resposta fosse votada depois disso. Acho que explicações adicionais ajudariam a esclarecer: @ John Sidles inicialmente pensou que a promessa não estava sendo usada, mas a prova usa uma promessa mais forte : é executado em ou , não apenas em P.Mn2n3
Aaron Sterling
2
@ John: Contanto que nenhuma referência publicada seja dada, considere esta diretriz .
Raphael
29

Esta é uma reformulação da resposta de Emanuele Viola com o objetivo de ser mais compreensível.

Mostramos que o problema dado é indecidível, reduzindo o problema geral de parada a ele.PH

Seja qualquer exemplo do problema de parada, ou seja, temos que decidir se ( pára em ). Construa uma máquina de Turing que funcione da seguinte maneira:(M,x)M(x)MxM

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Agora observamos as seguintes implicações:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

e

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

Portanto, . Supondo que fosse algoritmicamente decidível, seria , o que gera uma contradição. P H H(M,x)P(M,2)PH

Rafael
fonte
12

No lado positivo, é decidível se uma máquina de Turing de uma fita é executada no tempo para , consulte:C , D NnCn+DC,DN

David Gajser: Verificando se as Máquinas de Turing Não Determinísticas de Uma Fita Funcionam no TempoCn+D , arXiv: 1312.0496

Andrej Bauer
fonte
11
Não há falta de comportamento incomum nas TMs de uma única fita. :)
Kaveh
4

O problema também foi resolvido no meu artigo " O conteúdo intensional do Teorema de Rice " POPL'2008, onde provo que nenhuma "camarilha da complexidade" é decidível. Uma camarilha de complexidade é uma classe de programas que encerram programas com comportamento e complexidade semelhantes . Eu também fornece condições necessárias para propriedades semi-decidíveis.

Os programas executados em O (n ^ k) são um clique de complexidade no sentido acima, portanto, o conjunto não é decidível.

Recentemente, o resultado também foi estendido a configurações sub-recursivas (como P) por Mathieu Hoyrup: As propriedades decidíveis das funções sub-recursivas (ICALP 2016).

Andrea Asperti
fonte
2

Para adicionar às respostas anteriores, esse problema não é apenas indecidível, mas completo. Assim, é indecidível mesmo que o decisor tenha um oráculo para o problema da parada. Σ20

Para esclarecer a completude, enquanto a condição de promessa em tempo P também é concluída com , existe um conjunto de códigos decidível, de modo que todas as máquinas em são tempo polinomial e a pergunta é completar em .Σ20SSO(n2)Σ20S

Para provar isso, escolha completo , com tempo polinomial computável (para números binários). & Phi φ (x) k mΣ20φψφ(x)kmψ(x,k,m)ψ

Então mantém se a seguinte máquina for onde é o comprimento de entrada (a máquina se preocupa apenas com o comprimento de entrada):O ( n 2 ) nφ(x)O(n2)n

para em 0 a :     se : # testado usando uma         parada de loop,     aguarde etapas paradan m < nkn
n 2m<nψ(x,k,m)

n2

Note-se que para cada não muito pequena , se um programa sempre pára em (por exemplo) passos é -completo, mas perguntando sobre limites de uma forma robusta dá -completeness.n 2 + c Π 0 1 Σ 0 2cn2+cΠ10Σ20

Dmytro Taranovsky
fonte
-1

aqui estão novas análises / ângulos / resultados mais sistemáticos recentes sobre esta questão e questões relacionadas, introduzindo o conceito de "verificabilidade algorítmica" e um análogo de Rice-like-thm para a teoria da complexidade. uma seção relevante do resumo é a seguir e existem muitos outros teoremas relacionados à provabilidade de P vs NP etc.

  • Por que o conceito de complexidade computacional é difícil para a matemática verificável / Hromkovic

    Primeiro, provamos que o teorema de Rice é improvável, alegando que cada problema semântico não trivial dos programas não é praticamente solucionável em todos os lugares na matemática "AV" algoritmo-verificável. Usando isso, mostramos que existem infinitos algoritmos (programas comprovadamente algoritmos) para os quais não existem provas de que eles trabalhem em tempo polinomial ou que não funcionem em tempo polinomial. ...

    Observe que, se P! = NP é comprovável em matemática AV, é provável que, para cada algoritmo A, "A não resolva a SATISFIABILIDADE ou A não funcione em tempo polinomial". Curiosamente, finalmente mostramos que existem algoritmos para os quais não é provável que eles não funcionem em tempo polinomial, nem que eles não resolvam a SATISFIABILIDADE. Além disso, existe um algoritmo que resolve SATISFIABILITY, para o qual não se pode provar na matemática AV que ele não funciona em tempo polinomial.

    Além disso, mostramos que P = NP implica a existência de algoritmos X para os quais a afirmação "X resolve SATISFIABILIDADE em tempo polinomial" não é possível em matemática AV.

vzn
fonte
-3

A solução do Viola pode ser generalizada para qualquer tempo de execução (além do poli): Você pode reduzir o problema de parada da seguinte forma. Dada uma instância (M, x) do problema de parada, construa uma nova máquina M ′ que funciona da seguinte maneira: nas entradas de comprimento n, ele simula M em x para f (n) etapas ou até M parar, onde f (n ) é qualquer função arbitrária crescente (maior que constante) de n. (Obs .: M ′ lê gradualmente a entrada, para evitar desperdiçar tempo linear [O (n)] apenas para ler desnecessariamente toda a entrada, se ela for grande o suficiente e M parar.)

Se M parar em x, o fará em etapas T = O (1), portanto o tempo de execução de M ′ seria O (1). Se M nunca parar, o tempo de execução de M ′ é O (n ^ 2 * f (n)).

Portanto, você pode decidir se M aceita x decidindo se o tempo de execução de M ′ é O (1) ou O (n ^ 2 * f (n)).

Em seguida, o código auxiliar do Raphael pode ser generalizado de acordo com:

Seja (M, x) qualquer instância do Problema da Parada, ou seja, temos que decidir se M pára em x. Construa uma Máquina de Turing determinística (DTM) M * que funciona da seguinte maneira:

  1. M * (entrada) = {
  2. n: = 0
  3. Leia o primeiro símbolo da entrada
  4. Ciclo:
  5. n: = n + 1
  6. Simule M (x) para etapas de f (n) ou até M (x) parar
  7. Leia o próximo símbolo da entrada
  8. Loop até end_of_input ou até M (x) parar
  9. }

Agora observamos as seguintes implicações:

M pára em x depois de no máximo k etapas (constantes) => T (M *) = O (1) e

M nunca pára em x => T (M *) = O (n ^ 2 * f (n))

Portanto, mesmo decidir se o tempo de execução de um DTM arbitrário é simplesmente maior que constante é tão difícil quanto o Problema de Parada. □

André Luiz Barbosa
fonte
2
1) Por favor, use o LaTeX. 2) Qual é a nova contribuição para esta questão? 3) Seu raciocínio está com defeito. Simular leva tempo , pois certamente não pode ser executado em tempo constante. O ( n ) M MO(n)M
Raphael
Para n grande o suficiente, se M (x) parar, sua simulação também pára e retorna a M * dentro de n0 (constante) etapas.
André Luiz Barbosa