He estado leyendo un poco sobre el método de suma de cuadrados (SOS) de la encuesta de Barak & Steurer y las notas de clase de Barak . En ambos casos, barren problemas de precisión numérica debajo de la alfombra.
Desde mi comprensión (ciertamente limitada) del método, lo siguiente debería ser cierto:
Dado cualquier sistema de igualdades polinómicas sobre variables de valor real , donde todos los parámetros son ( , y grado de cada restricción), el grado- " " ( ) El método SOS encuentra una asignación satisfactoria de las variables o prueba que no existe ninguna en el tiempo .
Mi primera pregunta es si la afirmación anterior es cierta (¿hay algún argumento ingenuo que no use SOS para resolver esto?). La segunda pregunta es dónde encaja la precisión numérica. Si quiero obtener una asignación que satisfaga todas las restricciones dentro de la precisión aditiva , ¿cómo depende el tiempo de ejecución de ? En particular, ¿es polinomial?
La motivación para esto es, por ejemplo, aplicar un enfoque de divide y vencerás en un sistema grande hasta que el caso base sea un sistema de tamaño .
EDITAR: De Barak-Steurer, parece que el " algoritmo de suma de cuadrados de grado " en la página 9 (y los párrafos que lo conducen) definen problemas para soluciones sobre R , y de hecho la definición de un pseudo -Distribución en la sección 2.2 es más de R . Ahora veo en Lemma 2.2, sin embargo, que no se garantiza una solución / refutación en el grado 2 n sin variables binarias.
Entonces puedo refinar mi pregunta un poco. Si sus variables no son binarias, la preocupación es que la secuencia de salidas no es finita (¿tal vez ni siquiera un aumento monotónico?). Entonces la pregunta es: ¿ φ ( l ) sigue aumentando? Y si es así, hasta qué punto se tiene que ir a conseguir una precisión aditivo ε ?
Aunque esto probablemente no cambia nada, me he enterado de mi sistema es satisfiable (no hay refutación de cualquier grado), así que estoy realmente preocupado por lo grande que tiene que ser. Finalmente, estoy interesado en una solución teórica, no en un solucionador numérico.
fuente
Respuestas:
Aquí está el comentario de Boaz Barak sobre el tema:
fuente
Creo que mi respuesta es probablemente insuficiente, pero sigue siendo por completo (aunque vea los comentarios de Boaz a continuación para probablemente una mejor respuesta)
Cuando nos limitamos a las variables booleanas, la afirmación se puede ver cuando para todo i ∈ [ n ] con la observación de que grado 2 n(x2i−1)∈E i∈[n] 2n pseudodistribuciones de son distribuciones reales, es decir, supongamos que tiene una pseudodistribución sobre soluciones x de sus igualdades polinómicas E satisfactoria:μ(x) x E
y ∑ x ∈ { - 1 , 1 } n μ ( x ) p 2 ( x ) ≥ 0 para todos los polinomios p con grado máximo n∑x∈{−1,1}nμ(x) ∑x∈{−1,1}nμ(x)p2(x)≥0 p n
Pero los polinomios de grado incluyen el polinomio indicador (por ejemplo, x 1 = 1 , x 2 = - 1 , x 3 = 1 tiene 2 - 3 ( 1 + x 1 ) ( 1 - x 2 ) ( 1 + x - 1 , 1 } n , por lo que concluimos que μ es una distribución real sobre las soluciones de E. Grado ℓn x1=1,x2=−1,x3=1 que es todo cero en otro lugar y 1 en esa asignación). Entonces μ ( x ) ≥ 0 para todo x ∈ {2−3(1+x1)(1−x2)(1+x3) μ(x)≥0 x∈{−1,1}n μ E ℓ pseudo-distribuciones se pueden encontrar mediante el uso de programación semidefinida para encontrar un grado asociado operador pseudo-expectativa en n O ( ℓ ) tiempo, por lo que podemos encontrar la distribución realℓ nO(ℓ) en el tiempo n O ( n ) usando ese pseudo expectativa (ahora una expectativa real) para encontrar todos los momentos de μ .μ nO(n) μ
Entonces, si , entonces puede encontrar una distribución de soluciones a E en O ( 1 ) tiempo. Por supuesto, la búsqueda de fuerza bruta garantiza lo mismo.|E|=O(1) E O(1)
Sin embargo, si las soluciones no son necesariamente booleanas, entonces las pseudo-expectativas de grado no son suficientes para encontrar una distribución sobre las soluciones. Como se puede ver arriba, la prueba de que las pseudodistribuciones de grado 2 n son distribuciones reales depende del hecho de que los polinomios de grado n son suficientes para 'seleccionar' asignaciones individuales, lo que no es cierto en general. Otra forma de verlo es que se consideran polinomios de variable booleana2n 2n n , entonces el grado de cada monomio es como máximon.mod(x2i) n
Por ejemplo, uno podría considerar reemplazar cada variable binaria con una variable de 4 arios, digamos incluyendo . Entonces tendría que tener un grado 4 n de pseudo-expectativa para garantizar la recuperación de una distribución sobre soluciones.(x2i−1)(x2i−4)∈E 4n
Ahora, para garantías teóricas, parece que aproximarse a la raíz de un sistema de polinomios también se conoce como el problema número 17 de Smale, y aparentemente hay un algoritmo de tiempo polinomial aleatorio (Las Vegas) que resuelve esto: consulte http://arxiv.org /pdf/1211.1528v1.pdf . Tenga en cuenta que esto parece estar en el modelo Blum-Shub-Smale, por lo que las operaciones reales son primitivas. No estoy seguro si esto le da la garantía que necesita.
fuente