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

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

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

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

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

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

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

Для общих схем мы знаем, что в есть проблемы , для которых требуются схемы размером , это связано с Рави Каннаном (1981) и основано на его результате, что содержит такие проблемы. Ω ( n k ) P $\Sigma^p_2 \cap \Pi^p_2$$\Omega(n^k)$$PH$

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

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

Для уточнения ответа, для каждых к ≥ 1 и C , либо * Проблема поиска 3-СБ не имеет ~ О ( п K ) цепей или * Некоторые проблемы в O - P со временем (и размером свидетелей) ограничивается ~ O ( п K 2 ) не имеет io- O ( п K ( журнал п ) гр ) схем (Io средств бесконечно часто).$\mathrm{S}_2\mathrm{P}$$k≥1$$c$
$\tilde{O}(n^k)$
$\mathrm{O}_2\mathrm{P}$$\tilde{O}(n^{k^2})$$O(n^k (\log n)^c)$

$\mathrm{O}^2\mathrm{P}$$\tilde{O}(n^{k^2+k})$$i$хватает.$\tilde{O}(n^{\min(k^2+k,k^3)})$

Одной из проблем решения, не поддающейся вычислению для схем io- является наименьшее число N (запрашиваемое с использованием его двоичных цифр), которое не является таблицей истинности схемы с n k ⌊ ( log n ) c + 1 ⌋ ворота. Если NP находится в P / poly, у проблемы есть неопровержимый неопровержимый свидетель, состоящий из следующего: (1) N (2) схема, которая дала N ′ < N , показывает, что N ′ имеет достаточно малую схему.$O(n^k (\log n)^c)$$N$$n^k ⌊(\log n)^{c+1}⌋$
$N$
$N' < N$$N'$
(3) (используется только для , связанный) верификатор , что дает нам возможность запускать цепь противника на (2) только O ( 1 ) раз (получение 1 бит на ходу).$\tilde{O}(n^{k^3})$$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 + $k$$O(n^k)$$\mathrm{O}_2\mathrm{P}$$Σ_2^P$$n^{k+1}$ and $n^{k+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.