Функция Тардос - Tardos function - Wikipedia

В теория графов и сложность схемы, то Функция Тардос это инвариант графа представлен Эва Тардос в 1988 г., обладающий следующими свойствами:^[1][2]

• Словно Число Ловаса из дополнение графа, функция Тардос зажата между номер клики и хроматическое число графа. Эти два числа оба NP-жесткий вычислить.
• Функция Тардос является монотонной в том смысле, что добавление ребер к графу может только привести к увеличению или сохранению ее функции Тардос, но никогда не уменьшится.
• Функция Тардос может быть вычислена в полиномиальное время.
• Любой монотонная схема для вычисления функции Тардос требуется экспоненциальный размер.

Чтобы определить свою функцию, Тардос использует схема полиномиальной аппроксимации для числа Ловаса на основе эллипсоидный метод и предоставлено Грётшель, Ловас и Шрайвер (1981).^[3] Однако приближение числа Ловаса дополнения и последующее округление приближения до целого числа не обязательно приведет к монотонной функции. Чтобы сделать результат монотонным, Тардос аппроксимирует число Ловаса дополнения с точностью до аддитивной ошибки ${\displaystyle 1/n^{2}}$, добавляет ${\displaystyle m/n^{2}}$ с приближением, а затем округляет результат до ближайшего целого числа. Здесь ${\displaystyle m}$ обозначает количество ребер в данном графе, а ${\displaystyle n}$ обозначает количество вершин.^[1]

Тардос использовала свою функцию, чтобы доказать экспоненциальное разделение возможностей монотонных логических схем и произвольных схем. Александр Разборов, ранее использовавшиеся, чтобы показать, что кликовое число требует экспоненциально больших монотонных схем,^[4][5] также показывает, что функция Тардос требует экспоненциально больших монотонных схем, несмотря на то, что ее можно вычислить немонотонной схемой полиномиального размера. Позже та же функция использовалась для обеспечения контрпример к предполагаемому доказательству P ≠ NP Норберта Блюма.^[6]

Рекомендации

1. Тардос, Э. (1988), «Разрыв между монотонной и немонотонной сложностью схемы экспоненциальный» (PDF), Комбинаторика, 8 (1): 141–142, Дои:10.1007 / BF02122563, МИСТЕР  0952004
2. Юкна, Стасис (2012), Сложность логической функции: достижения и рубежи, Алгоритмы и комбинаторика, 27, Springer, стр. 272, г. ISBN  9783642245084
3. Грётшель, М.; Ловас, Л.; Шрайвер, А. (1981), "Метод эллипсоидов и его последствия в комбинаторной оптимизации", Комбинаторика, 1 (2): 169–197, Дои:10.1007 / BF02579273, МИСТЕР  0625550.
4. Разборов, А.А. (1985), "Нижние оценки монотонной сложности некоторых булевых функций", Доклады Академии Наук СССР, 281 (4): 798–801, МИСТЕР  0785629
5. Алон, Н.; Боппана, Р. Б. (1987), "Монотонная схемная сложность булевых функций", Комбинаторика, 7 (1): 1–22, CiteSeerX  10.1.1.300.9623, Дои:10.1007 / BF02579196, МИСТЕР  0905147
6. Тревизан, Лука (15 августа 2017 г.), «О заявленном доказательстве Норберта Блюма того, что P не равно NP», в теории