Tardos Функция контрпример Блюма Претензия

В этой теме попытка Нобетта Блюма в доказательстве лаконично опровергается, когда отмечается, что функция Тардоса является контрпримером к теореме 6 $P \neq NP$

Теорема 6 : Пусть - любая монотонная булева функция. Предположим, что существует CNF-DNF-аппроксиматор который можно использовать для доказательства нижней оценки . Тогда также можно использовать для доказательства той же нижней оценки для . $f \in \mathcal{B}_n$ $\mathcal{A}$ $C_m(f)$ $\mathcal{A}$ $C_{st}(f)$

Вот моя проблема: функция Тардоса не является булевой, так как же она удовлетворяет условиям теоремы 6?

В этой статье они обсуждают сложность функции , которая в общем случае не является монотонной булевой функцией, поскольку увеличение ребер может сделать больше, чтобы сделать false, когда это было верно с меньшим во входных данных. Функция , как правило, не вычисляет в и в . $\varphi(X) \leq f(v)$ $\varphi(X)$ $\varphi(X) \leq f(v)$ $1$ $\varphi(X) \geq f(v)$ $1$ $T_1$ $0$ $T_0$

Фактически, тестовые наборы и выбраны точно так, чтобы вычисление в и в с монотонностью означало вашу функцию в точном вычислении CLIQUE (они определяют границу и в решетке входов ), поэтому эти замечания подразумевают, что функция Tardos такая же, как CLIQUE, что явно не соответствует действительности. $T_1$ $T_0$ $1$ $T_1$ $0$ $T_0$ $1$ $0$

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

cc.complexity-theory np-hardness complexity-classes user144527
источник

Хорошим источником была бы книга Юкны, с.272 (как раз перед теоремой 9.28). Учитывая (не булеву) функцию , рассмотрим булеву функцию которая является пороговым значением : Результат применяется.

ϕ

$\phi$

f_{ϕ}

$f_\phi$

ϕ

$\phi$

f_{ϕ} (G) = {\begin{cases} 1 & if ϕ (G) \geq \sqrt{n} \\ 0 & otherwise \end{cases}

$f_\phi(G) = \begin{cases} 1 & \text{if } \phi(G) \geq \sqrt{n}\\ 0&\text {otherwise}\end{cases}$

Клемент С.

Итак, чтобы быть ясным, вы говорите мне, что будет оценивать до в кликах размера и в графах вершин, индуцированных собственно красители?

f_{ϕ} (G)

$f_\phi(G)$

1

$1$

\sqrt{n}

$\sqrt{n}$

0

$0$

n

$n$

⌊ \sqrt{n} - 1 ⌋

$\lfloor \sqrt{n}-1 \rfloor$

user144527

Конечно, это не относится ни к одной . Но функция Тардоса основана на монотонной граф-функции удовлетворяющей . Итак, пороговое значение of делает именно то, что вы говорите. Смотрите конец Раздела 9.8 здесь .

ϕ

$\phi$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

ω (G) \leq ϕ (G) \leq χ (G)

$\omega(G)\leq \phi(G)\leq \chi(G)$

f_{ϕ}

$f_{\phi}$

ϕ

$\phi$

Стасис

Правильно. Кстати, я на самом деле не понимаю, почему люди голосуют против вашего (приемлемого ввиду всего этого шума вокруг этого «доказательства») вопроса? Теперь автор этой очереди заявления P! = NP: объясните, почему «доказательство» НЕ будет работать для функции Тардоса. Укажите страницу X и строку (и) Y в документе. Подсказка: ошибка заключается в ограничении количества ошибок, внесенных во время аппроксимации (отрицания могут уничтожить множество ранее «действительных» терминов). В противном случае (без объяснения) = нет «доказательства».

Стасис

@Stasys, ваш первый комментарий может быть ответом.

Каве

Ответы:

таким образом, из этих замечаний следует, что функция Тардоса такая же, как CLIQUE. $f$

Краткий ответ - НЕТ.

Это только монотонный «клик-подобный»: принимает все клики и отклоняет все полные -раздельные графы. Однако он может принять некоторые графы, отклоненные CLIQUE: графы с но (так называемые "неидеальные" графы). В работе Грёшеля, Ловаша и Шрайвера подразумевается, что имеет немонотонную цепь полиномиального размера. Но, согласно теореме 6 в «доказательстве» , любая монотонная клико-подобная булева функция требует немонотонных цепей суперполиномиального размера. Итак, одна из этих двух статей должна $k$ $(k-1)$ $G$ $\omega(G) < k$ $\chi(G)\geq k$ $f$ быть неправым. Бумага GLS-1981 просуществовала уже> 35 лет ...

То, что делает Тардос, заключается в следующем. Она начинает с функции графа , где - знаменитая тэта-функция Ловаша. Фундаментальный факт заключается в том, что число находится между номером клика и хроматическим числом: . Затем она использует тот факт, что может быть аппроксимирована за полиномиальное время. На основании этого она определяет граф-функцию со следующими свойствами: $\varphi(G):=\vartheta(\overline{G})$ $\vartheta$ $\varphi(G)$ $\omega(G)\leq \varphi(G)\leq \chi(G)$ $\vartheta(G)$ $\phi(G)$

Значения могут быть вычислены за полиномиальное время (в количестве вершин). $\phi(G)$ $n$
$\phi$ является монотонным: добавление ребер может только увеличить его значение.
$\omega(G)\leq \phi(G)\leq \chi(G)$ имеет место для всех графов . $G$

Затем (как отмечает Клемент С.) она определяет желаемую монотонную булеву функцию как: тогда и только тогда, когда . Согласно (1), функция имеет (немонотонную) схему полиномиального размера. Согласно (2), является монотонной булевой функцией. Согласно (3), принимает все -клики и отклоняет все полные -раздельные графы. $f$ $f(G)=1$ $\phi(G)\geq k$ $f$ $f$ $k$ $(k-1)$

Смотрите здесь для технических деталей.

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

Документ GLS-1981 здесь бесплатно. Эта статья, в свою очередь, основана на элипсоидной бумаге Хачияна-1979. Итак, (по крайней мере) один из этих трех документов должен быть неправильным?

Тобиас Мюллер,

@Tobias: мы уверены, что эти две> 35 старых статей верны (столько раз, что они воспроизводились на лекциях, кто-то уже заметил бы ошибку). Проблема с нынешним «доказательством» состоит в том, что оно «по построению», а не «по аргументу» (как в двух упомянутых статьях). Тогда трудно будет указать на конкретное место, где «строительство» терпит неудачу. Особенно, когда «конструкция» такая неточная. Вот почему я думаю, что теперь ОБЯЗАННОСТЬ автора, а не нас, указывать на это место (где Тардос не проходит свою конструкцию.)

Стасис