Самые известные совместные сдерживания для / от NP и Parity-P?

18

Parity-P - это набор языков, распознаваемых недетерминированной машиной Тьюринга, которая может различать только четное число или нечетное число путей «принятия» (а не нулевое или ненулевое число путей принятия). Таким образом, Parity-P - это, в основном, младший брат PP с задержкой роста: в то время как PP подсчитывает, является ли количество принимающих путей NP-машины мажоритарным или нет ( т. Е. Наиболее значимым битом этого количества), Parity-P указывает младший бит числа принимающих путей.

Как и NP, Parity-P содержит UP (который содержит P, вероятно, строго так); и как NP, Parity-P содержится в PSPACE.

Вопрос. Каковы наиболее известные совместные верхние и нижние границы для NP и Parity-P?

cc.complexity-theory complexity-classes np Ниль де Бодрап
источник

Ответы:

17

По Valiant-Vazirani, NP содержится в точке BP Parity-P (которая, очевидно, содержит Parity-P). Более того, Тода показал, что PH находится в точке BP Parity-P, которая находится в P ^ (# P) (которая находится в PSPACE).

Что касается нижних границ, я думаю, что оба класса содержат класс, известный как FewP, который содержит UP и похож на NP, но вы спрашиваете, что строки в языке имеют не более чем полиномиально много принимающих путей.

[Обновление: исправлена ​​опечатка BPP вместо BP]

Manu
источник
5
Следствием PH сдерживания в BPP-точке Parity-P является то, что Parity-P не содержится в Poly Hierarchy, если только эта иерархия не разрушится.
Энди Друкер
4
Это следует из того, что, если Parity-P находится в Sigma_k-P, то PH находится в точке BPP Sigma_k-P, которая содержится в Pi_ (k + 1) -P. (это последнее ограничение следует из простого «операторного» обобщения результата, согласно которому BPP находится в Sigma_2 P, пересекающем Pi_2 P.)
Энди Друкер
4
Я думаю, что считается вероятным, что точка BPP Точность-P содержится в P ^ (Паритет-P). Если это так, то PH содержится в P ^ (Parity), который содержится в (Parity-P) ^ (Parity-P), который фактически равен Parity-P. В чем я не уверен, так это в том, дают ли какие-либо документы о твердости и случайности гипотезу, которая подразумевает точку БЧП Parity-P, содержащуюся в P ^ (Parity-P).
Энди Друкер
4
Наконец, Parity-P отличается от NP и других классов PH тем, что, как известно, имеет место уменьшение от наихудшего к среднему. То есть, если Parity-P не находится в P, то он содержит проблемы распределения, которые сложны для среднего случая. См. Фейгенбаум-Фортнау, «Случайно-самосводимость полных множеств».
Энди Друкер
3
Вот общая идея: пусть C - класс сложности. Язык L находится в (точка BPP C), если существует язык S в C, состоящий из кодированных пар (x, r), таких что: -если x находится в L, то для 2/3 всех r пара (x, r) находится в S; -Если x не в L, то для 2/3 всех r пара (x, r) не находится в S. (Технически длина r зависит от x и должна быть не более некоторого полинома из | x |.)
Энди Друкер