Какой класс наименьшей сложности известен для границы суперлинейного контура?

25

Извиняюсь за вопрос, который обязательно должен быть во многих стандартных ссылках. Мне любопытно точно вопрос в названии, в частности, я имею в виду булевы схемы, без ограничений по глубине. Я поместил «наименьшее» в кавычки, чтобы учесть, что существует множество разных классов, которые, как известно, не включают друг друга, для которых известна суперлинейная граница.

Мэтт Гастингс
источник

Ответы:

25

Я считаю, что наименьшими из известных классов являются (Cai, 2001), (Vinodchandran, 2005) и (Santhanam, 2007). Известно, что все они не находятся в для каждой константы .P P ( M A c o M A ) / 1 S I Z E ( n k ) kS2PPP(MAcoMA)/1SIZE(nk)k

Райан О'Доннелл
источник
1
Спасибо всем за ответы. Я принимаю Райана, потому что у него самые разные результаты, но спасибо Робину и Каве за подробные объяснения.
Мэтт Гастингс
20

Самый сильный результат, который я знаю, заключается в том, что для всех k существует проблема в которая требует схемы размера . Ω ( n k )S2PΩ(nk)

S2P класс , содержащийся в , который сам содержится в \ Sigma_2 ^ P \ Колпачок \ Pi_2 ^ P . ( Зоопарк сложности имеет больше информации об этом классе.) Σ P 2Π P 2ZPPNPΣ2PΠ2P

Результат вытекает из наиболее сильной версии теоремы Карпа-Липтона из-за Цая .

Быстрое доказательство того, как это следует из теоремы KL: во-первых, если SAT требует схем с суперполиномиальными размерами, мы закончили, так как мы продемонстрировали проблему в которая нуждается в схемах с суперполиномиальными размерами. Если СБ имеет схемы полиномиального размера, то самой сильной версии теоремы Карп-Lipton, PH коллапсирует . Мы знаем, что PH содержит проблемы, такие проблемы (по результату Каннана), и, таким образом, содержит такую ​​проблему. S P 2 S P 2S2PS2PS2P

Робин Котари
источник
3
Хороший и превосходный ответ, как всегда. :)
Kaveh
13

Для общих схем мы знаем, что в есть проблемы , для которых требуются схемы размером , это связано с Рави Каннаном (1981) и основано на его результате, что содержит такие проблемы. Ω ( n k ) P HΣ2pΠ2pΩ(nk)PH

Я думаю, что лучшие нижние границы для по-прежнему около .5 нNP5n

См. Книгу Ароры и Барака, стр. 297. У Ричарда Липтона была запись в своем блоге об этих результатах, см. Также эту .

Кава
источник
1

Для уточнения ответа, для каждых к 1 и C , либо * Проблема поиска 3-СБ не имеет ~ О ( п K ) цепей или * Некоторые проблемы в O - P со временем (и размером свидетелей) ограничивается ~ O ( п K 2 ) не имеет io- O ( п K ( журнал п ) гр ) схем (Io средств бесконечно часто).S2Pk1c
O~(nk)
O2PO~(nk2)O(nk(logn)c)

O2PO~(nk2+k)iхватает.O~(nmin(k2+k,k3))

Одной из проблем решения, не поддающейся вычислению для схем io- является наименьшее число N (запрашиваемое с использованием его двоичных цифр), которое не является таблицей истинности схемы с n k( log n ) c + 1 ворота. Если NP находится в P / poly, у проблемы есть неопровержимый неопровержимый свидетель, состоящий из следующего: (1) N (2) схема, которая дала N < N , показывает, что N имеет достаточно малую схему.O(nk(logn)c)Nnk(logn)c+1
N
N<NN
(3) (используется только для , связанный) верификатор , что дает нам возможность запускать цепь противника на (2) только O ( 1 ) раз (получение 1 бит на ходу).O~(nk3)O(1)

Отдельно отметим, что для каждого в (MA ∩ coMA) / 1 существуют проблемы решения, в которых нет O ( n k ) цепей. «/ 1» означает, что машина получает один совет, который зависит только от размера ввода. Кроме того, строка, которую отправляет Мерлин, может быть выбрана, чтобы зависеть только от размера ввода (с этим ограничением MA является подмножеством O 2 P ) и сложности рекомендации Σ P 2 . Доказательство (Santhanam 2007) обобщает IP = PSPACE и PSPACE⊂P / poly ⇒ PSPACE = MA, используя определенную корректную PSPACE-задачу и дополняет входы, чтобы получить минимальные размеры схем, которые бесконечно часто находятся между n k + 1.kO(nk)O2PΣ2Pnk+1 and nk+2, using advice to detect enough examples of such n, and for these n, solving the padded problem by having Merlin produce such a circuit.

Dmytro Taranovsky
источник