¿Cómo el enfoque geométrico de Mulmuley-Sohoni para producir límites inferiores evita producir pruebas naturales (en el sentido de Razborov-Rudich)?

22

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 de los obstáculos en juego en la pregunta P / poli versus NP (no relativizante, no algebrazing, probablemente no será una prueba natural) .

¿Qué hace que la geometría algebraica parezca que puede sortear este tipo de obstáculos? ¿Es solo una intuición experta en el campo o tenemos una buena razón para creer que el enfoque es fundamentalmente más poderoso que los enfoques anteriores? ¿Qué resultados más débiles ha logrado este enfoque?

Ross Snider
fuente

Respuestas:

19

[Contestaré la pregunta como se indica en el título, dejando la letanía de otras preguntas sobre GCT para otros hilos.] Probar las conjeturas que surgen en GCT parece que usará de manera crucial el hecho de que las funciones bajo consideración (determinantes y permanentes, y otros polinomios relacionados para P / poli y NP) se caracterizan por sus simetrías. Esta necesidad no es un resultado formal, sino una intuición expresada por varios expertos. (Básicamente, en ausencia de caracterización por simetrías, comprender la geometría algebraica y la teoría de la representación que surge es mucho más difícil).

Esto debería evitar a Razborov-Rudich porque muy pocas funciones se caracterizan por sus simetrías (evitando la condición de amplitud en la definición de pruebas naturales). Nuevamente, no he visto una prueba de esto, pero es una intuición que he escuchado expresada por varios expertos.

Ahora, sobre los números complejos, no está claro para mí que haya un análogo de Razborov-Rudich. Aunque la mayoría de GCT actualmente se enfoca en los números complejos, hay análogos en la característica finita (prometida en el próximo artículo GCT VIII). En una característica finita, uno podría probar una declaración de la forma "Muy pocas funciones se caracterizan por sus simetrías".


[En respuesta al comentario de Ross Snider, aquí hay una explicación de caracterización por simetrías.]

Primero, una explicación por ejemplo. Para el ejemplo, defina una función auxiliar . Si es una matriz de permutación, entoncesAqA y si A es diagonal, entonces q ( A ) = d e t ( A ) (producto de las entradas diagonales). Ahora, supongamos que p ( X ) es un grado homogéneo n polinomio en n 2 variables (que consideramos como los entrantes de unamatriz n × n Xq(A)=1Aq(A)=det(A)p(X)nn2norte×norteX) Si tiene las siguientes simetrías:pags

  • (transposición)p(X)=p(Xt)
  • para todos los pares de matrices ( A , B ) de modo que A y B sean matrices de permutación o matrices diagonales y q ( A ) q ( B ) = 1p(AXB)=p(X)(A,B)ABq(A)q(B)=1

entonces es un múltiplo constante de p e r m ( X ) para todas las matrices X . Por eso decimos que el permanente se caracteriza por sus simetrías.pags(X)pagsmirmetro(X)X

Más en general, si tenemos una (homogéneo) polinomio en m variables, entonces la G L m (el grupo de todos invertible m × m matrices) actúa sobre f por ( A f ) ( x 1 , . . . , x m ) = f ( A - 1 ( x 1 ) ,F(X1,...,Xmetro)metrosolLmetrometro×metroF para A G L m (donde estamos tomando las variables x 1 , . . . , X m como base para el m espacio vectorial dimensional en la que G L m actúa naturalmente). El estabilizador de f en G L m es el subgrupo Stab ( f ) = { A G(Af)(x1,...,xm)=f(A1(x1),...,A1(xm))AGLmx1,...,xmmGLmfGLm . Decimos que f se caracteriza por sus simetrías si se cumple lo siguiente: para cualquier polinomio homogéneo f en m variables del mismo grado que f , si A f = f para todo A Stab ( f ) , entonces f es un múltiplo constante de f .Stab(f)={AGLm:Af=f}ffmfAf=fAStab(f)ff

Joshua Grochow
fuente
Esto parece una gran respuesta, pero me temo que no entiendo un poco acerca de las simetrías de funciones (lo que significa que me faltan los detalles cruciales de la respuesta). ¿Podrías desentrañar cuál es la simetría de una función, por qué sería importante que muy pocas funciones se caractericen por ella (alias, por qué esto permitiría pasar por alto la condición de amplitud de Razborov)? También para que quede claro, su respuesta es que hay una mezcla. Hay razones por las cuales el enfoque parece prometedor, pero en última instancia, la evidencia de estas razones se debe en gran medida a la intuición experta.
Ross Snider
44
Agregué una explicación de caracterización por simetrías para usted. Incluso si es el caso de que muy pocas funciones se caractericen por sus simetrías, seguimos confiando en la intuición de los expertos de que la caracterización por simetrías será crucial para probar las conjeturas que surgen en GCT. Si este es realmente el caso, entonces las técnicas de prueba utilizadas en esas conjeturas solo funcionarían para una pequeña fracción de funciones, evitando así la condición de amplitud. (¿O no era eso lo que preguntabas?)
Joshua Grochow
Ooooh Epifanía registrada aquí. Muchas gracias. ¿Cómo no puedo aceptar esta respuesta?
Ross Snider
15

La respuesta de Joshua Grochow es buena, pero creo que vale la pena hacer un comentario más general. El resultado de Razborov-Rudich dice que si desea probar que alguna función booleana no está en , entonces (suponiendo que cree en su hipótesis criptográfica) debe usar alguna propiedad de esa función que no sea trivial para calcular o eso es compartido solo por un pequeño número de otras funciones booleanas. En la práctica, no es fácil encontrar propiedades adecuadas; sin embargo, la observación de Razborov-Rudich en realidad no descarta muchos planes generales de ataque en los límites inferiores del circuito, en ausencia de detalles concretos sobre la prueba prevista. Por ejemplo, supongamos que ingenuamente dijera que mi plan para demostrarP/poly implicó mostrar que S A T P / p o l y , y que tenía la intención de utilizar el hecho de que S A T es N P -completo. Este ingenuo "plan de ataque" es casi libre de contenido, pero Razborov-Rudich no lo descarta, porque lacompletitud N P no es una gran propiedad.NPP/polySATP/polySATNPNP

Para decirlo de otra manera, Razborov – Rudich generalmente no presenta un gran obstáculo en las primeras etapas de la planificación de una línea de ataque en los límites inferiores del circuito, siempre y cuando deje algo de espacio en su plan para eventualmente emplear "propiedades especiales" de sus funciones booleanas candidatas. Solo cuando se arremanga y trata de completar los detalles del argumento, la barrera de naturalización comenzará a levantar la cabeza en serio. Dado que GCT aún se encuentra en una etapa temprana de desarrollo, no deberíamos esperar preocuparnos mucho por la naturalización (aunque, por supuesto, vale la pena verificar que el programa GCT no esté condenado por razones triviales).

También puede consultar la exposición de GCT de Ken Regan , que incluye algunos comentarios sobre la barrera de naturalización.

Timothy Chow
fuente