Какой «самый маленький» класс сложности, для которого

Я считаю , что ответы на этот вопрос зависит классы дают такое , что для всех полиномов , существует проблема в классе , который не имеет схемы размера . Однако я спрашиваю о размере схемы . $p$
$p(n)$
$\omega \hspace{.02 in}(n)$

$\big(\hspace{-0.07 in}\left\langle \hspace{-0.04 in}0^{\hspace{.02 in}0}\hspace{-0.03 in},\hspace{-0.04 in}1^{\hspace{-0.03 in}1}\hspace{-0.03 in},2^{\hspace{.02 in}2}\hspace{-0.04 in},\hspace{-0.03 in}3^1\hspace{-0.04 in},\hspace{-0.03 in}4^4\hspace{-0.03 in},\hspace{-0.03 in}5^1\hspace{-0.04 in},\hspace{-0.03 in}6^{\hspace{.03 in}6}\hspace{-0.03 in},\hspace{-0.03 in}7^1\hspace{-0.03 in},\hspace{-0.03 in}8^8\hspace{-0.03 in},\hspace{-0.03 in}9^1\hspace{-0.03 in},...\hspace{-0.05 in}\right\rangle \:$ суперлинейен, но не . Хотя такое четно-нечетное поведение может быть обработано заполнением, вместо этого могут быть очень длинные полосы суперполиномиальных значений между низкими значениями.) $\omega \hspace{.02 in}(n)$

circuit-complexity lower-bounds Сообщество
источник

Я думаю, что суперлинейные нижние границы означают, что есть нижняя граница в .

ω (n)

$\omega(n)$

Каве

Я не думаю, что мы называем это суперлинейной функцией. Насколько я знаю, люди понимают под суперлинейным же, как сублинейным является . Есть ли у вас какие-либо ссылки на использование суперлинейного в вашем смысле? Ваша последовательность бесконечно часто суперлинейна, но она не суперлинейна.

ω (n)

$\omega(n)$

o (n)

$o(n)$

Каве

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

O (n)

$O(n)$

Джошуа Грохов

См. Сообщение в блоге Fortnow о том, как правильно определить обозначение большого омега.

Робин Котари

@Kaveh: Извините, я должен был быть более конкретным. Я имел в виду утверждение, что «проблема X не имеет цепей линейного размера», как правило, эквивалентно высказыванию, что «проблема X имеет нижнюю границу размера суперлинейных цепей », и я считаю, что оба эти значения означают (и должны означать) то, что я сказал в моих предыдущих комментариях. Фраза «проблема X имеет цепи сверхлинейного размера» кажется мне странной, потому что «наличие таких-и-таких схем» является верхней границей, а «суперлинейная» - нижней границей ...

Джошуа Грохов

Ответы:

$S^p_2$ Известно, что и не имеют -цепей для каких-либо фиксированных k, и между ними нет никакой известной локализации. Подробности в моем блоге . $PP$ $n^k$

Обновление: как указывает Рики Демер, эти результаты не обязательно дают язык с нижней границей для всех в . Я думаю, что , вероятно, самый известный. Так как у есть полные наборы, вы можете получить все но у меня нет полного доказательства. $n$ $S_2^p$ $\Delta^p_3$ $PP$ $n$

Лэнс Фортноу
источник

Как вы идете от "не имеет

^{k}

$^k$ схемы "к

ω (n)

$\omega(n)$ Нижний предел размера схемы?

$\hspace{.84 in}$ Смотрите верхнюю часть этой страницы для последовательности, которая не имеет верхней границы полинома, но не

ω (n)

$\omega(n)$ .)

$\hspace{.58 in}$

@ EmilJeřábek: Как вы получаете это для всех достаточно большой

n

$n$ а не только для бесконечно многих

n

$n$ ?

$\hspace{.08 in}$ (Что нужно было бы получить "размер цепи

ω (n)

$\omega(n)$ "а не" размер цепи не

O (n)

$O(n)$ .)

$\hspace{1.12 in}$

@ EmilJeřábek: Смотрите мой ответ на meta.stackexchange.com/a/293100/232555 .

Вы правы, я сконцентрировался на первой части доказательства, которая отсутствует в блоге, и не осознавал, что существует огромная проблема с разграничением случаев. Так или иначе, есть язык в

Δ_{3}^{P}

$\Delta^P_3$ которые нуждаются в схемах размера

\geq n^{k}

$\ge n^k$ для всех достаточно больших

n

$n$ ,

Эмиль Йержабек

Может получить почти всюду нижнюю оценку для

P^{P P [n^{2}]}

$P^{PP[n^2]}$ , Для каждого

n

$n$ , позволять

S

$S$ быть множеством всех цепей размера

n \log n

$n\log n$ , За

i = 1, \dots, n^{2}

$i=1,\ldots,n^2$ вызовите оракула один раз, чтобы определить, что большинство цепей в

S

$S$ ответ на

i

$i$ ввод длины

n

$n$ и выбросить из

S

$S$ все схемы, которые дают этот ответ (это может быть закодировано как ограничение по времени при следующем вызове оракула). Наша сложная функция выведет противоположное значение на

i

$i$ ввод длины

n

$n$ .. Конец для. Теперь, учитывая AE-LB для

P^{P P [n^{2}]}

$P^{PP[n^2]}$ мы можем поднять его

P P

$PP$ ?

Райан Уильямс

Пусть dMCSP будет версией Решения о минимальном размере схемы,
и пусть «[1]» означает « только 1 запрос ».
Ответ на мой вопрос, кажется, $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ Который фактически
таков, что для каждого положительного целого числа k он имеет $\omega \hspace{-0.02 in}\big(\hspace{-0.03 in}n^k\hspace{-0.03 in}\big)$ Нижняя граница:

Следуйте последнему абзацу на странице 7 из этого документа , с этим абзацем $k$ быть на один больше, чем этот аргумент $k$ и, кроме того, "обратите внимание, что это задача" co_dMCSP ", чтобы решить,
является ли данная таблица истинности длины $\ell$ трудно», в том же смысле , как он используется в этом пункте страница-7.

В DNF схемы для произвольно длина- $\ell$ Таблица истинности имеет максимальный размер $\ell^{\hspace{.03 in}2} \cdot \operatorname{polylog}(\ell)$ ,
Так dMCSP в $\mathbf{NP}$ , Поэтому $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}}\hspace{-0.03 in}\right)} \subseteq \mathbf{P}^{\left(\mathbf{NP}^{\hspace{.03 in}\mathbf{NP}}\hspace{-0.03 in}\right)} = \Delta^p_3$ ,

Я не знаю ни одного доказательства того, что любой из этих $\subseteq$ s являются равенствами, и этот документ создает значительные препятствия для возможности dMCSP быть $\mathbf{NP}$ -трудно при рандомизированных сокращениях Тьюринга.
Равенства вытекают из того, что dMCSP $\mathbf{NP}$ -трудной под сильным недетерминистическую ( страница 6 ) сокращение один-запросов , которые принимают советы строку полиномиального размера , который является вычислимой
по $\mathbf{P}^{\left(\mathbf{NP}^{\hspace{.032 in}\operatorname{dMCSP}[1]}\hspace{-0.03 in}\right)}$ Но, в частности, я не знаю ни одного доказательства такой твердости.

источник