Estoy leyendo la prueba desde aquí y me topé con un problema técnico (pero crucial). Sé que esto es bastante específico y el contexto es problemático, pero no pude resolverlo yo mismo.
En las páginas 51 y 55, después de presentar los verificadores "estándar", se vuelven a modificar los verificadores para verificar las asignaciones divididas.
En el primer caso (p. 51) verifican que están del código polinomial, y luego usan la Algebraización (+ Zero-Testers) para construir una familia de polinomios (con una Suma- Compruebe la propiedad relacionada con la fórmula de entrada) de que cada uno puede evaluarse en un punto dado 3 valores de cada uno de (las palabras de código del armario de código polinómico a ).
En el segundo caso (p. 55) comprueban que son -cerca de ser lineal, y entonces definir una función que ser una suma especial de modo que pueda evaluarse en un punto dado valores de cada uno de (las funciones lineales se en ).
Luego, en ambos casos, realizan pruebas (Sum-Check o Tensor + Hadamard) sobre los valores de un polinomio aleatorio en la familia / .
Mi problema es que el procedimiento para la reconstrucción de los valores requeridos de cada uno de puede proporcionar valores incorrectos con alguna probabilidad constante no despreciable . Además, la probabilidad de que todos los valores se reconstruyan correctamente es muy baja, solo para alguna constante . Y esto es cierto para ambos casos.
Esto puede ser malo, ya que algunos de los pasos de los verificadores requieren obtener valores de la función objetivo / a polinomial de la familia whp
Entonces, necesitamos amplificar la probabilidad de éxito usando repetidamente el "procedimiento algebraico de reconstrucción" algunas veces para cada .
Ahora, esto significa que la explosión en la complejidad de la consulta de la subrutina (en relación con la complejidad de la consulta de los verificadores originales) es ligeramente mayor que , es decir, es (en contraste con el "garantizado" - "deseado" explosión en la declaración de los teoremas).
¿Es esto un problema o me estoy perdiendo algo (que probablemente sea)
fuente
Respuestas:
La complejidad de la consulta utilizada en este documento es y .O(1) O(poly(logn))
Para Lemma 3.1 hay una nota de que la complejidad de la consulta utilizada es .O(1)
Si la pregunta es cómo Lemma 3.1 se generaliza a la complejidad de consulta no constante, esto presenta un problema fuera de .O(poly(f(n)))
Este problema se evita al componer un verificador que reduce la complejidad de la consulta a (Lema 4.4).O(1)
fuente