¿Existe un sistema de tipos que restrinja los términos lambda a los términos que se encuentran dentro de una clase de complejidad? ¿Como los términos tipificables en la teoría están estrictamente dentro de la clase de complejidad? ¿O no es posible en absoluto?
Creo que hay muchos estudios sobre la expresibilidad de la teoría de tipos, como terminación probable, polinomios extendidos, etc. Pero, ¿hay alguna forma de restringir eso a una clase de complejidad?
complexity-classes
type-theory
Vinothkumar Raman
fuente
fuente
Respuestas:
Las palabras clave que busca son "Complejidad computacional implícita". Los estudios de campo, por ejemplo, las variantes de la lógica lineal y los límites de complejidad que pueden garantizar en los términos subyacentes a las derivaciones.
fuente