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

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

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

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

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

Ссылки

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