Сокращение разрыва - Gap reduction

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

проблема с зазором

Мы определяем проблема с зазором следующее:^[1] учитывая задачу оптимизации (максимизации или минимизации) P, эквивалентная задача c-зазора различает два случая для входа k и экземпляра x задачи P:

{ Displaystyle OPT_ {P} (х) leq k}

. Здесь лучшее решение экземпляра x проблемы P имеет стоимость или оценку ниже k.

{ displaystyle OPT_ {P} (x)> c cdot k}

. Здесь лучшее решение экземпляра x проблемы P имеет стоимость выше c⋅k. Таким образом, зазор между двумя порогами равен c.

Обратите внимание, что всякий раз, когда OPT оказывается между пороговыми значениями, нет никаких требований к тому, каким должен быть выход. Действительный алгоритм для проблемы c-промежутка может ответить на что угодно, если OPT находится в середине промежутка. Значение c не обязательно должно быть постоянным; это может зависеть от размера экземпляра P. Обратите внимание, что с-аппроксимация решение экземпляра P по крайней мере так же сложно, как решение версии P.

Можно определить (а, б) проблема зазора по аналогии. Разница в том, что пороги не зависят от входа; вместо этого нижний порог равен a, а верхний порог - b.

Уменьшение разрыва

Уменьшение разрыва - это снижение от задачи оптимизации к проблеме c-зазора, так что быстрое решение задачи c-зазора позволило бы быстро решить задачу оптимизации. Термин «создание разрыва» возникает из-за характера сокращения: оптимальное решение в задаче оптимизации отображается на противоположную сторону разрыва от любого другого решения посредством сокращения. Таким образом, возникает разрыв между оптимальным решением и любым другим решением.

Простым примером сокращения разрыва является неметрический Задача коммивояжера (то есть там, где стоимость ребер графа не обязательно должна удовлетворять условиям метрика ). Мы можем сократить от Гамильтонов путь Задача на заданном графе G = (V, E) к этой задаче следующим образом: мы строим полный граф G '= (V, E') для задачи коммивояжера. Для каждого ребра e ∈ G 'мы полагаем, что стоимость его обхода равна 1, если e находится в исходном графе G, и ∞ в противном случае. Гамильтонов путь в исходном графе G существует тогда и только тогда, когда существует решение коммивояжера с весом (| V | -1). Однако, если такой гамильтонов путь не существует, то поездка лучшего коммивояжера должна иметь вес не менее | V |. Таким образом, гамильтонов путь сводится к | V | / (| V | -1) -зонному неметрическому коммивояжеру.

Сокращение с сохранением зазоров

Сокращение с сохранением зазора - это снижение от проблемы c-зазора к проблеме c'-зазора. В частности, нам дан экземпляр x задачи A с | x | = n и хотите свести его к экземпляру x 'задачи B с | x' | = п '. Сокращение с сохранением зазора от A до B - это набор функций (k (n), k '(n'), c (n), c '(n')) таких, что

Для задач минимизации:

OPT_А(x) ≤ k ⇒ OPT_B(x ') ≤ k', и

OPT_А(x) ≥ c⋅k ⇒ OPT_B(х ') ≥ c'⋅k'

Для задач максимизации:

OPT_А(x) ≥ k ⇒ OPT_B(x ') ≥ k', и

OPT_А(x) ≤ k / c ⇒ OPT_B(х ') ≤ к' / с '

Если c '> c, то это уменьшение разрыва.

Примеры

Макс E3SAT

Эта проблема является формой Проблема логической выполнимости (SAT), где каждое предложение содержит три отдельных литерала, и мы хотим максимизировать количество удовлетворяемых предложений.^[1]

Хастад показал, что (1/2 + ε, 1-ε) -разрядная версия аналогичной задачи MAX E3-X (N) OR-SAT является NP-сложной.^[2] Задача MAX E3-X (N) OR-SAT - это форма SAT, где каждое предложение является XOR трех различных литералов, ровно один из которых инвертируется. Мы можем уменьшить с MAX E3-X (N) OR-SAT до MAX E3SAT следующим образом:

Пункт x_я ⊕ х_j ⊕ х_k = 1 преобразуется в (x_я ∨ х_j ∨ х_k) ∧ (¬x_я ∨ ¬x_j ∨ х_k) ∧ (¬x_я ∨ х_j ∨ ¬x_k) ∧ (x_я ∨ ¬x_j ∨ ¬x_k)

Пункт x_я ⊕ х_j ⊕ х_k = 0 преобразуется в (¬x_я ∨ ¬x_j ∨ ¬x_k) ∧ (¬x_я ∨ х_j ∨ х_k) ∧ (x_я ∨ ¬x_j ∨ х_k) ∧ (x_я ∨ х_j ∨ ¬x_k)

Если предложение не удовлетворяется в исходном экземпляре MAX E3-X (N) OR-SAT, то может быть выполнено не более трех из четырех соответствующих предложений в нашем экземпляре MAX E3SAT. Используя аргумент пробела, следует, что YES-экземпляр задачи имеет как минимум (1-ε) часть удовлетворенных клозов, в то время как NO-экземпляр проблемы имеет не более (1/2 + ε) (1) + (1/2-ε) (3/4) = (7/8 + ε / 4) -доля пунктов удовлетворены. Отсюда следует, что (7/8 + ε, 1 - ε) -разрыв MAX E3SAT NP-труден. Обратите внимание, что эта граница жесткая, так как случайное присвоение переменных дает ожидаемую долю удовлетворенных предложений 7/8.

Этикетка Обложка

В крышка этикетки задача определяется следующим образом: для двудольного графа G = (A∪B, E) с

А = А₁ ∪ А₂ ∪ ... ∪ А_k, | A | = n и | A_я| = n / k

B = B₁ ∪ B₂ ∪ ... ∪ B_k, | B | = n и | B_я| = n / k

Определим «суперебро» между A_я и B_j если хотя бы одно ребро существует из A_я в B_j в G, и определим покрываемое ребро, если хотя бы одно ребро из A_я в B_j покрыто.

в максимальное количество повторений версии задачи мы можем выбрать по одной вершине из каждого A_я и каждый B_я, и мы стремимся к максимальному увеличению количества покрытых ребер. в мин-повтор версии, мы должны покрыть все суперребра в графе и хотим минимизировать количество выбираемых вершин. Manurangsi и Мошковиц покажем, что (O (n^1/4), 1) -зонная версия обеих задач разрешима за полиномиальное время.^[3]