Cómo aprender independientemente la teoría de la complejidad computacional

Estoy lejos de ser un experto en el campo, pero la informática teórica es sin duda el área que más me interesa, por lo que te daré una pista sobre lo que haría, pero tómalos por lo que valen:

  1. Lea Arora y Barack – Complejidad computacional: un enfoque moderno Complejidad computacional: un enfoque moderno, esto realmente debería ayudarlo porque toca una variedad de temas que generalmente no cubre en un solo curso de complejidad en la universidad.
  2. Lea las notas de los cursos de complejidad impartidos por el profesor Luca Trevisan, es uno de los mejores investigadores en el campo y la forma en que explica temas complicados es sorprendente.
  3. Otra gran fuente de complejidad es la página web del Prof. Ryan Williams
  4. Este blog del profesor Lance Fortnow es una muy buena fuente de publicaciones interesantes sobre preguntas abiertas y preguntas recientemente resueltas en Complejidad computacional
  5. Creo que en este punto tiene una base sólida de los resultados básicos y puede tomar temas más avanzados, simplemente comenzaría a recoger los documentos de referencia de los libros y las notas de los profesores en el punto 1-3, este es el momento en el que realmente empiezas a acercarte a la vanguardia del campo, lleva mucho tiempo, pero si realmente te encanta el tema, sigue leyendo los documentos e intenta comprender el panorama general.

No creo que este sea el campo más fácil para el autoaprendizaje porque el valor de tener una especie de oráculo (como en la teoría de la complejidad) que puede responder rápidamente a sus dudas sobre problemas y teoremas es increíble. Por lo tanto, si le encanta este campo, le sugiero que tome tantos cursos como los que ofrece su universidad, estudie la literatura e intente resolver los problemas usted mismo como en otros campos hasta que realmente pase tiempo pensando en soluciones que realmente no tiene una idea de lo que estas estudiando.

Para empezar, entre en la programación competitiva. Codeforces es tu amigo.