Consecuencia de PIT sobre no tiene un algoritmo eficiente

11

Dado modo que los coeficientes de están delimitados por , hace ¿sostener?p , q B p qp(x1,,xn),q(x1,,xn)Z[x1,,xn]p,qBpq

El lema de Schwartz-Zippel se aplica aquí, ya que es válido para campos generales y y hay un algoritmo aleatorio eficiente para este problema.ZQ

Esperamos que este problema tenga una desrandomización eficiente.

¿Cuál es la consecuencia si este problema no tiene una desrandomización eficiente?

András Salamon
fuente
1
¿Cómo se y dan? qpq
@RickyDemer ¿Cómo se da en las pruebas de identidad polinomiales regulares?
¿El resultado de Kabanets-Impagliazzo no dice que NO esperamos una desrandomización eficiente?
Suresh Venkat
1
Si. Pensé que mencionaría eso ya que con la representación estándar , diferentes cadenas representan elementos distintos.
3
@SureshVenkat: Kabanets & Impagliazzo demostraron varias cosas, entre ellas: 1. Si PIT puede ser aleatorizado, NEXP no tiene circuitos de polisización (booleanos) o el permanente no tiene circuitos de polisización (aritmética); 2. Si el permanente requiere circuitos de tamaño superpoly, el PIT se puede desrandomizar "débilmente". Dado que las conclusiones de 1. generalmente se conjeturan así como la premisa de 2., diría que, en contra de usted, el resultado de KI dice que ESPERAMOS una desrandomización eficiente.
Bruno

Respuestas:

8

Como PIT está en , si no hay una desrandomización eficiente, entonces (y, en particular, , pero eso es no es tan sorprendente, ya que esperamos que sea cierto de todos modos). Esto también implica, por supuesto, que , por lo que cualquier cosa que implique convierte en falso. Por ejemplo, no existen generadores de números pseudoaleatorios suficientemente fuertes, y tendría circuitos de tamaño subexponencial!PR P PN P PB P P P = B P P E = D T I M E ( 2 O ( n ) )coRPPRPPNPPBPPP=BPPE=DTIME(2O(n))

Joshua Grochow
fuente
Entonces, ¿esto se mantiene independientemente del campo de tierra (coeficientes en donde con algunos límites en los coeficientes)? p{2,3,5,7,}{}Qpp{2,3,5,7,}{}
De hecho, como ya señaló Schwarz-Zippel-DeMillo-Lipton se aplica sobre campos arbitrarios, y todo lo que necesita es un límite en el grado de los polinomios (no el tamaño de los coeficientes ni el tamaño del circuito). Con un número muy pequeño de excepciones, PIT generalmente significa la versión limitada por grado (grado limitado por un polinomio en el número de variables).
Joshua Grochow
Puede ser una tontería. Usted mencionó la independencia en el tamaño de los coeficientes y el tamaño del circuito. Supuse que el tamaño depende del grado y tamaño de coeff. ¿Me equivoco?
2
El tamaño del circuito puede depender del tamaño de coeff., Dependiendo de su modelo (el modelo del que depende generalmente se llama "sin constante"). El tamaño del circuito solo depende muy poco del grado, en el sentido de que el tamaño es al menos logarítmico del grado, pero en realidad el algoritmo coRP que sale de SZDL es casi un grado. Ni siquiera depende de las funciones que se otorgan como circuitos, solo de alguna forma en la que puedan evaluarse fácilmente ("recuadro negro").
Joshua Grochow
Gracias. Es un poco preocupante que derandomization puede hacerse sin pérdida de eficiencia, incluso si los propios coeficientes pueden ser complicados constructivamente
0

Te estás preguntando acerca de los problemas generales aquí. Un número natural puede representarse canónicamente en notación unaria, pero esta representación es bastante ineficiente en cuanto al espacio. También podría representarlo en notación binaria, que es más eficiente en el espacio, pero ya no es canónica, porque también podría usar notación tenaria o notación decimal. Pero observe que la representación por circuitos no es significativamente menos eficiente que la notación binaria, ver por ejemplo

101101 = (((1+1)*(1+1)+1)*(1+1)+1)*(1+1)*(1+1)+1

Y observe que (...)*(1+1)puede ser reemplazado por x:=(...) in x+x, por lo que ni siquiera necesita multiplicación para esto. Pero debido a que tiene multiplicación, incluso puede representar eficientemente números como 1011^101101. También tenga en cuenta que puede sumar, restar y multiplicar números de manera eficiente en esta representación. Pero esta representación no se limita a los números, incluso funciona exactamente de la misma manera para funciones polinomiales multivariadas. Y para los polinomios, es incluso una representación bastante natural, porque los polinomios son el álgebra libre para los anillos conmutativos, y la representación como circuito se puede usar para cualquier álgebra libre.

Pero volvamos a los números (naturales) por un momento, números como . NJ Wildberger ha escrito algunas diatribas ultrafinitistas, por ejemplo , la teoría de conjuntos: ¿Deberías creer? . En la sección ¿Pero qué pasa con los números naturales? se admite la existencia de números como , porque obviamente puedes escribirlos. Pero la existencia de casi todos los números naturales entre y c 0 cc=1010101010c0cse niega, porque la mayoría de esos números contendrían más información de la que posiblemente podría representar el universo físico. La mayor parte de la queja me hizo reír, pero este punto me hizo pensar. Filósofos como Willard Van Orman Quine han protestado contra la afirmación de la existencia de posibilidades no actualizadas, entre otras porque conducen a elementos desordenados que no pueden decirse de manera significativa que sean idénticos entre sí y distintos. Así que me pareció bastante razonable preguntarme acerca de las presentaciones de números para las cuales todavía se realizan sumas, restas y multiplicaciones, y al menos determinar significativamente si dos números son distintos entre sí. La representación del circuito logra esto ...

Volver a polinomios y representaciones de circuitos de álgebras libres. Aquí hay algunas preguntas generales:

  • ¿Esta representación de un álgebra libre siempre permite pruebas de identidad probabilísticas eficientes, o se limita a anillos conmutativos?
    -> Las pruebas de identidad a menudo son incluso indecidibles: para , la red modular libre generada por elementos es infinita y, de hecho, tiene un problema verbal indecidible (Freese, Herrmann).n4n
  • ¿Existe un álgebra libre para el cual la prueba de identidad determinista eficiente invalidaría cualquier conjetura comúnmente creída, como P! = NP?
    -> Sí, la prueba de identidad para el álgebra libre para anillos conmutativos regulares es NP-completa. No me di cuenta de esto por mucho tiempo, mira abajo
  • ¿Las pruebas de identidad deterministas eficientes para (= el álgebra libre de anillos conmutativos) invalidarían cualquier conjetura interesante ?Z[x1,,xn]

Me pregunto especialmente sobre el álgebra libre para anillos conmutativos regulares aquí (es decir, anillos con una operación inversa generalizada), ya que permitirían representar números racionales y funciones racionales. Tenga en cuenta que si hubiéramos usado esta representación solo para números, entonces podríamos habernos preguntado si podemos probar de manera eficiente a < besta representación. Esta pregunta no tiene sentido para el anillo conmutativo libre, pero podría tener sentido para los polinomios, si los interpretamos en el contexto de los anillos libres parcialmente ordenados. Pero un anillo parcialmente ordenado es solo una estructura relacional en lugar de un álgebra, por lo que este es un tipo diferente de pregunta ...


El lema de Schwartz-Zippel se aplica aquí, ya que es válido para campos generales y y hay un algoritmo aleatorio eficiente para este problema.ZQ

Bueno, es cierto que el lema de Schwartz-Zippel se aplica aquí, y que existe un algoritmo aleatorio eficiente para este problema, pero estos dos hechos no están directamente relacionados. Recuerde que es fácil representar polinomios de manera eficiente como por un circuito. Entonces, si es el tamaño del circuito, entonces las magnitudes de los coeficientes de , o son fáciles de lograr. Dicho esto, la identidad polinómica probabilístico pruebas todavía funciona sobre . El límite en los coeficientes es algo así comon 7 2 n / 2 5 3 n / 3 Z B = exp ( exp ( n ) ) O ( log B )((33+3)3+x)3((22+5)3+x)2xn72n/253n/3ZB=exp(exp(n)), y solo necesita adivinar aleatoriamente un número primo que no divida simultáneamente todos los coeficientes. Existen suficientes números primos de orden para hacer esto de una manera probabilística eficiente.O(logB)


Me resultaría bastante sorprendente si PIT sobre pudiera ser aleatorizado. Pero una sorpresa similar me sucedió antes, cuando las pruebas de primalidad fueron desleatorizadas.Z[x1,,xn]

Por otro lado, también creo que puede usar cualquier generador razonable de números pseudoaleatorios y, por lo tanto, decidir PIT para todos los fines prácticos, si solo prueba lo suficiente. Solo creo que nunca puede deshacerse de la duda restante (infinitesimal pequeña), similar a los conjuntos de medida cero, que siguen siendo molestos al no estar vacíos.

Thomas Klimpel
fuente
quieres decir ? P!=NP
Estoy pensando en un problema de álgebra libre solamente pero no lo que está pensando