Apa konsekuensi dari Parity-L = P?

Parity-L adalah seperangkat bahasa yang dikenali oleh mesin Turing non-deterministik yang hanya dapat membedakan antara bilangan genap atau ganjil dari jalur "penerimaan" (daripada jumlah jalur penerimaan yang nol atau tidak nol), dan yang merupakan selanjutnya dibatasi untuk bekerja di ruang logaritmik. Memecahkan sistem persamaan linear lebih dari ℤ ₂ adalah masalah yang lengkap untuk Parity-L, sehingga Parity-L terkandung dalam P.

Apa hubungan kelas kompleksitas lain yang akan diketahui, jika Parity-L dan P sama?

parity- di N C 2 dan parity- L = P akan berarti bahwa P dapat disimulasikan secara paralel log 2 waktu atau di log 2 ruang (karena N C 2 adalah di 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)$

Nah, mengevaluasi sirkuit kuantum grup Clifford selesai di bawah pengurangan ruang log untuk paritas-L (Lihat Aaronson dan Gottesman, Physical Review A 70: 052328, 2004). Sekarang, mari kita gunakan beberapa trik dari perhitungan kuantum berbasis pengukuran:

Mengevaluasi sirkuit grup clifford ada di QNC ^ 1. Ini semata-mata karena tidak ada urutan waktu parsial pada pengukuran, dan operasi koreksi hanya dihitung berdasarkan paritas dari beberapa subset dari hasil pengukuran.

Ini sepertinya menyiratkan bahwa L ^ {QNC ^ 1} mengandung P.