Um algoritmo de máquina de Turing em tempo polinomial é considerado eficiente se seu tempo de execução, na pior das hipóteses, estiver limitado por uma função polinomial no tamanho da entrada. Estou ciente da forte tese de Church-Turing:
Qualquer modelo razoável de computação pode ser eficientemente simulado em máquinas de Turing
No entanto, não conheço a teoria sólida para analisar a complexidade computacional dos algoritmos de -calculus.
Temos uma noção de eficiência computacional para todo modelo conhecido de computação? Existem modelos úteis apenas para questões de computabilidade, mas inúteis para questões de complexidade computacional?
fonte
fonte
Sobre a inclusão do cálculo λ no modelo de complexidade padrão, aqui está o resumo de algumas (muito) novas pesquisas sobre o assunto. Dá uma resposta a esta pergunta para alguma forma restrita de redução β. Basicamente, a complexidade no modelo de custo padrão é semelhante à contagem de etapas de redução β quando restrita à redução de cabeças (que inclui estratégias de chamada por nome e chamada por valor).
Sobre a invariância do modelo de custo unitário para redução de cabeça por Beniamino Accattoli e Ugo Dal Lago. (WST2012, link para o processo )
fonte