Каковы последствия Паритета-L = P?

27

Parity-L - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которые могут различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия), и который далее ограничено работой в логарифмическом пространстве. Решение линейной системы уравнений над ℤ 2 является полной проблемой для Паритета-L, поэтому Паритет-L содержится в P.

Какие еще классовые отношения сложности были бы известны, если бы Parity-L и P были равны?

Ниль де Бодрап
источник

Ответы:

28

четность находится в N C 2, а четность L = P будет означать, что P можно моделировать в параллельном журнале 2 времени или в журнале 2 пространства (поскольку N C 2 находится в D S P A C E ( l o g 2 n ) )LNC2L=PPlog2log2NC2DSPACE(log2n)

Ноам
источник
11
Следствие: если Parity-L = P, то P ≠ PSPACE.
Ниль де Бодрап,
@ Ниль, я люблю это следствие! :)
Tayfun Pay
14

Что ж, оценка квантовых цепей группы Клиффорда завершена при сокращении логарифмического пространства для четности-L (см. Aaronson and Gottesman, Physical Review A 70: 052328, 2004). Теперь давайте воспользуемся некоторыми приемами из квантовых вычислений на основе измерений:

Оценка групповых схем Клиффорда дана в QNC ^ 1. Это просто потому, что нет частичного упорядочения по времени измерений, а операции коррекции просто рассчитываются по четности некоторого подмножества результатов измерений.

Казалось бы, это означает, что L ^ {QNC ^ 1} содержит P.

Джо Фитцсимонс
источник