O cálculo lambda afim pode resolver todos os problemas em P?

Em Tópicos avançados em tipos e linguagens de programação, é mencionado, no capítulo sobre sistemas de tipos subestruturais, que um cálculo lambda afinado "cuidadosamente criado" com um combinador de recursão para listas só pode digitar termos com tempo de execução polinomial (não apresentar a prova devido à complexidade). Isso seria super interessante se pudéssemos resolver todos os problemas em P. Eu poderia tentar encontrar uma solução para um problema de P-completo usando o cálculo apresentado por Não tenho certeza se isso realmente provaria alguma coisa. Não me parece que ele possa realizar todas as reduções necessárias para usar uma solução para um problema de P-completo (embora pareça provável).

Se não se sabe que um cálculo lambda afim é capaz de resolver exatamente os problemas em P, existe algum cálculo conhecido que possa resolver exatamente os problemas em P?

Edit: meu palpite no primeiro parágrafo abaixo está errado! Ugo Dal Lago apontou para mim um artigo posterior de Martin Hofmann (publicado no POPL 2002), do qual eu desconhecia, mostrando (como corolário de resultados mais gerais) que o sistema do livro ATTPL está de fato completo para ( apesar de não ser capaz de calcular cada função em F P ). Então, para minha surpresa, a resposta para a pergunta principal é sim.$\mathsf P$$\mathsf{FP}$

Em relação ao sistema que você está se referindo a (do livro ATTPL), eu tenho quase certeza que não pode decidir sobre as línguas em . Certamente não pode computar todas as funções na F P : como mencionado nas notas desse capítulo, esse sistema é retirado EICE de Martin Hofmann 1999 de papel ( "tipos lineares e computação tempo polinomial não-aumento-size"), em que é mostrado que as funções representáveis ​​são polytime e não aumentam o tamanho$\mathsf P$$\mathsf{FP}$, que exclui muitas funções polytime. Também parece dar uma séria limitação no tamanho da fita das máquinas de Turing que você pode simular nesse idioma. No artigo, Hofmann mostra que você pode codificar a computação linear do espaço; meu palpite é que você não será capaz de fazer muito mais, ou seja , a classe correspondente a esse sistema é aproximadamente os problemas solucionáveis ​​simultaneamente no politimo e no espaço linear.

No que diz respeito à sua segunda pergunta, existem vários -calculi que pode resolver exatamente os problemas em P . Alguns deles são mencionados nas notas do capítulo ATTPL a que você está se referindo (Seção 1.6): λ- calcculus em camadas de Leivant (veja seu artigo POPL 1993, ou o artigo com Jean-Yves Marion "Caracterizações de Cálculo do Tempo da Poli-Tempo de Jean-Yves Marion" ", Fundamenta Informaticae 19 (1/2): 167-184, 1993), que está relacionada com a caracterização de de Bellantoni e Cook F P ; e o λ -calculi derivado da lógica linear de luz de Girard ( Information and Computation , 143: 175-204, 1998) ou da lógica linear suave de Lafont ( Theoretical Computer Science$\lambda$$\mathsf P$$\lambda$$\mathsf{FP}$$\lambda$318 (1-2): 163-180, 2004). Os sistemas de tipos que surgem desses dois últimos sistemas lógicos e garantem o término do politempo (enquanto ainda desfrutam de integridade) podem ser encontrados em:

Patrick Baillot, Kazushige Terui. Tipos de luz para cálculo do tempo polinomial no cálculo lambda. Informação e computação 207 (1): 41-62, 2009.

Marco Gaboardi, Simona Ronchi Della Rocca. Da lógica leve às tarefas de digitação: um estudo de caso. Logic Journal of the IGPL 17 (5): 499-530, 2009.

Você encontrará muitas outras referências nesses dois artigos.

Para concluir, permita-me expandir a observação de Neel Krishnaswami. A situação é um pouco sutil. Todos os cálculos acima podem ser vistos como restrições de cálculos mais gerais, nos quais você pode calcular muito mais do que apenas as funções polytime, por exemplo, sistema F. Por outras palavras, você define uma propriedade Φ dos programas do sistema F P : string → bool de forma que:$\lambda$$\Phi$$P:\texttt{string}\rightarrow\texttt{bool}$

solidez: implica que a linguagem decidida por P esteja em P ;$\Phi(P)$$P$$\mathsf P$

completude: para todo , existe um programa F do sistema P que decide L tal que Φ ( P ) .$L\in\mathsf P$$P$$L$$\Phi(P)$

O interesse é que a propriedade expressa por seja puramente sintática e, em particular, decidível. Portanto, a integridade só pode ser mantida em um sentido extensional: se L é seu idioma favorito em P e se P é seu algoritmo favorito para decidir L expresso no sistema F, pode ser que Φ ( P ) não seja válido. Tudo que você sabe é que existe algum outro programa do sistema F P 'que decide L e tal que Φ ( P ' ) se mantém. Infelizmente, pode acontecer que P $\Phi$$L$$\mathsf P$$P$$L$$\Phi(P)$$P'$$L$$\Phi(P')$$P'$é muito mais artificial do que o seu . De fato, a integridade é comprovada pela codificação de máquinas de Turing com sincronismo polinomial como termos do sistema F que satisfazem Φ . Portanto, a única maneira garantida de resolver L usando seu algoritmo favorito é implementá-lo em uma máquina de Turing e depois traduzi-lo no sistema F usando a codificação fornecida na prova de completude (sua própria codificação pode não funcionar!). Não é exatamente a solução mais elegante em termos de programação ... Certamente, em muitos casos, o programa "natural" P satisfaz Φ . No entanto, em muitos outros casos, isso não ocorre: no artigo do LICS 1999 mencionado acima, Hofmann fornece o tipo de inserção como um exemplo.$P$$\Phi$$L$$P$$\Phi$

Existem sistemas de tipos intencionalmente completos , capazes de digitar exatamente os programas polytime da linguagem mais ampla (sistema F no meu exemplo acima). Claro, eles são indecidíveis em geral. Vejo

Ugo Dal Lago, Marco Gaboardi. Tipos dependentes lineares e integridade relativa. Métodos Lógicos em Ciência da Computação 8 (4), 2011.