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?
fuente
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.
fuente