Parity-L - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которые могут различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия), и который далее ограничено работой в логарифмическом пространстве. Решение линейной системы уравнений над ℤ 2 является полной проблемой для Паритета-L, поэтому Паритет-L содержится в P.
Какие еще классовые отношения сложности были бы известны, если бы Parity-L и P были равны?
cc.complexity-theory
complexity-classes
conditional-results
Ниль де Бодрап
источник
источник
Что ж, оценка квантовых цепей группы Клиффорда завершена при сокращении логарифмического пространства для четности-L (см. Aaronson and Gottesman, Physical Review A 70: 052328, 2004). Теперь давайте воспользуемся некоторыми приемами из квантовых вычислений на основе измерений:
Оценка групповых схем Клиффорда дана в QNC ^ 1. Это просто потому, что нет частичного упорядочения по времени измерений, а операции коррекции просто рассчитываются по четности некоторого подмножества результатов измерений.
Казалось бы, это означает, что L ^ {QNC ^ 1} содержит P.
источник