De um ponto de vista puramente abstrato do raciocínio matemático / computacional, (como) alguém poderia descobrir ou raciocinar sobre problemas como 3-SAT, Subset Sum, Traveling Salesman etc.? Será que vamos ser mesmo capaz de raciocinar sobre eles de qualquer maneira significativa com apenas o funcional ponto de vista? Seria possível?
Estive refletindo sobre essa questão puramente a partir de um ponto de auto-indagação como parte do aprendizado do modelo de cálculo do cálculo lambda. Entendo que é "não intuitivo" e é por isso que Godel favoreceu o modelo de Turing. No entanto, gostaria apenas de saber quais são as limitações teóricas conhecidas desse estilo funcional de computação e quanto seria um obstáculo para analisar a classe de problemas NP?
Respostas:
Você pode querer procurar semântica de custos para linguagens funcionais . Essas são várias medidas de complexidade computacional para linguagens funcionais que não passam por nenhum tipo de máquina de Turing, RAM, etc. Um bom lugar para começar a procurar é este post do Lambda the Ultimate , que tem boas referências adicionais.
A Seção 7.4 dos Fundamentos práticos de Bob Harper para linguagens de programação explica a semântica dos custos.
O artigo Sobre a utilidade relativa de bolas de fogo de Accattoli e Coen mostra que o cálculo tem uma explosão linear no máximo em relação ao modelo de máquina RAM.λ
Em resumo, neste outro planeta as coisas seriam praticamente as mesmas com relação ao NP, mas haveria menos transbordamentos de buffer e não haveria tanto lixo por aí.
fonte
A pedido de Andrej e PhD, estou transformando meu comentário em uma resposta, com desculpas por autopublicidade.
Recentemente, escrevi um artigo no qual analiso como provar o teorema de Cook-Levin (NP completidade do SAT) usando uma linguagem funcional (uma variante do λ-cálculo) em vez de máquinas de Turing. Um resumo:
Portanto, a única coisa que mudaria "deste lado do planeta" é, talvez, que consideraríamos um problema relacionado ao cálculo λ, em vez de um problema relacionado ao circuito booleano, ser o "primordial"NP - problema completo.
Uma observação lateral: a prova acima mencionada pode ser reformulada em uma variante do cálcio do Accattoli com substituições explícitas lineares mencionadas na resposta de Andrej, que talvez seja mais padrão do que o λ- cálcio que uso no meu trabalho.λ λ
Edição posterior: minha resposta foi um pouco mais do que recortar e colar do meu comentário e percebo que algo mais deve ser dito sobre o cerne da pergunta que, como eu a entendo, é: seria possível desenvolver a teoria deNP -completeness sem máquinas de Turing?
Concordo com o comentário de Kaveh: a resposta é sim , mas talvez apenas retrospectivamente. Ou seja, quando se trata de complexidade (contando tempo e espaço), as máquinas de Turing são imbatíveis na simplicidade, o modelo de custo é evidente por tempo e quase evidente por espaço. No cálculo- , as coisas são muito menos evidentes: modelos de custo de tempo como os mencionados por Andrej e dados no livro de Harper são de meados dos anos 90, modelos de custo de espaço ainda quase inexistentes (conheço essencialmente um trabalho publicado Em 2008λ ).
Portanto, é claro que podemos fazer tudo usando a perspectiva puramente funcional, mas é difícil imaginar um universo alternativo no qual Hartmanis e Stearns definam classes de complexidade usandoλ e, 30 a 50 anos depois, as pessoas começam a adaptar seu trabalho a Turing máquinas
fonte