Implicaciones matemáticas de las conjeturas de la teoría de la complejidad fuera de TCS

25

¿Conoces consecuencias interesantes de conjeturas (estándar) en la teoría de la complejidad en otros campos de las matemáticas (es decir, fuera de la informática teórica)?

Preferiría respuestas donde:

  • la conjetura de la teoría de la complejidad es lo más general y estándar posible; También estoy de acuerdo con las consecuencias de la dureza de problemas específicos, pero sería bueno si se cree que los problemas son difíciles (o al menos se han estudiado en más de un par de artículos)

  • la implicación es una afirmación que no se sabe que es verdadera incondicionalmente, u otras pruebas conocidas son considerablemente más difíciles

  • cuanto más sorprendente sea la conexión, mejor; en particular, la implicación no debería ser una declaración explícita sobre algoritmos

Las conexiones tipo "si los cerdos pudieran volar, los caballos cantarían" también están bien, siempre y cuando los cerdos voladores provengan de la teoría de la complejidad y los caballos cantantes de algún campo de las matemáticas fuera de la informática.

Esta pregunta es, en cierto sentido, "la inversa" de una pregunta que teníamos sobre los sorprendentes usos de las matemáticas en la informática. Dick Lipton tuvo una publicación en el blog exactamente en este sentido: escribe sobre las consecuencias de la conjetura de que la factorización tiene una gran complejidad de circuito. Las consecuencias son que ciertas ecuaciones de diofantina no tienen soluciones, un tipo de afirmación que puede ser muy difícil de probar incondicionalmente. La publicación se basa en el trabajo con Dan Boneh, pero no puedo encontrar un artículo.

EDITAR: Como Josh Grochow señala en los comentarios, su pregunta sobre las aplicaciones de TCS a las matemáticas clásicas está estrechamente relacionada. Mi pregunta es, por un lado, más permisiva, porque no insisto en la restricción "matemática clásica". Creo que la diferencia más importante es que insisto en una implicación probada de una conjetura de complejidad a una declaración en un campo de las matemáticas fuera de TCS. La mayoría de las respuestas a la pregunta de Josh no son de este tipo, sino que proporcionan técnicas y conceptos útiles en matemáticas clásicas que fueron desarrolladas o inspiradas por TCS. Sin embargo, al menos una respuesta a la pregunta de Josh es una respuesta perfecta a mi pregunta: el artículo de Michael Freedmanque está motivado por una pregunta idéntica a la mía, y demuestra un teorema en la teoría de nudos, condicionada a . Argumenta que el teorema parece estar fuera del alcance de las técnicas actuales en la teoría de nudos. Según el teorema de Toda, si P # P = N P, entonces la jerarquía polinómica se colapsa, por lo que la suposición es bastante plausible. Estoy interesado en otros resultados similares.P#PNPP#P=NPAGS

Sasho Nikolov
fuente
Relacionado: implicaciones, no para las matemáticas, sino para la "realidad física"
Austin Buchanan
¿Es esto lo mismo que cstheory.stackexchange.com/questions/149/… ? ¿O esta pregunta pretende ser más amplia que esa?
Joshua Grochow
3
@Joshua, hay cierta superposición, pero creo que son incomparables. Por un lado, no insisto mucho en las matemáticas "clásicas", es decir, los resultados no complejos en mecánica cuántica están bien. Por otro lado, me gustaría implicaciones directas de las conjeturas CC a los teoremas matemáticos fuera de TCS, mientras que muchas de las respuestas a su pregunta son sobre técnicas desarrolladas en TCS que nos volvieron útiles en matemáticas clásicas. Aún así, cstheory.stackexchange.com/a/163/4896 es una respuesta perfecta a mi pregunta. ¿Demasiada superposición?
Sasho Nikolov
1
TalL vez debería haber publicado mi respuesta a la pregunta de Josh aquí: la conjetura L de Bürgisser implica resultados en curvas elípticas .
Bruno
1
@ Sasho: Creo que está bien. Gracias por aclararlo. (Por cierto, cuando dije "clásico" en mi otra pregunta, no quise excluir la mecánica cuántica; de hecho, la teoría cuántica de campos y el álgebra cuántica son dos temas matemáticos importantes hoy en día, estudiados en una gran cantidad de (incluso los mejores) departamentos de matemáticas .)
Joshua Grochow

Respuestas:

14

Aquí hay otro ejemplo de la teoría de grafos. El teorema del gráfico menor nos dice que, para cada clase de gráficos no dirigidos que se cierra debajo de menores, hay un conjunto de obstrucción finita O b s ( G ) tal que un gráfico está en G si y solo si no contiene un gráfico en O b s ( G ) como menor. Sin embargo, el teorema de la gráfica de menor importancia es inherentemente no constructiva y no nos dice nada acerca de lo grande que estos conjuntos son de obstrucción, es decir, el número de gráficos que contiene para una elección particular de G .GObs(G)solOsis(sol)sol

En Too Many Minor Order Obstructions , Michael J. Dinneen demostró que bajo una conjetura teórica de complejidad plausible, se puede demostrar que los tamaños de varios de estos conjuntos de obstrucción son grandes. Por ejemplo, considere la clase parametrizada de gráficos de género como máximo k . A medida que k aumenta, podemos esperar que los conjuntos de obstrucción O b s ( G k ) se vuelvan cada vez más complicados, pero ¿cuánto? Dinneen demostró que si la jerarquía polinómica no colapsa a su tercer nivel, entonces no hay un polinomio p tal que el número de obstrucciones en O b s (solkkkOsis(solk)pagsestá delimitado porp(k). Dado que el número de obstrucciones menores para tener el género cero (es decir, ser plano) es solo dos ( O b s ( G 0 )={ K 5 , K 3 , 3 }), este crecimiento superpolinómico no es inmediatamente obvio (aunque lo creo puede ser probado incondicionalmente). Lo bueno del resultado de Dinneen es que se aplica a los tamaños de los conjuntos de obstrucción correspondientes acualquierconjunto parametrizado de ideales menores G k para los cuales decidir elkmás pequeñoOsis(solk)pags(k)Osis(sol0 0)={K5 5,K3,3}solkkpara el cual es NP-duro; En todos estos ideales menores parametrizados, los tamaños de los conjuntos de obstrucción deben crecer de forma superpolinómica. solsolk

Bart Jansen
fuente
Gracias Bart! Esto es muy interesante. Acepto su respuesta como la más votada. ¡Gracias a todos por las respuestas!
Sasho Nikolov
6

Aquí hay un ejemplo: la complejidad computacional y la asimetría informativa en los productos financieros de Arora, Barak y Ge muestran que puede ser computablemente insoluble (es decir, NP-hard) valorar los derivados correctamente: usan el subgráfico más denso como un problema difícil incrustado.

En la misma línea y mucho antes se encuentra el famoso artículo de Bartholdi, Tovey y Trick sobre la dureza de manipular una elección.

Suresh Venkat
fuente
2
Claro, hasta cierto punto, todavía son resultados de complejidad (con implicaciones sociales). Tenía en mente resultados que no son sobre algoritmos. Aún así, ¡ambos son geniales!
Sasho Nikolov
No estaba del todo seguro de lo que estabas buscando. Supongo que quieres algo como lo contrario de "las curvas cerradas de tiempo colapsan cuántica y clásica"?
Suresh Venkat
1
En realidad, el resultado de CTC es un ejemplo perfecto. Quiero decir ni siquiera lo contrario, sino la afirmación en sí misma en contraposición: si cuántica y clásica no colapsan, entonces no existen CTC (polinomiales).
Sasho Nikolov
1
¿Estás diciendo que debería publicar una nueva respuesta :)?
Suresh Venkat
Creo que estoy diciendo eso :)
Sasho Nikolov
5

S2kS2k2δk

Está muy en el espíritu del artículo de Mike Freedman mencionado anteriormente.

Izaak Meckler
fuente
-6

Parece que muchas preguntas de separación de clases de complejidad TCS tienen implicaciones importantes en las matemáticas. La pregunta P =? NP en particular parece tener conexiones muy profundas en muchos campos y esto incluye las matemáticas. Algunos casos notables en esta área:

vzn
fuente
3
no entendió la pregunta: todos los resultados que menciona son sobre la complejidad. Quiero una consecuencia no compleja de una declaración en la teoría de la complejidad
Sasho Nikolov