¿Cuáles son las consecuencias de la paridad-L = P?

27

Parity-L es el conjunto de lenguajes reconocidos por una máquina de Turing no determinista que solo puede distinguir entre un número par o un número impar de rutas de "aceptación" (en lugar de un número cero o no cero de rutas de aceptación), y que es restringido aún más al trabajo en espacio logarítmico. Resolver un sistema lineal de ecuaciones sobre ℤ 2 es un problema completo para Parity-L, por lo que Parity-L está contenido en P.

¿Qué otras relaciones de clase de complejidad se conocerían si Parity-L y P fueran iguales?

Niel de Beaudrap
fuente

Respuestas:

28

paridad- está en N C 2 y paridad- L = P significaría que P puede simularse en el tiempo paralelo log 2 o en el espacio log 2 (ya que N C 2 está en D S P A C E ( l o g 2 n ) )LNC2L=PPlog2log2NC2DSPACE(log2n)

Noam
fuente
11
Corolario: si Parity-L = P, entonces P ≠ PSPACE.
Niel de Beaudrap
@Niel ¡Me encanta ese corolario! :)
Tayfun paga
14

Bueno, la evaluación de los circuitos cuánticos del grupo Clifford se completa con reducciones de espacio logarítmico para paridad-L (Ver Aaronson y Gottesman, Physical Review A 70: 052328, 2004). Ahora, usemos algunos trucos del cálculo cuántico basado en medidas:

La evaluación de los circuitos del grupo Clifford está en QNC ^ 1. Esto es simplemente porque no hay un pedido de tiempo parcial en las mediciones, y las operaciones de corrección simplemente se calculan por paridad de algún subconjunto de resultados de medición.

Esto parecería implicar que L ^ {QNC ^ 1} contiene P.

Joe Fitzsimons
fuente