es

8

Creo que estas dos clases deberían ser las mismas, pero no puedo encontrar ninguna literatura sobre esto y tengo antecedentes limitados sobre el tema.

Este es mi razonamiento, y me gustaría saber si (1) esto ya se conoce o (2) no entendí algo o (3) acabo de descubrir algo útil:

PCTC es la clase de problemas que se pueden resolver colocando cantidades polinómicas de datos en una máquina del tiempo.

BPPpath es la clase de problemas que pueden resolverse mediante la selección posterior en una máquina de Turing probabilística, es decir, ignorar los casos que no le interesan.

PCTC⊆BPPpathporque puede simular una curva cerrada similar al tiempo con una selección posterior como esta: Escanee todo el programa al principio, tanto el estado como la memoria. Luego, después del procesamiento, vuelva a hacerlo y seleccione después para que solo regrese si el estado y la memoria ahora son exactamente iguales al estado y la memoria de inicio (excepto por un solo bit que dice si esta es la primera iteración o no, para evitar un Bucle infinito).

BPPpath⊆PCTC porque puede simular una selección posterior como esta: si el mensaje del futuro comienza con 1, envía el mensaje 0en el pasado. De lo contrario, proceda normalmente. Cuando llegue al paso en el que normalmente seleccionaría posteriormente, envíe un 1 al pasado iff. desea ignorar esta línea de tiempo, de lo contrario un0. La única versión consistente ahora es aquella en la que ambos reciben y envían un 0 porque estaban satisfechos con los resultados.

complexity-theory complexity-classes quantum-computing Florian Dietz
fuente
2
No tengo absolutamente ninguna idea sobre este tema, pero en este enlace de papel dicen que la clase P_CTC es igual a PSPACE y BPP_PATH es igual a POST_BPP que está contenido en P con un oráculo NP. Entonces, las dos clases probablemente no sean lo mismo
rotia
¡Es bueno saberlo! Sin embargo, no diría que esto muestra que las dos clases no son iguales: solo significa que si son iguales, entonces PSPACE = P ^ NP. Hace que sea menos probable que sea cierto porque alguien más podría haber descubierto esta conexión antes si fuera cierto, pero también significa que si el enfoque SI es correcto, tendrá consecuencias útiles.
Florian Dietz el
El bosquejo de su prueba de que "P_CTC está en BPP_PATH" es el culpable en mi opinión. Un problema es que no es obvio cómo su máquina postBPP retiene adecuadamente estados consistentes del número polinómico de registros CTC. P_CTC no es simplemente tiempo polinómico con viaje en el tiempo. Hay criterios de consistencia causal muy específicos que deben aplicarse. Estas restricciones son las que le dan a la máquina la capacidad de encontrar puntos fijos parciales fácilmente, lo que podría decirse que es más general que la mera selección posterior. Le animo a que revise cuidadosamente la definición formal de P_CTC.
mdxn

Respuestas:

0

Creo que he encontrado la respuesta: la prueba es incorrecta. BPP_PATH no está en P_CTC porque se requiere P_CTC para dar una respuesta definitiva única, mientras que BPP_PATH es un algoritmo probabilístico, por lo que la segunda reducción no funciona. Para que funcione, uno tendría que usar la información del viaje en el tiempo para contar el número de éxitos del algoritmo probabilístico frente al número de sus fallas. No tengo idea de cómo hacer esto, o si incluso se puede hacer (probablemente no).

Florian Dietz
fuente
... y cinco minutos después ya no estoy seguro. P_CTC = PSPACE, y ¿PSPACE no puede simular BPP?
Florian Dietz
2
Te estás confundiendo a ti mismo. Las máquinas deterministas son básicamente probabilísticas con tolerancia cero al error y sin acceso a la aleatoriedad. Si una máquina candidata puede responder las mismas preguntas sin el error, entonces no hay problema. No hay necesidad de equivocarse con la misma frecuencia. Independientemente, PSPACE le permite simular una máquina BPP fácilmente al poder probar cada cadena aleatoria y calcular manualmente la probabilidad de aceptación. Dado que P_CTC = PSPACE, razona que hay una máquina P_CTC equivalente que puede responder de la misma manera dada cualquier máquina BPP en particular.
mdxn