¿En qué medida puede un algoritmo predecir la complejidad temporal de un programa de entrada arbitrario?

El problema de detención indica que es imposible escribir un programa que pueda determinar si otro programa se detiene, para todos los programas de entrada posibles .

Sin embargo, ciertamente puedo escribir un programa que pueda calcular el tiempo de ejecución de un programa como:

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

y devuelve una complejidad de tiempo de , sin ejecutarlo nunca.$N$

Para todos los demás programas de entrada, devolvería un indicador que indica que no pudo determinar la complejidad temporal.

Mi pregunta es esta:

¿Qué condiciones deben cumplir, de modo que podamos determinar algorítmicamente la complejidad temporal de un programa dado?

* Si hay una referencia canónica o un artículo de revisión sobre esto, agradecería un enlace a él en los comentarios.

En general, no puede determinar la complejidad, incluso para detener programas: deje que sea ​​una máquina Turing arbitraria y deje que p T sea ​​el programa (que siempre devuelve 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

Está claro que, en general, es indecidible si es de tiempo lineal o de tiempo cuadrático.$p_T$

Sin embargo, se ha trabajado mucho en el cálculo efectivo de la complejidad del programa. Tengo especial afición por la teoría de la complejidad implícita, que tiene como objetivo crear lenguajes que, utilizando construcciones especiales o disciplinas de tipo, le permitan a uno escribir solo programas que habitan una cierta clase de complejidad bien definida. ¡Por lo que considero un milagro, estos idiomas a menudo están completos para esa clase!

J.-Y. describe en este documento un ejemplo particularmente agradable. Marion, que describe una pequeña lenguaje imperativo, con una disciplina tipo inspirado a partir de técnicas de flujo de información y análisis de seguridad, lo que permite una caracterización de algoritmos en P .

La pregunta que plantea y el truco de conteo específico que describe es clásico en el análisis de programas. Existe el problema teórico del análisis de complejidad, y es una manifestación práctica en términos de estimar automáticamente el rendimiento de un fragmento de código. Tal análisis automatizado tiene varias aplicaciones, desde la detección de errores de rendimiento hasta la estimación del costo de algunos cálculos en la nube.

Cody señaló que el problema es indecidible en general. Este problema es más difícil que probar la finalización, porque obtener un límite de complejidad implica que el programa también finalice. Hay dos enfoques para tal problema. Uno es del análisis del programa. La idea de agregar un contador y estimar su valor existe desde los años 70. Esta codificación reduce el problema de determinar el tiempo de ejecución al cálculo de una invariante.

Un segundo enfoque es diseñar un lenguaje de programación que solo admita programas de cierta complejidad limitada. Esta es el área de la complejidad computacional implícita.

Algunas referencias para ambas áreas siguen.

1. El Proyecto SPEED es una línea específica de trabajo de análisis de programas que se enfoca en cómo encontrar límites en los contadores una vez introducidos en el programa. Los contadores pueden medir el consumo de tiempo o espacio.
2. Análisis de recursos amortizados multivariados , Jan Hoffman, Klaus Aehlig, Martin Hoffman, ACM TOPLAS 2012
3. Sobre las propiedades de tasa de crecimiento determinables de los programas imperativos , Amir Ben Amram, Desarrollos en la conformidad computacional implícita 2010. Esta es una hermosa línea de trabajo sobre la complejidad límite de los programas imperativos por restricciones sintácticas.