Enfoque cohomológico de la complejidad booleana.

33

Hace unos años, Joel Friedman realizó algunos trabajos relacionados con los límites del circuito inferior a la cohomología de Grothendieck (ver documentos: http://arxiv.org/abs/cs/0512008 , http://arxiv.org/abs/cs/0604024 ) ¿Esta línea de pensamiento ha aportado nuevas ideas sobre la complejidad booleana, o sigue siendo más bien una curiosidad matemática?

cc.complexity-theory lower-bounds circuit-complexity boolean-functions Marcin Kotowski
fuente
44
Tengo mucha curiosidad por ver la respuesta a esto. Por supuesto, lo más fácil sería enviar un correo electrónico a Joel Friedman :)
Suresh Venkat

Respuestas:

28

Me comuniqué con Joel Friedman hace aproximadamente 3 años sobre este tema. En ese momento dijo que su enfoque no había conducido a ninguna nueva comprensión significativa de la teoría de la complejidad, aunque todavía pensaba que era una táctica prometedora.

Básicamente, Friedman intenta reformular los problemas de la complejidad del circuito en el lenguaje de las gavillas en una topología de Grothendieck. La esperanza es que este proceso permita que la intuición geométrica se aplique al problema de encontrar los límites inferiores del circuito. Si bien vale la pena verificar si este camino conduce a alguna parte, existen razones heurísticas para ser escépticos. La intuición geométrica funciona mejor en el contexto de variedades suaves, o cosas que son lo suficientemente similares a las variedades suaves que la intuición no se descompone por completo. En otras palabras, necesita cierta estructura para que la intuición geométrica se establezca. Pero los límites inferiores del circuito, por su propia naturaleza, deben enfrentar cálculos arbitrarios, que son difíciles de analizar precisamente porque parecen no tener estructura. Friedman admite desde el principio que las topologías de Grothendieck que considera son altamente combinatorias y muy alejadas de los objetos habituales de estudio en geometría algebraica.

Como comentario adicional, diría que es importante no entusiasmarse demasiado con una idea solo porque utiliza maquinaria desconocida y de alta potencia. La maquinaria puede ser muy efectiva para resolver los problemas para los que fue diseñada, pero para que sea útil para atacar un problema difícil conocido en otro dominio, debe haber algún argumento convincente por qué la maquinaria extranjera está bien adaptada para abordar los problemas fundamentales. obstáculo en el problema de interés.

Timothy Chow
fuente
44
Por supuesto, los esfuerzos de Mulmuley están en líneas "similares" en el sentido de usar "estructuras lisas", pero está buscando problemas que admitan invariantes geométricos agradables para empezar.
Suresh Venkat
2
@Suresh: Tiene razón en que el enfoque de Mulmuley-Sohoni es diferente, pero el problema fundamental de hacer frente a un cálculo arbitrario todavía está al acecho, por lo que es justo preguntar cómo se espera llegar a un acuerdo con él. Por el momento, no creo que nadie lo sepa realmente, por eso la gente de GCT no promete avances espectaculares en el corto plazo.
Timothy Chow
en efecto. es interesante ver un artículo de STOC 2011 que usa GCT para los límites de multiplicación de matrices (y Ketan había mencionado este resultado en su tutorial en FOCS)
Suresh Venkat
1
@Suresh: Si estás hablando del artículo de Buergisser / Ikenmeyer, creo que dice mucho más sobre los límites del enfoque de GCT que sobre cómo probar los límites inferiores.
5501
1
@Neel, no tengo una respuesta, pero me pregunto si esto podría merecer una pregunta propia.
Suresh Venkat
16

Creo que Timothy Chow tiene toda la razón. Tengo mi propia lista personal de ideas que involucran variedades "suaves", o conceptos como contar componentes conectados o monomios que van con los pocos peldaños inferiores de la "escalera de cohomología" --- todos ellos demostraron no ser predicados de dureza por ( variaciones sobre) la construcción de Mayr-Meyer que muestra EXPSPACE-completitud de varios problemas relacionados con GCT. ¡Mi único riff en su último párrafo es que creo que se necesita algún tipo de maquinaria de alta potencia ...!

Kenneth W. Regan
fuente