Errores unilaterales en sistemas de prueba probablistic

10

En la mayoría de los sistemas de prueba probabilística (teorema PCP, por ejemplo), las probabilidades de error generalmente se definen del lado de los falsos positivos, es decir, una definición típica podría verse así: si , el verificador siempre acepta, pero en En otro caso, la probabilidad de rechazo es de al menos 1/2.xL

¿Hay algún problema al permitir que el error ocurra en el otro lado? Eso significa que el verificador siempre rechaza cuando debería, y no comete más que un error constante cuando necesita aceptar. Otra posibilidad obvia es permitir el error en ambos lados. ¿Estas definiciones serán equivalentes a las que se dan habitualmente? ¿O se comportan de manera diferente? O, para el caso, ¿existe un problema genuino al permitir los errores del otro lado?

Arnab
fuente
¿Por qué el voto negativo? Algunos PCP no tienen una integridad perfecta. Por otro lado, hay algunas reducciones con una solidez perfecta pero no una integridad perfecta ("Bits libres, etc.", Bellare + Goldreich + Sudán, p. 21, último párrafo).
Yuval Filmus
@Yuval Filmus: Hay muchas versiones del artículo que mencionaste. ¿A qué versión te refieres?
Tsuyoshi Ito
Muchas gracias a ambos por las respuestas. Supongo que el voto negativo vino de la percepción de que no es una pregunta de "investigación". De hecho no lo es. De todos modos, ni siquiera puedo votar la respuesta con mi puntaje de reputación, que incluso se redujo hoy :)
Arnab
@TsuyoshiIto En la versión 2, se encuentra en la parte inferior de la página 22 (página 24 del archivo).
Yuval Filmus
1
No tengo idea. Simplemente busqué en Google "perfecto sonido".
Yuval Filmus

Respuestas:

12

Permitir errores de integridad no tiene ningún problema, y ​​a menudo se considera. Aquí hay algunos consejos .

Por otro lado, en términos generales, no permitir errores de solidez elimina significativamente la potencia de un modelo.

En el caso de los sistemas de prueba interactivos, la anulación del error de solidez hace que la interacción sea inútil, excepto para la comunicación unidireccional de un probador a un verificador; es decir, IP con perfecta solidez es igual a NP. Esto puede mostrarse considerando una máquina NP que adivina los bits aleatorios del verificador y la transcripción de la interacción que hace que el verificador acepte [FGMSZ89].

En el caso de los sistemas de prueba probabilísticamente verificable (PCP), el mismo razonamiento muestra que requerir una solidez perfecta hace que la aleatoriedad sea inútil para elegir las ubicaciones a consultar. Más precisamente, se puede demostrar que PCP ( r ( n ), q ( n )) con integridad c ( n ) y solidez perfecta (incluso con consultas adaptativas) es igual a la clase C de problemas de decisión A = ( A , A no ) para el cual existe un lenguaje B ⊆ {0,1} * × {0,1} * × {0,1} * en P tal que

  • si xA , entonces Pr y ∈ {0,1} r ( n ) [∃ z ∈ {0,1} q ( n ) tal que ( x , y , z ) ∈ B ] ≥ c ( n ), y
  • si xA no , entonces ∀ y ∈ {0,1} r ( n )z ∈ {0,1} q ( n ) , ( x , y , z ) ∉ B ,

donde n = | x |. (Tenga en cuenta que en la definición de la clase C , el caso sí no requiere que se prepare un certificado completo antes de que el verificador elija la cadena aleatoria y , a diferencia de la definición habitual de un sistema PCP. Se puede preparar un certificado después de conocer y , y solo se necesita la parte consultada del certificado, por lo que la longitud de z es q ( n ).) Combinado con límites inferiores directos, esto implica lo siguiente:

  • PCP (log, log) con perfecta solidez = P.
  • PCP (poli, log) con perfecta solidez = RP .
  • PCP (poli, poli) con perfecta solidez = NP.

Comparando estos con los teoremas de PCP PCP (log, O (1)) = NP y PCP (poly, O (1)) = NEXP, podemos ver que requerir una perfecta solidez tiene un gran impacto.

[FGMSZ89] Martin Fürer, Oded Goldreich, Yishay Mansour, Michael Sipser y Stathis Zachos. Sobre integridad y solidez en sistemas de prueba interactivos. En Aleatoriedad y Computación , vol. 5 de Advances in Computing Research , págs. 429–442, 1989. http://www.wisdom.weizmann.ac.il/~oded/PS/fgmsz.ps

Tsuyoshi Ito
fuente