Desde un punto de vista puramente abstracto de razonamiento matemático / computacional, ¿cómo podría uno incluso descubrir o razonar sobre problemas como 3-SAT, Subset Sum, Travelling Salesman, etc.? Estaríamos incluso capaz de razonar sobre ellas de una manera significativa con sólo la funcionalidad punto de vista? ¿Sería posible?
He estado reflexionando sobre esta cuestión únicamente desde un punto de auto indagación como parte del aprendizaje del modelo de cálculo de cálculo lambda. Entiendo que es "no intuitivo" y por eso Godel favoreció el modelo de Turing. Sin embargo, solo deseo saber cuáles son las limitaciones teóricas conocidas de este estilo funcional de cómputo y cuánto obstáculo sería para analizar la clase de problemas NP.
Respuestas:
Es posible que desee ver la semántica de costos para lenguajes funcionales . Estas son varias medidas de complejidad computacional para lenguajes funcionales que no pasan por ningún tipo de máquina Turing, máquina RAM, etc. Un buen lugar para comenzar a buscar es esta publicación de Lambda the Ultimate , que tiene algunas buenas referencias adicionales.
La Sección 7.4 de los Fundamentos prácticos para lenguajes de programación de Bob Harper explica la semántica de costos.
El documento sobre la utilidad relativa de las bolas de fuego por Accattoli y Coen muestra que el cálculo tiene como máximo una explosión lineal con respecto al modelo de máquina RAM.λ
En resumen, en este otro planeta las cosas serían más o menos lo mismo con respecto a NP, pero habría menos desbordamientos de búfer y no habría tanta basura por ahí.
fuente
A petición de Andrej y PhD, estoy convirtiendo mi comentario en una respuesta, con disculpas por la publicidad propia.
Recientemente escribí un artículo en el que miro cómo probar el teorema de Cook-Levin ( -completitud del SAT) usando un lenguaje funcional (una variante del cálculo λ) en lugar de las máquinas de Turing. Un resumen:N P
fuente