¿Qué tipo de formación matemática se necesita para la teoría de la complejidad?

79

Actualmente soy un estudiante de pregrado, destinado a graduarme este año. Después de la graduación, estoy considerando trabajar para obtener un master / doctorado en TCS. He comenzado a preguntarme qué campos de las matemáticas se consideran útiles para TCS, especialmente la teoría de la complejidad (clásica).

¿Qué campos consideras esenciales para alguien que quiere estudiar teoría de la complejidad? ¿Conoces algún buen libro de texto que cubra estos campos? En caso afirmativo, incluye su nivel de dificultad (introductorio, graduado, etc.).

Si considera un campo que no se usa mucho en la teoría de la complejidad pero lo considera crítico para TCS, por favor, consúltelo.

cc.complexity-theory soft-question advice-request chazisop
fuente
14
Le recomiendo que comience a leer un texto estándar sobre teoría de la complejidad, como Arora / Barak o Papadimitriou, y cada vez que se atasque porque no entiende las matemáticas, intente aprender las matemáticas asociadas con algún detalle antes de continuar.
Robin Kothari
8
Después de haber hecho lo que Robin sugirió, comience a trabajar en algunos pequeños problemas abiertos. Te sentirás estimulado para aprender las matemáticas que hay detrás. Como estudiante de posgrado, no me parece muy eficiente aprender algún campo matemático solo por el simple hecho de aprender.
Alessandro Cosentino

Respuestas:

53

Si observa las respuestas a esta pregunta de TCS StackExchange , verá que existe la posibilidad de que casi cualquier área de las matemáticas pueda ser importante en la teoría de la complejidad. Entonces, si está realmente interesado en alguna área de las matemáticas que no parece estar relacionada, continúe y estudie de todos modos. Si alguna vez se vuelve relevante para la teoría de la complejidad, serás uno de los pocos teóricos de la complejidad que lo entienda.

Peter Shor
fuente
20
Esta respuesta no significa que no debas estudiar los campos que sabemos que están relacionados (ver las otras respuestas). Yo diría que estos incluyen álgebra lineal, teoría de grafos, teoría de probabilidad, álgebra abstracta básica y lógica básica.
Peter Shor el
66
Por supuesto, si quieres hacer algo como contribuir al programa de Mulmuley para probar P NP, necesitas mucha, mucha, mucha más matemática que esta. ≠
Peter Shor el
34

Debería agregar el libro de Dexter Kozen sobre la teoría de la computación a su lista. Cubre los conceptos básicos de la teoría de la complejidad de manera muy efectiva, y el formato de conferencia breve es excelente.

En términos de antecedentes matemáticos, además de lo mencionado anteriormente:

  • Teoría de probabilidad
  • Álgebra lineal y álgebra abstracta
  • Teoría de grafos
  • lógica básica

No creo que necesite ser un maestro de estos temas para comenzar, pero definitivamente ayuda tener un cierto nivel de comodidad.

Suresh Venkat
fuente
32

El libroExtremal Combinatorics, de Stasys Jukna, es OMI muy poco conocido dentro de la comunidad de complejidad. Es una gran colección de técnicas combinatorias escritas en gran medida teniendo en cuenta sus aplicaciones en TCS (principalmente complejidad). Se discuten varias técnicas de complejidad importantes en su contexto combinatorio, incluidos resultados famosos como monótonos ylímites inferiores del circuito A C 0 , pero también algunos resultados muy buenos que de otro modo no podría encontrar. Y hay muchos ejercicios.∙AC0

Es (que yo sepa) el único libro publicado que trata el 'método de álgebra lineal en combinatoria' en profundidad: una herramienta hábil y poderosa para conocer. Hay un borrador del manuscrito de Babai y Frankl que profundiza mucho más, pero que no está publicado ni en línea:

https://cs.uchicago.edu/page/linear-algebra-methods-combinatorics-applications-geometry-and-computer-science

∙

Andy Drucker
fuente
2
En la misma línea, quiero señalar la guía bellamente escrita del método de entropía, "Entropía y conteo", de Jaikumar Radhakrishnan. El método de entropía es otra de esas herramientas ingeniosas que son muy satisfactorias para aplicar cuando se presenta la oportunidad adecuada.
arnab
27

Las respuestas anteriores ya enumeraban las básicas: teoría de probabilidad, combinatoria, álgebra lineal, álgebra abstracta (campos finitos, teoría de grupos, etc.).

Yo podria agregar:

Análisis de Fourier , véase, por ejemplo, el curso de Ryan O'Donnel: http://www.cs.cmu.edu/~odonnell/boolean-analysis/

Teoría de la codificación , ver el curso de Madhu Sudán: http://people.csail.mit.edu/madhu/coding/course.html

Teoría de la información , el libro estándar es Elementos de la teoría de la información: http://www.amazon.com/Elements-Information-Theory-Telecommunications-Processing/dp/0471241954

También hay teoría de la representación, caminatas aleatorias y muchos más que probablemente olvide ...

Dana Moshkovitz
fuente
55
La mayoría de las cosas que aprendes a medida que avanzas, dependiendo de dónde te lleve la investigación / la vida: de los cursos, de las conferencias, de los colaboradores, de los documentos, etc.
Dana Moshkovitz
22

Aparte de cosas básicas, probablemente:

  • Combinatoria : puede que te encuentres contando cosas con bastante frecuencia
  • Estocástico : para análisis de casos promedio y algoritmos aleatorios

Me gusta Concrete Mathematics de Knuth. Ofrece una buena visión general / conocimiento básico de muchas herramientas importantes.

Si le gusta generar funciones (vea la función de generación de Wilf) como herramienta, el análisis complejo también es útil.

Rafael
fuente
Me encanta Concrete Math, pero es un poco esotérico. Recomendaría primero un libro más convencional, como "Combinatorics" de Cameron.
Emil
77
Esta es mi impresión: Concrete Math parece ser un libro increíble para aprender a hacer análisis exactos (o casi exactos) de algoritmos, el punto fuerte de Knuth. Si eso es lo que quieres hacer, sigue adelante. Pero tenga en cuenta que la mayoría de los documentos de teoría de complejidad dan límites mucho menos precisos, por lo que las técnicas de CM son menos relevantes.
Andy Drucker
1
Algunos podrían decir que esto se debe a que los teóricos de la complejidad son vagos. Pero creo que es porque (a) los límites exactos pueden ser más esfuerzo de lo que vale, (b) a menudo hay una brecha tan grande entre los límites superior e inferior conocidos que pequeños refinamientos en ambos lados pueden parecer de poco valor.
Andy Drucker
Debo decir que hay todo tipo de cosas interesantes en el libro: mis comentarios se refieren principalmente al material sobre soluciones exactas de sumatorios y relaciones de recurrencia.
Andy Drucker el
22

Sanjeev Arora tiene un buen documento para un curso de posgrado (para estudiantes de primer año) que enseñó llamado "kit de herramientas para teóricos", que tiene mucho material básico que un estudiante de teoría debe saber. Puede esperar muchas de estas cosas hasta la escuela de posgrado para aprender, pero le dará una buena idea de lo que necesitará saber y algunos de los requisitos previos.

Lev Reyzin
fuente
20

Un paradigma común, aunque ciertamente no universal, para muchos investigadores exitosos en la comunidad TCS es el siguiente: Conocer algunos conceptos básicos a nivel de pregrado, como lógica, álgebra lineal, probabilidad, optimización, teoría de grafos, combinatoria, álgebra abstracta básica. Más allá de eso, no te obligues a aprender nada más hasta que realmente creas que lo necesitas para resolver ese problema con el que has estado luchando durante meses, o si crees que realmente disfrutarías aprender algo por el simple hecho de hacerlo.

"¿Cómo sé que lo necesito si nunca lo he visto antes?", ¿Preguntas? Buena pregunta. A veces tienes suerte y lo sientes: "Sabes qué, este subproblema que estoy tratando de resolver suena muy parecido a esa cosa de transformación de Fourier que Fred no quiere callar. Tendré que comprobarlo o atrapar a Fred en una habitación y que me eche un vistazo rápido a lo básico ". Otras veces, atrapas a un grupo de personas más conocedoras que tú en una habitación, por ejemplo, dando una charla en el seminario o algo así, y te quejas de cómo no puedes resolver este problema hasta que Fred interviene con "Hey, apuesto a que puede resolver esto con el Análisis de Fourier. Déjame mostrarte cómo ". Al final, obtienes un documento conjunto con Fred, aprendiste algo nuevo, y tú y Fred son los mejores amigos ahora y salen a beber cada dos sábados por la noche.

TCSgradstudent
fuente
18

¡Creo que una lista de campos de matemáticas que no son útiles sería mucho más corta que una lista de campos que sí lo son! No se me ocurre ninguno.

Estudie cualquier matemática que parezca interesante y / o lo que parezca que necesita en este momento. Incluso si no lo usas directamente, te ayudará a aprender otras cosas que haces.

Jeffε
fuente
44
Secundaré esta respuesta. Cualquier matemática que encuentre más interesante lo guiará a los problemas que son más interesantes, así como a los problemas que está bien preparado para resolver.
Derrick Stolee
9

La teoría de números no ha sido mencionada, pero es una herramienta muy importante para muchas construcciones teóricas de complejidad y criptografía.

arnab
fuente
6

La teoría de la representación de grupos finitos (también sobre campos finitos) puede ser sorprendentemente útil para diversas tareas, que incluyen:

  • algoritmos de multiplicación de matrices ( Cohn - Kleinberg-Szegedy-Umans )

  • construcción de códigos decodificables localmente (ver, por ejemplo, este documento de Klim Efremenko)

  • aplicaciones en computación cuántica (problema de subgrupos ocultos para grupos no belgas, método adversario multiplicativo)

Sn

Marcin Kotowski
fuente
no olvide las construcciones deterministas de los gráficos de expansión
Sasho Nikolov
¿Te refieres a construcciones algebraicas usando la propiedad (T) a la Lubotzky? En ese caso, esto tiene un sabor algo diferente a los ejemplos anteriores (no use irreps de grupos finitos).
Marcin Kotowski
4

Recomiendo leer el libro de Garey y Johnson

Computadoras e Intractabilidad: una guía para la teoría de la completitud NP .

Esto se puede leer con muy pocos antecedentes matemáticos. Creo que es un placer leer este libro, y lo recomendaría como primer libro sobre Papadimitriou y Arora / Barak. Una vez que haya leído esto, puede sumergirse en los otros libros e identificar varias partes de las matemáticas que necesita para comprender los temas avanzados que le interesan.

Emil
fuente
1
Aprendí la complejidad de este libro, pero lo encuentro desequilibrado, con muchos detalles incómodos pero en última instancia sin importancia, pero carece de la cobertura de temas que eran importantes incluso en el momento en que se escribió el libro. Por otro lado, ocasionalmente es un trabajo de referencia importante. En contraste, el texto de Kozen mencionado en otra respuesta es claro, completo y moderno.
András Salamon
1

Érase una vez el curso de nivel universitario CS464 (2002) en UWaterloo CS utilizó la Complejidad Computacional de Christos H. Papadimitriou , Addison-Wesley, 1994.

Los temas de fondo enumerados incluyen máquinas de Turing, indecidibilidad, complejidad de tiempo y completitud de NP.

Para el fondo, busque en su biblioteca cerca de QA267.G57 (La introducción de la teoría de la computación de Goddard , basada en una lectura rápida o dos y su disponibilidad para mí, parece cubrir el lado CS del fondo; tengo la sensación de que hay un conjunto y un grupo la teoría del lado matemático puro también sería útil).

josh0
fuente
2
Desearía tener suficiente reputación para votar. ¿Por qué esas referencias a una universidad y su biblioteca?
Alessandro Cosentino
2
FWIW, QA267.G57 es un número de llamada de la Biblioteca del Congreso, que es un estándar de biblioteca ampliamente utilizado. No es específico de la Universidad de Waterloo (excepto posiblemente por los dígitos finales).
Emil Jeřábek