Was sind die Konsequenzen von Parität-L = P?

Parität-L ist die Menge von Sprachen, die von einer nicht-deterministischen Turing-Maschine erkannt werden und die nur zwischen einer geraden oder ungeraden Anzahl von "Akzeptanz" -Pfaden (anstelle einer Null- oder einer Nicht-Null-Anzahl von Akzeptanzpfaden) unterscheiden kann weiter auf die Arbeit im logarithmischen Raum beschränkt. Die Lösung eines linearen Gleichungssystems über over ₂ ist für Parity-L ein komplettes Problem, weshalb Parity-L in P enthalten ist.

Welche anderen Komplexitätsklassenbeziehungen wären bekannt, wenn Parität-L und P gleich wären?

Parität- ist in N C 2 und Parität- L = P würde bedeuten, dass P in paralleler log 2- Zeit oder in log 2- Raum simuliert werden kann (da N C 2 in D S P A C E ist ( l o g 2 n ) )$L$$NC^2$$L=P$$P$$\log^2$$\log^2$$NC^2$$DSPACE(log^2 n)$

Nun, die Auswertung der Quantenschaltungen der Clifford-Gruppe ist unter logarithmischen Raumreduzierungen für Parität-L abgeschlossen (siehe Aaronson und Gottesman, Physical Review A 70: 052328, 2004). Wenden wir nun einige Tricks aus der messungsbasierten Quantenberechnung an:

Die Auswertung von Clifford-Gruppenschaltungen erfolgt in QNC ^ 1. Dies liegt einfach daran, dass es keine zeitliche Teilreihenfolge für Messungen gibt und Korrekturoperationen einfach durch Parität einiger Teilmengen von Messergebnissen berechnet werden.

Dies scheint zu implizieren, dass L ^ {QNC ^ 1} P enthält.