Existem problemas decidíveis para os quais, sem algoritmos, podemos dar limites de tempo?

12

Existem problemas decidíveis que, para nenhum algoritmo que resolva o problema, podemos dar um tempo limitado em função do comprimento n da instância de entrada?

Cheguei a essa pergunta porque estava pensando no seguinte:

Suponha que temos um problema recursivamente enumerável, mas indecidível. Suponha ainda que eu seja uma instância "sim" do problema. Portanto, para nenhum algoritmo que identifique as instâncias "sim" do problema, podemos atribuir um limite de tempo em termos do tamanho n de I. Pois, se pudéssemos conceder um limite de tempo, poderíamos decidir o problema, como poderíamos simplesmente concluo que sou uma instância "não" quando o tempo limite é excedido.

Como não podemos dar um prazo para problemas recursivamente enumeráveis ​​e indecidíveis (para o tempo de computação para instâncias "sim"), fiquei pensando se também existem problemas decidíveis para os quais não podemos dar um prazo.

Hermann
fonte
9
Há um tempo trivial vinculado a esses algoritmos: execute o algoritmo e retorne o número de etapas executadas por esse algoritmo. Por outro lado, é fácil construir exemplos para os quais é difícil definir limites fáceis de entender ou expressar, por exemplo, a função ackermann.
Cody
2
Você terá que ser mais preciso. Se você fala sobre funções (matemáticas), sim, existe uma função que corresponde ao tempo de execução de qualquer máquina de Turing (de fato, há mais funções que as máquinas de Turing). Se você fala sobre funções computáveis ​​ou, equivalentemente, algoritmos, o @cody fornece a resposta: basta executar a máquina de Turing que decide o problema e contar o tempo de execução.
Alex ten Brink
8
@AlextenBrink: Na verdade, para obter o pior tempo de execução em função do tamanho de entrada , você precisa executar a máquina de Turing para todas as entradas possíveis de tamanho e aproveitar ao máximo. Mas é claro que isso também é possível. nnn
Jukka Suomela 12/02/2012
8
Posso sugerir uma revisão? Para evitar a resposta trivial, suponha que definimos a frase "podemos atribuir um limite de tempo" para significar "podemos calcular um limite superior no pior dos casos em execução mais rapidamente do que executando o algoritmo em todas as instâncias de tamanho n". Ou talvez "todas as instâncias" devam ser "uma única instância".
Jeffε
1
Seu argumento depende da função com limite de tempo ser totalmente computável. É sabido que isso não pode ser feito, mas se essa é sua pergunta (ou seja, existem funções computáveis ​​parciais sem extensão total da função computável), a questão não é de nível de pesquisa. Consulte as Perguntas frequentes para obter sugestões sobre onde você pode fazer esse tipo de perguntas.
22412 Kaveh

Respostas:

13

Para todo algoritmo que termina em uma classe de entradas , podemos definir a função de seus tempos de execução: onde é a classe de entradas de comprimento e é o algoritmo de tempo que exige para terminar em . Obviamente, essa definição é insatisfatória no que se refere ao algoritmo, mas mostra a existência de uma função. A questão que resta é se existe uma representação concisa (e acredito que era isso que você estava pedindo).AInI n ( n ) n t i m e ( A ( i ) ) A i

f(n)=maxiIn(n)  time(A(i)),
In(n)ntime(A(i))Ai

Se usarmos termos algébricos simples (sem recursão de qualquer tipo) como definição concisa, acho que a resposta é não: existem problemas que podem ser decididos, mas cuja complexidade é não-complementar. Ou seja, não existe uma pilha do formato que limite o tempo de execução de um algoritmo para um problema de tamanho n.2222n

Espero ter entendido sua pergunta da maneira correta.

Markus
fonte
6

Essa é uma opinião um pouco diferente da de Marcus, mas, à luz de sua explicação de como você chegou a essa questão, ela pode estar mais próxima do que você está procurando.

Às vezes, pode-se provar que um problema é decidível, sem poder exibir o algoritmo para ele. O exemplo mais famoso desse tipo de coisa é o trabalho de Robertson e Seymour em menores de gráfico, que mostra que qualquer propriedade hereditária de gráfico pode ser decidida em tempo polinomial, verificando a presença de uma lista finita adequada de menores proibidos. A prova deles mostra apenas que existe uma lista finita de menores proibidos, mas não fornece uma receita para encontrar a lista.

Como não sou especialista na área, não conheço um exemplo específico de uma propriedade de gráfico hereditário para a qual não possamos exibir um algoritmo porque não conhecemos a lista de menores proibidos e não conhecemos outra maneira de resolver o problema, mas suspeito que esses exemplos existem. (E podemos limitar o tempo de execução para encontrar um exemplo, se existir, pois sabemos que existem no máximo 8 bilhões de pessoas no mundo e, na pior das hipóteses, poderíamos pedir a todos!)

Uma outra observação: Como sabemos que a verificação de um menor pode ser feito em tempo, você poderia argumentar que em todos os casos fornecidos pelo algoritmo Robertson-Seymour, que não têm um "limite" de no tempo de execução. No entanto, eu argumentaria que isso é meio que trapaça, se não temos limites na constante.O ( n 3 )O(n3)O(n3)

Timothy Chow
fonte
2
Mas se você escolher um conjunto explícito de menores excluídos, poderá exibir um algoritmo. Melhor seria escolher algumas propriedades hereditárias que não foram estudadas. Isso é um pouco mais difícil de fazer, no entanto.
Timothy Chow
2
É bastante tangencial ao seu argumento, mas: as propriedades de um gráfico fechado menor podem ser decididas no tempo research.nii.ac.jp/~k_keniti/quaddp1.pdf . O(n2)
Emil Jeřábek 3.0
1
@ EmilJeřábek: ainda mais tangencialmente, decidir se um gráfico a partir satisfaçam familiares menores fechado uma propriedade de primeira ordem pode ser feito em tempo linear: arxiv.org/abs/1109.5036
András Salamon
1
A propósito, Kowarabayashi e Wollan reivindicam um limite na constante em seu documento do STOC 2011, dsi.uniroma1.it/~wollan/PUBS/shorter_struct_web.pdf, que também relata progressos adicionais que "ainda não estão totalmente escritos". No entanto, não consigo extrair facilmente um limite explícito deste artigo.
András Salamon
2
Para esse exemplo, você tem gráficos com uma cobertura plana. Estranhamente, quase conhecemos uma lista: existem 31 menores proibidos e um 32º potencial, mas, para este último, está aberto, com ou sem cobertura plana. Portanto, não temos um algoritmo para essa classe de gráficos. Veja por exemplo: fi.muni.cz/~hlineny/papers/plcover20-gc.pdf
Denis
3

Apenas para acrescentar uma perspectiva diferente, lembre-se de que nem todo problema tem uma complexidade "intrínseca", que é provavelmente a consequência mais interessante e de alguma forma negligenciada do teorema da aceleração de Blum.

Essencialmente, o teorema afirma que, corrigido um aumento de velocidade desejado g, você sempre pode encontrar um problema computacional P tal que, para qualquer programa que resolva P, exista outro programa que ainda resolva P e g-vezes mais rápido que o anterior.

Portanto, para esse tipo de problema, você não pode dar um prazo. Resultado surpreendente e bastante intrigante. É claro que P tem uma complexidade muito grande.

Andrea Asperti
fonte
Por que P tem uma complexidade muito grande?
Como o processo de aceleração pode ser iterado, portanto, ele deve ser compatível com uma cadeia infinita de algoritmos de complexidade decrescente.
Andrea Asperti 17/02
3

O aspecto teórico da sua pergunta é tratado por Markus. Mais praticamente, uma maneira interessante de entender sua pergunta é: existem problemas decidíveis para os quais não sabemos tempo limite?

A resposta é sim: por exemplo, pode acontecer que você tenha um semi-algoritmo para instâncias YES do seu problema e um semi-algoritmo para instâncias NO. Isso permite que você decida seu problema, mas não tem tempo limitado.

Aqui está um exemplo genérico: suponha que você tenha um sistema axiomático que permita provar todas as identidades verdadeiras em alguma álgebra. Além disso, você sabe que identidades falsas são sempre testemunhadas por uma estrutura finita.

Então você tem o seguinte algoritmo para decidir se uma identidade é verdadeira: enumere em provas paralelas e estruturas finitas e pare quando encontrar uma prova de ou de uma estrutura testemunhando que sou falsa. Ele lhe dá um algoritmo correto, mas nenhuma complexidade vinculada, a menos que você pode obrigado do tamanho de provas e estruturas finitas em relação ao .eu eu euIIII

Um exemplo disso é a lógica linear afim (LLW): agora é conhecido como completo em torre [1], mas por algum tempo nenhum limite foi conhecido, e apenas a decidibilidade foi mostrada, usando, entre outras técnicas, a propriedade do modelo finito [2] .

Referências:

[1] Complexidades não elementares para ramificação de VASS, MELL e extensões. Ranko Lazic e Sylvain Schmitz. CSL-LICS 2014

[2] A propriedade de modelo finito para vários fragmentos da lógica linear. Yves Lafont, J. Symb. Lógica. 1997

Denis
fonte
-4

como outros já declararam, a questão não é formulada de maneira a evitar uma resposta trivial; no entanto, existem alguns conceitos no TCS e na teoria dos números que são relacionados / similares.

1) nos teoremas da hierarquia do espaço e do tempo, é necessário o conceito de funções "tempo construtível" e "espaço construtível" . existem funções não construtíveis no tempo e não construtivas no espaço e levam a propriedades incomuns encontradas nos teoremas de Blum, como os teoremas "gap, speedup". a maioria das classes de complexidade padrão (todas?) são definidas em termos de funções construtivas de espaço e tempo.

2) a função ackerman é totalmente recursiva, mas não recursiva primitiva e isso tem implicações para o tempo limite. as funções recursivas primitivas, em certo sentido, representam as operações matemáticas "básicas".

3) existem thms sobre seqüências da teoria dos números incontestáveis ​​na aritmética peano que podem ser interpretadas como criando limites de tempo não computáveis ​​em um sentido, como a sequência goodstein ou paris-harrington thms

vzn
fonte
5
não é uma resposta para a pergunta.
Kaveh