Функция Тардос

В теории графов и сложности схем функция Тардоса представляет собой инвариант графа, введенный Ивой Тардос в 1988 году и обладающий следующими свойствами:

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

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

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