¿Una prueba interactiva del número de Dios?

11

Últimamente he estado aprendiendo sobre pruebas interactivas y me he estado preguntando si todo esto no era más que una curiosidad teórica, o si tenía alguna aplicación práctica. Pensé comenzar con un ejemplo que se me ocurrió en la ducha:

Últimamente ha salido la noticia de que "Número de Dios" = 20. (El número de Dios es el número mínimo de pasos necesarios para resolver el Cubo de Rubik). Si bien esto es bastante interesante, parece haber un pequeño giro ... Esta no es una prueba "normal" en el libro de texto, sentido verificable del tiempo polinómico. Esta prueba tiene un sabor distintivo de "fuerza bruta": quiero decir, los tipos del laboratorio del Dr. Morley intentaron con miles de millones de combinaciones de cubos en las supercomputadoras masivas de Google para encontrar este límite inferior limpio y ajustado.

De todos modos, la pregunta es: ¿cómo podemos estar seguros de que el Dr. Morley Davidson y su equipo son honestos? Bueno, de inmediato puede arrojar el argumento de la autoridad por la ventana, ya que no es matemáticamente riguroso. La alternativa obvia es volver a verificar la prueba, verificando el código fuente y ejecutando todo de nuevo, lo que parece ser un terrible desperdicio de recursos computacionales, sin mencionar el hecho de que todos los que quisieran estar convencidos de esto necesita hacerlo en su propia estación de trabajo, una propuesta muy tediosa y desagradable para el verdadero escéptico. Entonces esto parece ser una especie de deilema ontológico.

Entonces, lo que creo es que esta es exactamente una situación en la que necesitamos una prueba interactiva . La Supercomputadora de Google podría ser el Prover todo poderoso pero engañoso, y nosotros los escépticos, si no miembros anales del público, somos los Verificadores acotados polinómicamente. Si de alguna manera pudiéramos consultar a nuestro "Oráculo" un número polinómico de veces, y convencernos de este límite inferior, podríamos convencernos del hecho de que tiene razón, más allá de toda duda razonable.

Por lo tanto, parece que el problema de decisión "Número de Dios es <20" mentiras en o pueden ser actualizados como sigue (de manera informal)Π2p

Para todas las combinaciones iniciales en el Cubo de Rubik, existe una solución que toma <= 20 pasos, β que lo resuelve.αβ

(no estoy seguro de si eso es correcto, pero y β son de tamaño pequeño, dada una configuración inicial y una solución, es fácil verificar que realmente resuelve el cubo)αβ

y el problema de Decisión "El número de Dios es 20" puede reexpresarse como

El número de Dios es <20 y existe una solución para una combinación inicial del cubo de Rubik que toma 20 pasos.

Entonces probablemente haya una prueba de IP [n] para esto. (una vez más, revisa mi funcionamiento)

Mi pregunta es doble

  1. ¿Hay alguna forma real de hacer esto?
  2. ¿Qué otros ejemplos de usos "prácticos" de pruebas interactivas existen?
gabgoh
fuente
Creo que te refieres a "número de Dios" es el número máximo de movimientos necesarios para resolver el Cubo de Rubix. De manera similar, usted menciona varias veces "este límite inferior ordenado y ajustado" mientras que quiere decir "límite superior".
Ross Snider
1
De todos modos, una respuesta parcial a su pregunta. Hay una pregunta posiblemente relacionada cstheory.stackexchange.com/questions/2461/… . Según tengo entendido, la respuesta a su primera pregunta es sí, solo siga el protocolo. Sin embargo, también tengo entendido que participar en una configuración de prueba interactiva no se ha "entendido". ¿Alguien sabe si las constantes involucradas son muy altas?
Ross Snider
Π2PSPACE

Respuestas:

10

Π2p

PHP#PLPH

Usando sus técnicas, Shamir demostró que IP = PSPACE .

Anteriormente se demostró que todas las IP tienen pruebas de conocimiento cero , por lo que:

Todos los idiomas en PSPACE tienen pruebas interactivas de conocimiento cero.

MS Dousti
fuente
Π2#P
@Peter: Si por "práctico" te refieres al probador que es BPP, entonces tienes razón. De hecho, solo los idiomas NP tienen tales pruebas.
MS Dousti
Me refería a algo "práctico" en el que el probador tiene aproximadamente el mismo poder computacional que la prueba de que el número de Dios = 20.
Peter Shor
1
α
2
@sadeq: Tal vez algunos problemas en MA y AM podrían, pero no estoy al tanto de nada fuera de estas clases que tenga pruebas interactivas "prácticas".
Peter Shor
1

20Gs=U,U,U2,D,D,D2,mϵπ

n<mnmπAG AM

|s|=18m

  • nmϵgG18n|G|gsn

  • n<mk=|A|gGg18n2|G|n

ϵ1109|G|k110|G|

n

  1. gGhG18n|G|yh
  2. Wng
  3. Wh(W)=yng
  4. Arthur y Merlin repiten para amplificar según sea necesario

Porque, para los grupos, creo, el tiempo de mezcla es al menos el diámetro (número de Dios), esto también proporciona una prueba de Arthur-Merlin para vincular el número de Dios de un grupo grande.

Marcas
fuente