Лемма об изоляции

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

Первая лемма об изоляции была предложена Валиантом и Вазирани (1986) , хотя и не под этим названием.Их лемма об изоляции выбирает случайное количество случайных гиперплоскостей и обладает тем свойством, что с немалой вероятностью пересечение любого фиксированного непустого пространства решений с выбранными гиперплоскостями содержит ровно один элемент. Этого достаточно, чтобы показать теорему Валианта – Вазирани :существует рандомизированное полиномиальное сведение от проблемы выполнимости булевых формул к проблеме определения того, имеет ли булева формула единственное решение. Малмули, Вазирани и Вазирани (1987) ввели лемму об изоляции несколько иного типа:Здесь каждой координате пространства решений присваивается случайный вес в определенном диапазоне целых чисел, и свойство состоит в том, что с немалой вероятностью в пространстве решений есть ровно один элемент, который имеет минимальный вес. Это можно использовать для получения рандомизированного параллельного алгоритма для задачи максимального соответствия .

В литературе были представлены более строгие леммы об изоляции, отвечающие различным потребностям в различных условиях.Например, лемма об изоляции Чари, Рохатги и Шринивасана (1993) имеет те же гарантии, что и лемма Малмули и др., Но она использует меньше случайных битов.В контексте экспоненциального времени гипотезы Калабро и др. (2008) доказали лемму об изоляции для формул k-КНФ .Ноам Та-Шма ^[1] дает лемму об изоляции с немного более сильными параметрами и дает нетривиальные результаты, даже если размер весовой области меньше количества переменных.

Лемма об изоляции Малмули, Вазирани и Вазирани.

Лемма. Позволять

n

и

N

— положительные целые числа, и пусть

{\mathcal {F}}

быть произвольным непустым семейством подмножеств вселенной

\{1,\dots ,n\}

. Предположим, что каждый элемент

x\in \{1,\dots ,n\}

во вселенной получает целочисленный вес

w(x)

, каждый из которых выбирается независимо и равномерно случайным образом из

\{1,\dots ,N\}

. Вес набора S в

{\mathcal {F}}

определяется как

w(S)=\sum _{x\in S}w(x)\,.

Тогда с вероятностью не менее

1-n/N

, есть уникальный набор в

{\mathcal {F}}

который имеет минимальный вес среди всех наборов

{\mathcal {F}}

.

Примечательно, что лемма ничего не предполагает о природе семейства. ${\mathcal {F}}$ : например ${\mathcal {F}}$ может включать все $2^{n}-1$ непустые подмножества. Поскольку вес каждого набора в ${\mathcal {F}}$ находится между $1$ и $nN$ в среднем будет $(2^{n}-1)/(nN)$ наборы каждого возможного веса.Тем не менее, с большой вероятностью существует уникальный набор, имеющий минимальный вес.

Малмули, Вазирани и доказательство Вазирани

Предположим, мы зафиксировали веса всех элементов, кроме элемента x . Тогда x имеет пороговый вес α , такой, что если вес w ( x ) x больше α , то он не содержится ни в каком подмножестве минимального веса, и если $w(x)\leq \alpha$ , то оно содержится в некоторых наборах минимального веса. Далее заметим, что если $w(x)<\alpha$ , то каждое подмножество минимального веса должно содержать x (поскольку, когда мы уменьшаем w(x) от α , множества, не содержащие x, не уменьшают вес, а те, которые содержат x, уменьшают). Таким образом, неоднозначность относительно того, содержит ли подмножество минимального веса x или нет, может возникнуть только тогда, когда вес x точно равен его порогу; в этом случае мы будем называть x «сингулярным». Теперь, поскольку порог x был определен только через веса других элементов , он не зависит от w(x) и, следовательно, поскольку w ( x ) выбирается равномерно из {1, …, N },

\Pr[x{\text{ is singular}}]=\Pr[w(x)=\alpha ]\leq 1/N

и вероятность того, что некоторый x является сингулярным, не превосходит n/N . Поскольку существует единственное подмножество минимального веса тогда и только тогда, когда ни один элемент не является сингулярным, отсюда следует утверждение леммы.

Замечание: Лемма справедлива при $\leq$ (а не =), поскольку возможно, что некоторый x не имеет порогового значения (т. е. x не будет ни в каком подмножестве минимального веса, даже если w ( x ) получит минимально возможное значение, 1).

Доказательство Джоэла Спенсера

Это переформулированная версия приведенного выше доказательства, предложенная Джоэлом Спенсером (1995). ^[2]

Для любого элемента x в наборе определите

\alpha (x)=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\}).

Обратите внимание, что $\alpha (x)$ зависит только от весов элементов, отличных от x , а не от самого w ( x ). Итак, какова бы ни была ценность $\alpha (x)$ , поскольку w ( x ) выбирается равномерно из {1, …, N }, вероятность того, что она равна $\alpha (x)$ не более 1/ N . Таким образом, вероятность того, что $w(x)=\alpha (x)$ для некоторого x не более n/N .

если в , Теперь ${\mathcal {F}}$ с минимальным весом, то, взяв любой x из A\B , получим

{\begin{aligned}\alpha (x)&=\min _{S\in {\mathcal {F}},x\not \in S}w(S)-\min _{S\in {\mathcal {F}},x\in S}w(S\setminus \{x\})\\&=w(B)-(w(A)-w(x))\\&=w(x),\end{aligned}}

и, как мы видели, это событие происходит с вероятностью не более n/N .

Примеры/приложения

Первоначальное применение заключалось в поиске идеальных паросочетаний минимального (или максимального) веса в графе. Каждому ребру присваивается случайный вес в {1, …, 2 m }, и ${\mathcal {F}}$ — множество совершенных паросочетаний, так что с вероятностью не менее 1/2 существует единственное совершенное паросочетание. Когда каждое неопределенное $x_{ij}$ в матрице Тутте графа заменяется на $2^{w_{ij}}$ где $w_{ij}$ — случайный вес ребра, мы можем показать, что определитель матрицы не равен нулю, и в дальнейшем использовать это для поиска соответствия.
В более общем плане в статье также отмечается, что любая задача поиска вида «Для заданной системы $(S,{\mathcal {F}})$ , найдите набор в ${\mathcal {F}}$ можно свести к задаче решения вида «Существует ли множество в ${\mathcal {F}}$ с общим весом не более k ?". Например, он показал, как решить следующую задачу, поставленную Пападимитриу и Яннакакисом, для которой (на момент написания статьи) неизвестен детерминированный алгоритм с полиномиальным временем: задан граф и подмножество ребер, отмеченных как «красные», находят идеальное совпадение ровно с k красными ребрами.
Теорема Валианта–Вазирани , касающаяся уникальных решений NP-полных задач, имеет более простое доказательство с использованием леммы об изоляции. Это доказывается рандомизированным сокращением от CLIQUE до UNIQUE-CLIQUE. ^[3]
Бен-Дэвид, Чор и Голдрейх (1989) используют доказательство Валианта-Вазирани в своем сокращении поиска до решения для средней сложности .
Ави Вигдерсон использовал лемму об изоляции в 1994 году, чтобы провести рандомизированное сокращение от NL до UL и тем самым доказать, что NL/poly ⊆ ⊕L/poly. ^[4] Позже Рейнхардт и Аллендер снова использовали лемму об изоляции, чтобы доказать, что NL/poly = UL/poly. ^[5]
В книге Хемаспаандры и Огихары есть глава, посвященная технике изоляции, включая обобщения. ^[6]
Лемма изоляции была предложена в качестве основы схемы цифровых водяных знаков . ^[7]
Продолжается работа по дерандомизации леммы об изоляции в конкретных случаях. ^[8] и об использовании его для проверки личности. ^[9]

Примечания

Ссылки

Арвинд, В.; Мукхопадхьяй, Партха (2008). Дерандомизация леммы об изоляции и нижние границы размера схемы . Материалы 11-го международного семинара APPROX 2008 и 12-го международного семинара RANDOM 2008 по аппроксимации, рандомизации и комбинаторной оптимизации: алгоритмы и методы. Бостон, Массачусетс, США: Springer-Verlag. стр. 276–289. arXiv : 0804.0957 . Бибкод : 2008arXiv0804.0957A . ISBN 978-3-540-85362-6 . Проверено 10 мая 2010 г.
Арвинд, В.; Мукхопадхьяй, Партха; Шринивасан, Шрикантх (2008). Новые результаты по некоммутативной и коммутативной проверке полиномиальной идентичности . Материалы 23-й ежегодной конференции IEEE по сложности вычислений 2008 г. Компьютерное общество IEEE. стр. 268–279. arXiv : 0801.0514 . Бибкод : 2008arXiv0801.0514A . ISBN 978-0-7695-3169-4 . Проверено 10 мая 2010 г.
Бен-Дэвид, С.; Чор, Б. ; Гольдрайх, О. (1989). К теории средней сложности случая . Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89. п. 204. дои : 10.1145/73007.73027 . ISBN 0897913078 .
Калабро, К.; Импальяццо, Р.; Кабанец, В.; Патури, Р. (2008). «Сложность уникального k-SAT: лемма изоляции для k-CNF» . Журнал компьютерных и системных наук . 74 (3): 386. doi : 10.1016/j.jcss.2007.06.015 .
Чари, С.; Рохатги, П.; Шринивасан, А. (1993). Оптимальная по случайности изоляция уникальных элементов с приложениями для идеального сопоставления и решения связанных с этим задач . Материалы двадцать пятого ежегодного симпозиума ACM по теории вычислений - STOC '93. п. 458. дои : 10.1145/167088.167213 . hdl : 1813/6129 . ISBN 0897915917 .
Хемаспаандра, Лейн А.; Огихара, Мицунори (2002). «Глава 4. Техника изоляции» (PDF) . Товарищ по теории сложности . Спрингер. ISBN 978-3-540-67419-1 .
Маджумдар, Рупак; Вонг, Дженнифер Л. (2001). Водяные знаки SAT с использованием лемм комбинаторной изоляции . Материалы 38-й ежегодной конференции по автоматизации проектирования. Лас-Вегас, Невада, США: ACM. стр. 480–485. CiteSeerX 10.1.1.16.9300 . дои : 10.1145/378239.378566 . ISBN 1-58113-297-2 .
Рейнхардт, К.; Аллендер, Э. (2000). «Делаем недетерминизм однозначным» (PDF) . SIAM Journal по вычислительной технике . 29 (4): 1118. doi : 10.1137/S0097539798339041 .
Малмули, Кетан ; Вазирани, Умеш ; Вазирани, Виджай (1987). «Сопоставление так же просто, как инверсия матрицы». Комбинаторика . 7 (1): 105–113. CiteSeerX 10.1.1.70.2247 . дои : 10.1007/BF02579206 .
Юкна, Стасис (2001). Экстремальная комбинаторика: с приложениями в информатике . Спрингер. стр. 147–150. ISBN 978-3-540-66313-3 .
Валиант, Л.; Вазирани, В. (1986). «NP — это так же просто, как найти уникальные решения» (PDF) . Теоретическая информатика . 47 : 85–93. дои : 10.1016/0304-3975(86)90135-0 .
Вигдерсон, Ави (1994). НЛ/поли ⊆ ⊕Л/поли (PDF) . Материалы 9-й конференции «Структуры в сложности». стр. 59–62.

Внешние ссылки

[tashmaiso-1] Ноам Та-Шма (2015); Простое доказательство леммы об изоляции в eccc

[2] Джукна (2001)

[3] Малмули, Вазирани и Вазирани (1987)

[4] Вигдерсон (1994)

[5] Рейнхардт и Аллендер (2000)

[6] Хемаспаандра и Огихара (2002)

[7] Маджумдар и Вонг (2001)

[8] Арвинд и Мукхопадьяй (2008)

[9] Арвинд, Мукхопадьяй и Шринивасан (2008)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]