Es significativo para la teoría de la complejidad geométrica.
La teoría de la complejidad geométrica es un intento de formalizar [matemáticas] \ text {P} \ neq \ text {NP} [/ math] en términos de objetos puramente algebraicos. En particular, la esperanza es que uno pueda reducir el tiempo de NP a un cierto problema de álgebra (por ejemplo, encontrar las raíces de alguna ecuación restringida) y luego usar métodos formales de geometría algebraica para obtener una prueba de este caso. Se sabe que el paso de reducción de un problema NP genérico a un problema algebraico existe (por ejemplo, hay un problema algebraico NP-completo de este tipo). [0]
Como primer paso para entender hacia dónde nos pueden llevar tales técnicas, una resolución de la conjetura permanente vs.determinante mostrará si esta idea puede probar otras conjeturas, como [matemáticas] \ # \ text {P} \ not \ subset \ text {NC} [/ matemáticas]. Como señala Justin Rising, el cálculo del permanente es [matemáticas] \ # \ text {P} [/ matemáticas] completo, por lo que el problema permanente vs. determinante sirve como el problema de decisión algebraico para el [matemáticas] \ # \ texto Conjetura {P} \ not \ subset \ text {NC} [/ math].
- ¿Es posible iterar a través de todos los números reales en [a, b] en cualquier lenguaje de programación? ¿Se acerca algo?
- Tienes 25 caballos y quieres elegir los 3 caballos más rápidos de esos 25. En cada carrera, solo 5 caballos pueden correr al mismo tiempo porque solo hay 5 pistas. ¿Cuál es el número mínimo de carreras requeridas para encontrar los 3 caballos más rápidos sin usar un cronómetro?
- ¿Qué están resolviendo realmente los mineros de Bitcoin? ¿Qué tipo de problemas matemáticos están resolviendo y qué logran al resolverlos?
- ¿Es importante entender cómo se derivan los teoremas específicos, o es suficiente entender solo cómo usarlos?
- ¿Se pueden programar las computadoras con 0,1 y 2? ¿Qué tal 0,1,2 y 3? ¿O son todos los programas manipulaciones de 0 y 1? Nuevos detalles añadidos para explicar.
Entonces, ¿cuál es el problema permanente versus el determinante?
El problema permanente versus determinante pregunta:
Dada una matriz [matemática] n \ veces n [/ matemática] [matemática] A [/ matemática] ¿existe una matriz [matemática] m \ veces m [/ matemática] [matemática] B [/ matemática] tal que [matemática ] \ text {perm} (A) = \ det (B) [/ math]?
Si dicha matriz existe y [math] m \ in \ text {poly} (n) [/ math], entonces se dice que el permanente es polinomialmente reducible. La conjetura permanente versus determinante afirma que no existe tal reducción.
Ketan Mulmuley ha encabezado muchos de los avances en la teoría de la complejidad geométrica. Para una revisión, ver [1]
[0] Teoría de la complejidad geométrica I: un enfoque de P. vs. NP y problemas relacionados
[1] Página en uchicago.edu
