La relación entre la complejidad computacional y la lógica matemática es tan antigua como todo el campo de la complejidad computacional (ver la carta de Gödel [1] a von Neumann). Se han realizado enormes cantidades de trabajo para dilucidar esas conexiones e intentar avanzar en cuestiones como P vs NP utilizando herramientas de la lógica y la teoría de modelos, incluida la posibilidad de que P vs NP sea indecidible en algunos marcos lógicos.
En cualquier caso, los métodos matemáticos rara vez caen perfectamente en un solo cubo. Comprender la complejidad computacional implica herramientas de la teoría de grafos, la teoría de la computación, la teoría de números, el análisis, la lógica matemática y cualquier otra cantidad de disciplinas mezcladas. No creo que sea útil o correcto decir que la mayoría de las personas investigan estos problemas “por combinatoria” en lugar de “por lógica”.
Notas al pie
- ¿Hay algún buen sitio web para aprender matemáticas avanzadas paso a paso?
- ¿Cuál es la diferencia entre Basic Auth, Digest Auth, oAuth1.0 y oAuth2.0? ¿Cuál es un ejemplo de cada uno en el núcleo de PHP?
- Cómo resolver este problema particular de programación dinámica ACM-ICPC
- Teoría de la complejidad computacional: ¿cómo es posible que P! = NP no se haya probado todavía?
- ¿Cuál es la diferencia entre una cubierta abierta y una subcubierta finita en relación con la compacidad?
[1] La carta de Gödel
