Вопросы с тегом «approximation-hardness»

Твердость аппроксимации, ака неприемлемость.

64
Разрешены ли границы времени выполнения в P? (ответ: нет)

Заданный вопрос состоит в том, является ли следующий вопрос разрешимым: Проблема   Учитывая целое число kkk и обещанная машина Тьюринга MMM в P, является ли время выполнения MMM O(nk)O(nk){O}(n^k) относительно длины ввода nnn ? Узкий ответ «да», «нет» или «открытый» является приемлемым (со...

38
Оптимальные жадные алгоритмы для NP-сложных задач

Жадность, из-за отсутствия лучшего слова, это хорошо. Одной из первых алгоритмических парадигм, изучаемых в курсе вводных алгоритмов, является жадный подход . Жадный подход приводит к простым и интуитивно понятным алгоритмам для многих задач в P. Более интересно, что для некоторых NP-трудных задач...

36
Твердость аппроксимации без теоремы PCP

Важное применение теоремы PCP состоит в том, что она дает результаты типа «твердость приближения». В некоторых относительно более простых случаях такую ​​твердость можно доказать без PCP. Есть ли, однако, какой-либо случай, когда твердость результата аппроксимации была сначала доказана с...

32
Является ли Gap-3SAT NP-полным даже для формул 3CNF, в которых пара переменных не встречается в значительно большем количестве предложений, чем в среднем?

В этом вопросе формула 3CNF означает формулу CNF, в которой каждое предложение включает ровно три различные переменные. Для константы 0 < s <1 Gap-3SAT s является следующей проблемой обещания: GAP-3sat сек экземпляра : а 3CNF формула φ. Да-обещание : φ выполнимо. Нет-обещание : Нет истину...

32
Твердость аппроксимации при условии NP! = CoNP

Два общих предположения для доказательства твердости результатов аппроксимации - это и гипотеза об уникальных играх. Есть ли какая-либо сложность результатов аппроксимации, предполагающих ? Я ищу проблему такую, что «трудно приблизить пределах коэффициента если ».N P ≠ c o N P A A α N P = c o N Pп≠...

26
Когда расслабленно считать трудно?

Предположим, что мы решили проблему подсчета правильных раскрасок путем подсчета взвешенных раскрасок следующим образом: каждая правильная раскраска получает вес 1, а каждая неправильная раскраска получает вес где c - некоторая постоянная, а v - число ребер с конечными точками, окрашенными...

26
Сборник лучших результатов аппроксимации и твердости для задач оптимизации NP

Знаете ли вы какие-либо современные вики, посвященные задачам оптимизации NP, с их наилучшим приближением и результатом твердости? Судя по отзывам, можно предположить, что такого ресурса нет (см. В конце этого вопроса два близких варианта). - добавлено 8 февраля. Поскольку за последние два...

24
Твердость аппроксимации - аддитивная ошибка

Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо...

22
Алгоритмы аппроксимации полиномиального времени для машинного планирования: сколько осталось открытых задач?

В 1999 году Петра Шурман и Герхард Дж. Вёгингер опубликовали статью «Алгоритмы аппроксимации полиномиального времени для машинного планирования: десять открытых задач» . С тех пор, насколько мне известно, обзоры, которые касались бы одного и того же списка проблем, не появлялись. Таким образом,...

22
Что такое UG-твердость и чем она отличается от NP-жесткости, основанной на гипотезе уникальных игр?

Есть много результатов неприемлемости, которые основаны на гипотезе об уникальных играх. Например, Предполагая гипотезу об уникальных играх, трудно вычислить аппроксимацию задачи максимального разреза в пределах коэффициента R для любой константы R > R GW . (Здесь R GW = 0,878… - коэффициент...

20
Примеры твердости фазовых переходов

Предположим, у нас есть проблема, параметризованная вещественным параметром p, который «легко» решить, когда и «трудно», когда для некоторых значений , . p = p 1 p 0 p 1p=p0p=p0p=p_0p=p1p=p1p=p_1п0p0p_0п1p1p_1 Одним из примеров является подсчет спиновых конфигураций на графиках. Считая взвешенные...

16
Почему коэффициенты дифференциальной аппроксимации недостаточно хорошо изучены по сравнению со стандартными, несмотря на заявленные преимущества?

Существует стандартная теория приближений, в которой коэффициент приближения равен supAOPTвирAОпT\sup\frac{A}{OPT} (для задач сMINMяNMINзадачами),AAA- значение, возвращаемое некоторым алгоритмомAAAаOPTОпTOPT- оптимальное значение. И еще одна теории, что издифференциального приближениягде отношение...

16
UGC твердость предиката

Фон : В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих 8ϵϵ\epsilonиз...

15
наименьший размер цепи с использованием вентилей XOR

Предположим, нам дан набор из n булевых переменных x_1, ..., x_n и набора из m функций y_1 ... y_m, где каждый y_i является XOR (заданного) подмножества этих переменных. Цель состоит в том, чтобы вычислить минимальное количество операций XOR, которое необходимо выполнить для вычисления всех этих...

15
Ударять множество попарно пересекающихся семейств

Наезд набор из семейства является подмножеством из такое , что для . Задача найти минимальное множество попаданий данного семейства NP-трудна в общем, поскольку она обобщает проблему покрытия вершин. Теперь мой вопрос:S= { S1, … , SN}Sзнак равно{S1,...,SN}\mathcal{S} = \{S_1, \dots, S_n\}ЧАСЧАСH⋃Nя...

15
Аппроксимация в субэкспонентальное время

Есть исследования об алгоритмах аппроксимации для NP полных задач за полиномиальное время и точных алгоритмов за экспоненциальное время. Проводятся ли исследования по алгоритмам аппроксимации для полных задач NP в субэкспоненциальном времени вида где...

15
Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...

14
Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...

14
Означает ли PSPACE-полнота твердость аппроксимации?

В другом посте cstheorySE упоминается, что PSPACE-полнота подразумевает APX-жесткость. Кто-нибудь может объяснить / поделиться ссылкой на это? Это "плотно"? (т. е. существуют ли PSPACE-полные задачи, задача оптимизации которых допускает постоянную аппроксимацию множителя за много времени?) Как...

12
сложность аппроксимации хроматического числа в графах с ограниченной степенью

Я ищу результаты твердости по раскраске вершин графов с ограниченной степенью. Учитывая граф , мы знаем, что для любого ϵ > 0 трудно приблизить χ ( G ) с множителем | V | 1 - ϵ, если NP = ZPP [ 1 ]. Но что, если максимальная степень G ограничена d ? Существуют ли в этом случае коэффициенты...