¿Ha construido alguien un lenguaje de programación que pueda construir todos los algoritmos de P, y ningún otro?
Me interesa que esta restricción provenga naturalmente de la sintaxis, en lugar de ser una máquina de Turing normal con un temporizador.
Sí, hay todo un campo de investigación dedicado a este problema: se llama "teoría de la complejidad implícita". La idea general es utilizar un cálculo lambda basado en la lógica lineal. La restricción de linealidad de los términos lambda permite controlar la complejidad de la eliminación de cortes (y, por tanto, de la evaluación), lo que da lugar a lenguajes de programación naturales que son completos para varias clases de complejidad (como PTIME, PSPACE o LOGSPACE).
Quizá los ejemplos más naturales procedan de diversas extensiones de SQL (por supuesto, si los lenguajes de consulta cuentan). Por ejemplo, Datalog sobre relaciones ordenadas es igual a P. En general, estos lenguajes se sitúan en torno a P, pero para la mayoría de ellos es realmente difícil dar caracterizaciones exactas.
Otra perspectiva (y en mi opinión más natural) es la siguiente teoría descriptiva de la complejidad (véase también este artículo de Wikipedia ).
Estudian la cuestión desde una perspectiva distinta a la mencionada por Neel. Existen varios lenguajes que capturan exactamente las funciones computables en tiempo polinómico. Uno de los más famosos es FO+LFP .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
7 votos
¡Buena pregunta! Pero probablemente más bien respondida en CSTheory StackExchange : cstheory.stackexchange.com
3 votos
¿Por qué te opones al método del cronómetro? ¿No proporciona una manera de satisfacer su requisito formal sintácticamente, mientras que también calcula claramente exactamente los algoritmos de tiempo polinómico?
4 votos
Véase también la pregunta relacionada: mathoverflow.net/questions/28056/
1 votos
@Joel: la motivación es quizá más clara en el caso del logspace. Si $f$ y $g$ son logspace-computables, entonces también lo es $f \circ g$ pero su implementación es sorprendentemente delicada, ya que hay que encajar la ejecución de $f$ y $g$ para producir incrementalmente los bits de $g$ para alimentar a $f$ . Por lo tanto, es natural buscar lenguajes/lógicas de programación en los que la operación de composición tenga un buen comportamiento algebraico y no requiera complicados juegos de codificación.