Até que ponto um algoritmo pode prever a complexidade de tempo de um programa de entrada arbitrário?

O problema de parada indica que é impossível escrever um programa que possa determinar se outro programa é interrompido para todos os programas de entrada possíveis .

Eu posso, no entanto, certamente escrever um programa que pode calcular o tempo de execução de um programa como:

for(i=0; i<N; i++)
    { x = 1; }

e retorne uma complexidade de tempo de , sem nunca executá-lo.$N$

Para todos os outros programas de entrada, ele retornaria um sinalizador indicando que não era possível determinar a complexidade do tempo.

Minha pergunta é esta:

Quais condições devem ser mantidas, para que possamos determinar algoritmicamente a complexidade de tempo de um determinado programa?

* Se houver uma referência canônica ou artigo de revisão, eu apreciaria um link para ele nos comentários.

Em geral, você não pode determinar a complexidade, mesmo para programas vacilantes: vamos haver alguma máquina de Turing arbitrária e deixe p T ser o programa (que sempre retorna 0):$T$$p_T$

input: n
run T for n steps
if T is in halting state, output: 0
otherwise, loop for n^2 steps and output: 0

É claro que é indecidível, em geral, se é tempo linear ou a tempo quadrática.$p_T$

No entanto, muito trabalho foi realizado no cálculo efetivo da complexidade do programa. Tenho particular interesse pela Teoria da Complexidade Implícita, que visa criar linguagens que, usando construções especiais ou disciplinas de tipo, permitem escrever apenas programas que habitam uma certa classe de complexidade bem definida. Pelo que considero um milagre, essas línguas costumam ser completas para essa classe!

Um exemplo particularmente interessante é descrito neste artigo por J.-Y. Marion, que descreve uma pequena linguagem imperativa, com uma disciplina tipo inspirado em técnicas de informação de fluxo e análise de segurança, que permite uma caracterização de algoritmos em P .

A pergunta que você faz e o truque de contagem específico que você descreve são clássicos na análise de programas. Existe o problema teórico da análise de complexidade e sua manifestação prática em termos de estimativa automática do desempenho de um pedaço de código. Essa análise automatizada possui vários aplicativos, desde a detecção de bugs de desempenho até a estimativa do custo de alguns cálculos na nuvem.

Cody apontou que o problema é indecidível em geral. Esse problema é mais difícil do que provar a finalização, porque a obtenção de um limite de complexidade implica que o programa também seja finalizado. Existem duas abordagens para esse problema. Um é da análise do programa. A ideia de adicionar um contador e estimar seu valor existe desde os anos 70. Essa codificação reduz o problema de determinar o tempo de execução ao da computação de um invariante.

Uma segunda abordagem é projetar uma linguagem de programação que admita apenas programas de certa complexidade limitada. Essa é a área de complexidade computacional implícita.

Seguem algumas referências para as duas áreas.

1. O Projeto SPEED é uma linha específica de trabalho de análise de programas que se concentra em como encontrar limites nos contadores, uma vez introduzidos no programa. Os contadores podem medir o consumo de tempo ou espaço.
2. Análise multivariada de recursos amortizados , Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012
3. Sobre propriedades decidíveis de taxa de crescimento de programas imperativos , Amir Ben Amram, Desenvolvimentos em conformidade computacional implícita 2010. Esta é uma bela linha de trabalho para limitar a complexidade de programas imperativos por restrições sintáticas.