Teoria dos tipos e complexidade computacional

8

Existe um sistema de tipos que restrinja os termos lambda aos termos que se enquadram em uma classe de complexidade? Como os termos tipáveis ​​da teoria estão estritamente dentro da classe de complexidade? Ou isso não é possível?

Acho que existem muitos estudos sobre expressibilidade da teoria dos tipos, como terminação comprovada, polinômios estendidos etc. Mas existe alguma maneira de restringir isso a uma classe de complexidade?

Vinothkumar Raman
fonte
1
Este tópico faz parte da área de Complexidade Computacional Implícita, na qual existem muitos resultados desse tipo. Os sistemas de tipos considerados existem "tipos ramificados" ou variantes da lógica linear, por exemplo, Light Affine Logic ou Soft Affine Logic.
Jan Johannsen

Respostas:

10

As palavras-chave que você está procurando são "Complexidade Computacional Implícita". Os estudos de campo, por exemplo, variantes da lógica linear e os limites de complexidade que podem garantir nos termos subjacentes às derivações.

Gallais
fonte
1
Você tem alguma referência legal para o mesmo? Eu realmente gostaria de entender isso melhor?
Vinothkumar Raman
1
@VinothkumarRaman Gostaria de procurar o trabalho de (Martin) Hofmann e (Jan) Hoffmann.
Xrq 26/10/19