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 ) 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.
fonte
Respostas:
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) M′ n M x n M n2 n3
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 3M x t=O(1) M′ O(n2) M M′ n3
Portanto, você pode decidir se aceita decidindo se o tempo de execução de é ou .x M ′ O ( n 2 ) O ( n 3 )M x M′ O(n2) O(n3)
fonte
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.P H
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)↓ M x M∗
Agora observamos as seguintes implicações:
e
Portanto, . Supondo que fosse algoritmicamente decidível, seria , o que gera uma contradição. P H ◻H(M,x)⇔P(M∗,2) P H □
fonte
No lado positivo, é decidível se uma máquina de Turing de uma fita é executada no tempo para , consulte:C , D ∈ Nn↦C⋅n+D C,D∈N
fonte
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).
fonte
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.Σ02
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 .Σ02 S S O(n2) Σ02 S
Para provar isso, escolha completo , com tempo polinomial computável (para números binários). & Phi φ (x)⇔ ∃ k ∀ mΣ02 φ ψφ(x)⇔∃k∀mψ(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 < nk n ∀m<nψ(x,k,m)
n2
n 2
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 2c ≤n2+c Π01 Σ02
fonte
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
fonte
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:
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. □
fonte