Si se toma esto en serio, se encontrará rebotando entre recursos que buscan refinar su comprensión con nuevas perspectivas, por lo que enumeraré un montón que me ayudó.
En primer lugar, la respuesta de Alon Amit cubre probablemente el mejor recurso, pero vale la pena repetirlo. Complejidad computacional: un enfoque moderno proporciona una base en lo básico, a través de la complejidad clásica y hasta la barrera de relativización que pone en duda la capacidad de las herramientas clásicas para separar P de NP, y el teorema de Karp-Lipton que motivó enfoques a través de la complejidad del circuito ; luego, hasta los resultados Razborov-Rudich, algo más recientes, sobre pruebas naturales que también vieron encallado la complejidad del circuito; y, por supuesto, innumerables subcampos y aplicaciones y direcciones de investigación dentro de la teoría de la complejidad en el medio. Es un excelente libro de encuestas bien escrito que vale cien veces su precio, pero puede ser matemáticamente exigente.
La complejidad computacional de Papadimitriou es un tratamiento antiguo, pero pasa más tiempo justificando modelos de computación y motivando definiciones que los enfoques más modernos tienden a dar por sentado, y parece valorar más el papel de la lógica y la teoría de la computabilidad que Arora y Barak, lo cual me parece admirable. Por ejemplo, Papadimitriou sintió la necesidad de establecer el teorema de la aceleración lineal y describir cómo una máquina de Turing puede simular una computadora práctica, mientras que los libros modernos prácticamente suponen que usted da por sentada la tesis de Cobham. Sin embargo, podría ser difícil encontrar una copia de este libro.
- ¿Es el principio de equivalencia computacional de Stephen Wolfram simplemente una extensión de la tesis de Church-Turing y la máquina universal de Turing de Turing?
- Cómo encontrar las soluciones integrales de ecuación usando un programa C / C ++ de manera eficiente, donde A, B, C, D y E son enteros, sabiendo que solo tiene una solución en enteros
- ¿Cuáles son algunos métodos heurísticos en la factorización de números primos?
- Si hubiera un algoritmo de tiempo polinómico para algo como 3SAT, ¿qué tan probable es que sea algo elegante y / o simple?
- Si quiero estar en análisis predictivo y no soy experto en matemáticas ni en programación, ¿cuál debo comenzar a perfeccionar primero y por qué?
Para una introducción muy suave que todavía no escatima en rigor, la Introducción a la teoría de la computación de Michael Sipser es una gran lectura. Se dirige a través de dos secciones completas que cubren la teoría de autómatas y la teoría de computabilidad respectivamente antes de alcanzar la complejidad, pero eso es para su beneficio: obtendrá una familiaridad funcional con conceptos importantes (por ejemplo, no determinismo, reducciones) y técnicas de prueba que harán que la teoría de la complejidad sea más digerible cuando llegas a eso.
Probablemente también valga la pena encontrar apuntes de clase para un curso de Scott Aaronson (o mejor aún, su maravilloso libro) para leer de vez en cuando. Mientras que todos los escritores que he mencionado generalmente quieren que te maravilles de la profundidad filosófica del tema, Aaronson realmente convierte este aspecto en once. La preferencia (y el don) de Aaronson por el estilo sobre el rigor puede ayudar a la intuición e inspirar pasión por el tema, pero también descubrí que no tener detalles revestidos de hierro frente a mí podría enturbiar muchas ideas.
A lo largo de su estudio, va a repasar conceptos de la lógica formal de vez en cuando. Si bien este campo puede ser un agujero de conejo completamente diferente con una lista de recursos propios para abrirse paso, una introducción matemática a la lógica de Herbert Enderton es mi elección si tengo que tener uno. El libro de Enderton es minucioso y exigente, y puede ser un trabajo muy difícil de superar, pero la recompensa es una idea absolutamente impresionante de que probablemente no obtendrá la misma fidelidad en ningún otro tratamiento. Por ejemplo, le enseña cómo usar las correspondencias entre infinitos innumerables para demostrar que ciertos problemas pueden resolverse mediante programas informáticos, lo que a simple vista es un poco ridículo, ¿verdad? Recomiendo altamente este libro.
Finalmente, todos los recursos anteriores son excelentes para comprender la teoría, pero ¿qué pasa con el lado práctico? ¿Qué pasa con todos esos miles de problemas NP-hard relevantes para la industria, y cómo puede identificar un problema NP-complete por sí mismo? Y mientras estamos en ello, ¿no debería tener una base sólida en esos problemas que podamos resolver de manera eficiente y las técnicas generales que nos ayudan a hacerlo? Querrá un recurso de teoría de algoritmos, y puedo apoyarme en el Diseño de algoritmos de Kleinberg y Tardos para eso.
