¿Alguien puede proporcionar una explicación concisa del enfoque GCT de Mulmuley comprensible para los no expertos? Una explicación que sería adecuada para una página de Wikipedia sobre el tema (que es un trozo en este momento). Motivación: estoy "co-leyendo" el libro de computación cuántica de...
A veces se afirma que la Teoría de la Complejidad Geométrica de Ketan Mulmuley es el único programa plausible para resolver las preguntas abiertas de la teoría de la complejidad como la pregunta P vs. NP. Ha habido varios comentarios positivos de famosos teóricos de la complejidad sobre el...
Parece que la teoría de la complejidad geométrica requiere mucho conocimiento de las matemáticas puras, como la geometría algebraica, la teoría de la representación. Si bien soy estudiante de CS y NO tengo clases de matemáticas muy abstractas y puras, estoy interesado en este programa. ¿Existe...
Según tengo entendido, el programa de teoría de la complejidad geométrica intenta separar al demostrar que el funcionamiento de una matriz de valores complejos es mucho más difícil de calcular que el determinante.VP≠VNPVP≠VNPVP \neq VNP La pregunta que tuve después de hojear los documentos de GCT:...
En esta publicación invitada de Josh Grochow en el complejo weblog, informa sobre un taller reciente dedicado a GCT que se celebró en Princeton en julio. Varios de los asistentes argumentaron que deberíamos usar GCT para atacar problemas más fáciles que vs. N P para construir la intuición y ver si...
Recientemente, Ryan Willams demostró que la constructividad en la prueba natural es inevitable para derivar una separación de clases de complejidad: y . NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} La constructividad en la prueba natural es una condición que satisface todas las pruebas combinatorias...
La redacción exacta del título se debe a Anand Kulkarni (quien propuso que se creara este sitio). Esta pregunta se hizo como una pregunta de ejemplo, pero tengo una curiosidad increíble. Sé muy poco acerca de la geometría algebraica y, de hecho, solo tengo una comprensión superficial y de pregrado...
Me preguntaba qué documentos debería leer para entender esta pregunta Una conexión inesperada con otras áreas de las matemáticas, como la geometría algebraica o la cohomología superior. Quizás incluso un área de matemáticas aún no desarrollada. Quizás alguien desarrolle una dirección...
La complejidad del circuito de profundidad limitada es una de las principales áreas de investigación dentro de la teoría de la complejidad del circuito. Este tema tiene su origen en resultados como "la función de paridad no está en AC0AC0AC^{0} " y "la función mod no es calculada por ", donde es la...
Mi pregunta es sobre los teoremas 4.1 y 4.2 en "Geometric Complexity Theory V" . El primer teorema establece que existe un algoritmo EXPSPACE para construir hsop para (ver definiciones en el documento) en C (de hecho, en un campo arbitrariamente cerrado algebraico de característica cero).Δ [ det ,...
Contexto: según tengo entendido, en la teoría de la complejidad geométrica, la existencia de obstrucciones sirve como un certificado de prueba, por así decirlo, de la inexistencia de un circuito computacional eficiente para la función explícita y difícil en el problema del límite inferior en...