В теории вычислительной сложности сокращение разрыва — это сокращение до определенного типа проблемы принятия решения, известной как проблема c-промежутка . Такие сокращения предоставляют информацию о сложности аппроксимации решений оптимизационных задач .. Короче говоря, проблема разрыва относится к проблеме, цель которой состоит в том, чтобы отличить случаи, когда лучшее решение выше одного порога, от случаев, когда лучшее решение ниже другого порога, так что между двумя порогами есть разрыв. Уменьшение зазора можно использовать для демонстрации результатов неаппроксимации, как если бы проблема могла быть аппроксимирована с лучшим коэффициентом, чем размер зазора, тогда алгоритм аппроксимации можно использовать для решения соответствующей проблемы с зазором.
Мы определяем проблему c -разрыва следующим образом: [1] при заданной задаче оптимизации (максимизации или минимизации) P эквивалентная проблема c -разрыва различает два случая, для входных данных k и экземпляра x задачи P :
Обратите внимание, что всякий раз, когда OPT попадает между пороговыми значениями, нет требований к тому, каким должен быть результат. Допустимый алгоритм для проблемы c -промежутка может ответить на что угодно, если OPT находится в середине промежутка. Значение c не обязательно должно быть постоянным; это может зависеть от размера экземпляра P . Обратите внимание, что c - аппроксимация решения экземпляра P по крайней мере так же сложна, как решение c - промежутковой версии P .
Аналогично можно определить проблему ( a , b ) -промежутка . Разница в том, что пороги не зависят от ввода; вместо этого нижний порог равен a, а верхний порог равен b .
Сокращение, производящее зазоры, — это сокращение от задачи оптимизации до задачи c-зазора, так что быстрое решение проблемы c-зазора позволяет быстро решить задачу оптимизации. Термин «производство разрыва» возникает из-за характера редукции: оптимальное решение в задаче оптимизации отображается на противоположную сторону разрыва от любого другого решения посредством редукции. Таким образом, возникает разрыв между оптимальным решением и любым другим решением.
Простым примером редукции, приводящей к разрыву, является неметрическая задача коммивояжёра (т. е. где стоимость ребер графа не обязательно должна удовлетворять условиям метрики ). Мы можем сократить из гамильтонова путизадачу на заданном графе G = (V, E) к этой задаче следующим образом: мы строим полный граф G' = (V, E'), для задачи коммивояжера. Для каждого ребра e ∈ G' мы принимаем стоимость его обхода равной 1, если e находится в исходном графе G, и ∞ в противном случае. Гамильтонов путь в исходном графе G существует тогда и только тогда, когда существует решение коммивояжера с весом (|V|-1). Однако если такого гамильтонова пути не существует, то лучший тур коммивояжера должен иметь вес не менее |V|. Таким образом, гамильтонов путь сводится к |V|/(|V|-1)-щелевому неметрическому коммивояжеру.