Доказательство того, что верхние границы схемы для

18

В официальном описании проблемы Клея для P против NP он заявил , что будет следовать из показывая , что «каждый язык в [класс языков , распознаваемый в экспоненциальное время с детерминированной машиной Тьюринга] может быть вычислено с помощью булева семейства схем такое , что , по крайней мере , одной , имеет меньше ворота , чем максимум , необходимый для вычисления любой булевой функции $P \neq NP$ $E$ $<B_n>$ $n$ $B_n$ $f: \{0,1\}^n \longrightarrow \{0,1\}$ «Однако единственное упоминание состоит в том, что это« интригующее наблюдение В. Кабанца ». Может, кто-нибудь подскажет мне опубликованную версию этого подтекста с доказательством?

cc.complexity-theory circuit-complexity Дэвид
источник

25

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

Доказательство требуемого утверждения заключается в следующем:

содержит функцию максимально возможной сложности схемы на каждой входной длине, просто определяя функцию, которая оказывается (с использованием чередования) отличной от всех функций с не максимальной сложностью схемы. Это стандартная идея, и доказательство идеи можно найти в таких источниках, как Арора и учебник Барака. $\Sigma_3 E$
Если , то , посредством заполнения и распада полиномиальной иерархии времени к . $P = NP$ $\Sigma_3 E = E$ $P$
Следовательно, если то в существует язык с максимальной сложностью схемы. Это противоположно тому, что вы хотите доказать. $P = NP$ $E$

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

Хорошо, я догадался, что ты первый ответишь на него.

Мухаммед Аль-Туркистани

4

Есть также ответ в газете Кабанец и Цай. В теореме 10 они доказывают, что если

находится в

, то

содержит семейство булевых функций максимальной сложности схемы. Если

, то

и

, поэтому по теореме

действительно содержит язык с максимальной сложностью.

M C S P

$MCSP$

P

$P$

E^{N P}

$E^{NP}$

P = N P

$P=NP$

M C S P \in P

$MCSP\in P$

E^{N P} = E

$E^{NP}=E$

E

$E$

Андрас Фараго

1

Хороший вопрос, Андрас! Один из кванторов в

части можно рассматривать как решение MCSP.

Σ_{3} E

$\Sigma_3 E$

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

6

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

Проблема минимизации цепи

Валентин Кабанец и Джин-Йи Кай

Мы изучаем сложность задачи минимизации схемы: учитывая таблицу истинности булевой функции f и параметр s, решить, может ли f быть реализована с помощью булевой схемы размером не более s. Мы спорим, почему эта проблема вряд ли будет в P (или даже в P / poly), приводя ряд неожиданных последствий такого предположения. Мы также утверждаем, что доказательство того, что эта задача является NP-полной (если она действительно верна), подразумевало бы доказательство сильных нижних границ схемы для класса E, что выходит за рамки известных в настоящее время методов.

Это было опубликовано ниже.

расширенный реферат в трудах тридцать второго ежегодного симпозиума ACM по теории вычислений (STOC'00), стр. 73-79, 2000. технический отчет, в электронном коллоквиуме по вычислительной сложности TR99-045, 1999. http: // www. cs.sfu.ca/~kabanets/Research/circuit.html
расширенный реферат в трудах тридцать второго ежегодного симпозиума ACM по теории вычислений (STOC'00), стр. 73-79, 2000. http://eccc.hpi-web.de/report/1999/045/

Джошуа Герман
источник

Обратите внимание, что этот ответ не отвечает на поставленный выше вопрос, но он дает ссылку, из которой возник этот вопрос.

Джошуа Херман,

Доказательство того, что верхние границы схемы для

Ответы: