Jakie są konsekwencje parzystości-L = P?

Parzystość-L jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może jedynie rozróżniać między liczbą parzystą lub nieparzystą liczbą ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji), i która jest dodatkowo ograniczone do pracy w przestrzeni logarytmicznej. Rozwiązanie liniowego układu równań powyżej ℤ ₂ jest kompletnym problemem dla parzystości-L, więc parzystość-L zawarta jest w P.

Jakie inne relacje klas złożoności byłyby znane, gdyby parzystość-L i P były równe?

parzystość - jest w N C 2, a parzystość - L = P oznaczałoby, że P może być symulowane w równoległym czasie log 2 lub w przestrzeni log 2 (ponieważ N C 2 jest w D S P A C E ( l o g 2 n ) )$L$$NC^2$$L=P$$P$$\log^2$$\log^2$$NC^2$$DSPACE(log^2 n)$

Cóż, ocena obwodów kwantowych grupy Clifford jest zakończona przy zmniejszeniu przestrzeni logarytmicznej dla parzystości-L (patrz Aaronson i Gottesman, Physical Review A 70: 052328, 2004). Teraz zastosujmy kilka sztuczek z obliczeń kwantowych opartych na pomiarach:

Ocena obwodów grupy Clifford jest w QNC ^ 1. Jest tak po prostu dlatego, że nie ma częściowego uporządkowania czasu pomiarów, a operacje korekcyjne są po prostu obliczane na podstawie parzystości pewnego podzbioru wyników pomiarów.

Wydaje się to sugerować, że L ^ {QNC ^ 1} zawiera P.