Лемма об изоляции - Isolation lemma

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

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

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

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

Любой линейная программа со случайно выбранной линейной функцией стоимости имеет уникальный оптимум с высокой вероятностью. Лемма об изоляции Малмули, Вазирани и Вазирани распространяет этот факт на произвольный наборы и функция случайной стоимости, которая выбирается с использованием несколько случайные биты.

Лемма. Позволять ${ displaystyle n}$ и ${ displaystyle N}$ - натуральные числа, и пусть ${ displaystyle { mathcal {F}}}$ - произвольное семейство подмножеств вселенной ${ Displaystyle {1, точки, п }}$. Предположим, что каждый элемент ${ Displaystyle х в {1, точки, п }}$ во вселенной получает целочисленный вес ${ Displaystyle ш (х)}$, каждый из которых выбирается независимо и равномерно случайным образом из ${ Displaystyle {1, точки, N }}$. Вес комплекта S в ${ displaystyle { mathcal {F}}}$ определяется как

${ Displaystyle вес (S) = сумма _ {х в S} вес (х) ,.}$

Тогда с вероятностью не менее ${ displaystyle 1-n / N}$, Существует уникальный установить в ${ displaystyle { mathcal {F}}}$ который имеет минимальный вес среди всех наборов ${ displaystyle { mathcal {F}}}$.

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

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

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

Примечания

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

внешняя ссылка

• Любимые теоремы: уникальные свидетели к Лэнс Фортноу
• Лемма об изоляции и не только к Ричард Дж. Липтон