Содержится ли

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

Предположим, что функция из однородного класса (например, ) также входит в небольшой неоднородный класс (например, , т. Е. Неоднородный ), означает ли это, что функция содержится в меньший однородный класс (как )? Если ответ на этот вопрос положительный, каков наименьший однородный класс сложности, содержащий ? Если отрицательный, можем ли мы найти интересный естественный контрпример? $NP$ $AC^0/poly$ $AC^0$ $P$ $NP \cap AC^0/poly$

Содержится ли в ? $AC^0/poly \cap NP$ $P$

Примечание: друг уже частично ответил на мой вопрос в автономном режиме, я добавлю его ответ, если он сам не добавит его.

Вопрос - моя вторая попытка формализовать следующий неформальный вопрос:

Может ли неравномерность помочь нам в вычислении естественных однородных задач?

Связанный:

Есть ли кандидат на естественную проблему в ? $P/poly−P$

cc.complexity-theory circuit-complexity uniformity Кава
источник

@Kaveh: Может быть, интересным вопросом было бы задать естественную проблему в P / poly и NP, но не в P. (Или, может быть, это слишком просто?)

Робин Котари

@Robin: что кажется интересным, но я не уверен , что это было бы легче найти естественную проблему в

N P \cap P / p o l y - P

$NP \cap P/poly - P$

Каве

@all: Мне нужно немного больше подумать об этом вопросе и ответах. Это кажется очень естественным вопросом. Но я чувствую себя неловко об ответах: во- первых, мы можем ослабить предположение, заменив

, где

является очень быстро растет функция; во-вторых, контрпример не только в

N E X P \neq E X P

$NEXP \neq EXP$

N T i m e (f) \neq D T i m e (f)

$NTime(f) \neq DTime(f)$

f

$f$

A C^{0} / p o l y

$AC^0/poly$ но имеет цепи размера 1, так как функция постоянна на всех входах размера

для всех

! Эти две причины могут говорить о том, что это неправильный вопрос.

n

$n$

n

$n$

Каве

@Kaveh: Возможно, вы захотите взглянуть на класс YP, определенный Скоттом Ааронсоном. Это как P / Poly, но «совет» не доверяют. Другими словами, это похоже на то, как NP пересекает coNP, но свидетель может зависеть только от длины ввода. YP находится в P / poly, и является унифицированным классом. Возможно, проблема в YP, но не в P, является примером проблемы, которую вы ищете. Это было бы естественно, равномерно, не в P, в P / poly, и, возможно, нетривиально, так как совет должен быть проверен схемой.

Робин Котари

@Kaveh: класс YP («Полиномиальное время Йоды») более формально определен в статье Скотта «Изучаемость квантовых состояний» [quant-ph / 0608142]

Алессандро Косентино,

Ответы:

Вот упрощение ответа Райана. Пусть . Определите язык . Предположение переводит к . Кроме того, тривиально . $\Lambda \in NE \setminus E$ $L = \{x : |x| \in \Lambda\}$ $\Lambda \in NE \setminus E$ $L \in NP \setminus P$ $L \in AC^0/poly$

Юваль Фильмус
источник

Хороший ответ Ювал!

Dai Le

По существу, то же самое преобразование используется в книге 1974 года, чтобы показать, что E ≠ NE тогда и только тогда, когда NP ∖ P содержит язык подсчета.

Цуёси Ито

Просто чтобы быть уверенным: правильно ли я понимаю, что

длина

написана в одинарном?

| x |

$|x|$

x

$x$

Винсент

@ Vincent Здесь

- это строка, а не целое число, а

это его длина.

x

$x$

| x |

$|x|$

Ювал Фильмус

да, это то, что смущает меня. Если

длина некоторой строки, то

целое число, так как это может быть элементом

| x |

$|x|$

| x |

$|x|$

Λ

$\Lambda$

Винсент

Ответ на первый вопрос: кажется маловероятным.

Теорема: Если , то . $NP \cap AC^0/poly \subseteq P$ $NEXP = EXP$

Учитывая схему которая выводит бит, определите декомпрессию C как строку битов, полученную путем оценки на всех возможных входах. То есть декомпрессия представляет собой . $C$ $C$ $C(0^n) C(0^{n-1}1) C(0^{n-2}10) \cdots C(1^n)$

Определите задачу Сукцинкт 3SAT следующим образом: для схемы размера кодирует ли ее декомпрессия выполнимую булеву формулу? $C$ $n$ Известно, что сжатый 3SAT является полным комплектом $NEXP$

Теперь рассмотрим язык

{целое число записанное в двоичном виде, является экземпляром yes краткой 3SAT}. $L =$ $1^n |$ $n$

явно в , таквы можете просто жестко ли в , для каждого . $L$ $AC^0/poly$ $1^n$ $L$ $n$

$L$ $NP$ $n$ $\log n$ $O(n)$ $O(n)$

$L \in P$ $NEXP=EXP$ $O(n^c)$ $\log n$

Ваш второй вопрос широко открыт (и открыт).

Райан Уильямс
источник

Почему вы должны принять некоторые полные проблемы?

Юваль Фильмус

Думал, что это сделало аргумент легче следовать.

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

Спасибо Райан за ваш хороший ответ и объяснение. Думаю, вы не возражаете, если я приму ответ Ювала, хотя вы были первым, кто отправил сообщение.

Каве

На вопрос Каве "Может ли неравномерность помочь нам в вычислении естественных однородных задач?"

$n$ $1$ $n$ $n^5$ $n$

Ссылки:

Фридхельм Мейер, Хайде, " Алгоритм полиномиального линейного поиска для n-мерной задачи о ранце ", 1984 г.

Стасис
источник

n

$n$

2

$2$

2^{n}

$2^n$

1

$1$

N P \subseteq P / p o l y

$NP\subseteq P/poly$

@Kaveh: Но NP сам по себе является большим ИЛИ P. «Временная версия» P против NP такова: можем ли мы заменить это большое ИЛИ детерминированным алгебраическим деревом решений полиномиальной глубины (с P на листьях)? Напомним, что тривиальная глубина для Subset-Sum равна 2 ^ n (не n). Dopkin и Lipton (1978) показали, что глубина n ^ 2/2 необходима, и широко распространено мнение, что это можно улучшить до n ^ k для любого k. Mayer auf der Heide опроверг это мнение: достаточно k = 5. Таким образом, неравномерность МОЖЕТ помочь, если нас интересует глубина (время).

Стасис