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

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

Чтобы определить свою функцию, Тардос использует схема полиномиальной аппроксимации для числа Ловаса на основе эллипсоидный метод и предоставлено Грётшель, Ловас и Шрайвер (1981).[3] Однако приближение числа Ловаса дополнения и последующее округление приближения до целого числа не обязательно приведет к монотонной функции. Чтобы сделать результат монотонным, Тардос аппроксимирует число Ловаса дополнения с точностью до аддитивной ошибки , добавляет с приближением, а затем округляет результат до ближайшего целого числа. Здесь обозначает количество ребер в данном графе, а обозначает количество вершин.[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», в теории