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

22

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

Теорема 6 : Пусть - любая монотонная булева функция. Предположим, что существует CNF-DNF-аппроксиматор который можно использовать для доказательства нижней оценки . Тогда также можно использовать для доказательства той же нижней оценки для .A C m ( f ) A C s t ( f )fBnACm(f)ACst(f)

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

В этой статье они обсуждают сложность функции , которая в общем случае не является монотонной булевой функцией, поскольку увеличение ребер может сделать больше, чтобы сделать false, когда это было верно с меньшим во входных данных. Функция , как правило, не вычисляет в и в .φ ( Х ) φ ( X ) F ( v ) 1 φ ( X ) F ( v ) 1 Т 1 0 Т 0φ(X)f(v)φ(X)φ(X)f(v)1φ(X)f(v)1T10T0

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

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

user144527
источник
Хорошим источником была бы книга Юкны, с.272 (как раз перед теоремой 9.28). Учитывая (не булеву) функцию , рассмотрим булеву функцию которая является пороговым значением : Результат применяется. е ф ф е ф ( G ) = { 1 , если  ф ( G ) ϕfϕϕ
fϕ(G)={1if ϕ(G)n0otherwise
Клемент С.
Итак, чтобы быть ясным, вы говорите мне, что будет оценивать до в кликах размера и в графах вершин, индуцированных собственно красители? 1 fϕ(G)1 0nn0nn1
user144527
4
Конечно, это не относится ни к одной . Но функция Тардоса основана на монотонной граф-функции удовлетворяющей . Итак, пороговое значение of делает именно то, что вы говорите. Смотрите конец Раздела 9.8 здесь . е ф ф ш ( G ) & le ; ф ( G ) & le ; х ( G ) F ф фϕfϕϕω(G)ϕ(G)χ(G)fϕϕ
Стасис
4
Правильно. Кстати, я на самом деле не понимаю, почему люди голосуют против вашего (приемлемого ввиду всего этого шума вокруг этого «доказательства») вопроса? Теперь автор этой очереди заявления P! = NP: объясните, почему «доказательство» НЕ будет работать для функции Тардоса. Укажите страницу X и строку (и) Y в документе. Подсказка: ошибка заключается в ограничении количества ошибок, внесенных во время аппроксимации (отрицания могут уничтожить множество ранее «действительных» терминов). В противном случае (без объяснения) = нет «доказательства».
Стасис
1
@Stasys, ваш первый комментарий может быть ответом.
Каве

Ответы:

18

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

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

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

То, что делает Тардос, заключается в следующем. Она начинает с функции графа , где - знаменитая тэта-функция Ловаша. Фундаментальный факт заключается в том, что число находится между номером клика и хроматическим числом: . Затем она использует тот факт, что может быть аппроксимирована за полиномиальное время. На основании этого она определяет граф-функцию со следующими свойствами:thetas ; ф ( G )φ(G):=ϑ(G¯)ϑφ(G)ϑ ( G ) ϕ ( G )ω(G)φ(G)χ(G)ϑ(G)ϕ(G)

  1. Значения могут быть вычислены за полиномиальное время (в количестве вершин). nϕ(G)n
  2. ϕ является монотонным: добавление ребер может только увеличить его значение.
  3. Gω(G)ϕ(G)χ(G) имеет место для всех графов . G

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

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

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