Неприменимость набора покрытия: могу ли я считать, что m = poly (n)?

Я пытаюсь показать, что определенная проблема недопустима из-за сокращения охвата. Мое сокращение превращает экземпляр с базовым набором размера и устанавливает в экземпляр моей проблемы, где определенный параметр имеет размер . Затем я могу показать, что экземпляр установленного покрытия, где размер покрытия равен s, соответствует экземпляру моей проблемы, где размер оптимального решения равен (или что-то в этом роде), и наоборот. Я хотел бы призвать Раз-Сафру заключить, что моя проблема недопустима вплоть до коэффициента , для некоторой константы . Это будет работать нормально, если бы я мог предположить, что $n$ $m$ $r$ $O(n+m)$ $2s$ $c \log{r}$ $c$ $m$ ограничен фиксированным полиномом от . Кто-нибудь знает, кошерно ли это считать? Это, конечно, верно для семейства экземпляров, используемых в стандартном доказательстве твердости NP для покрытия набора, но я не уверен, что это так и есть для тех видов PCP, которые используются в Raz и Safra. $n$

cc.complexity-theory approximation-hardness set-cover Эдит Элкинд
источник

Да, количество наборов m в экземпляре set-cover является полиномиальным по количеству элементов.

Между прочим - современные результаты твердости для Set-Cover:

С помощью Noga Alon и Muli Safra мы показали, как использовать PCP Raz-Safra / Arora-Sudan для получения лучшей константы в коэффициенте твердости . $c$ $c\log n$

http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps
Фейдж показал, как получить оптимальный коэффициент твердости , предполагая . $(1-\epsilon)\ln n$ $NP\not\subseteq DTIME(n^{\log\log n})$

http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf
Недавно я опубликовал заметку о том, как адаптировать уменьшение Фейге к результату NP-твердости (т.е. результату на основе ), предполагая правдоподобную гипотезу о PCP (гипотезу, которую я называю «Гипотеза о проекционных играх» - специализация "Гипотеза скользящей шкалы" 1993 года к проекционным играм). $P\neq NP$

http://eccc.hpi-web.de/report/2011/112/ (позже я обнаружил, что сокращение дает оптимальный компромисс между и увеличением сокращения). $\epsilon$

Дана Мошковиц
источник

Каково самое слабое предположение о разделении, которое все еще приведет к твердости?

(1 - ϵ) \log n

$(1-\epsilon)\log n$

Суреш Венкат

Дана, спасибо за ваш ответ! Дополнительный вопрос, если вы не возражаете: это «глупый» вопрос, т. Е. Есть ли какие-то соображения высокого уровня, которые подразумевают m = poly (n), или это тот случай, когда нужно знать Раз-сафра доказательство твердости ответить на мой вопрос?

Эдит Элкинд

@ Суреш: Полагаю, вы имеете в виду . Предположение о Фейге ( ) и мое предположение («Гипотеза о проекционных играх») несопоставимы. Я верю, что мое предположение подтвердится в обозримом будущем.

(1 - ϵ) \ln n

$(1-\epsilon)\ln n$

N P ⊈ D T I M E (n^{\log \log n})

$NP\not\subseteq DTIME(n^{\log\log n})$

Дана Мошковиц

@lostinjungle: Если бы m не было полиномом от n, вы не могли бы считать сокращение «сокращением по времени». Конкретная причина того, что PCP Раз-Сафра / Арора-Судан дает m = poly (n), заключается в том, что существует набор для переменной / ограничения + PCP и их присвоения, а также число переменных и ограничений, а также Размер алфавита полиномиален, а количество запросов постоянно.

Дана Мошковиц

@DanaMoshkovitz: Спасибо! Я не уверен, что понимаю вашу первую претензию, хотя. Что не так со следующим (гипотетическим) сокращением: я начинаю с экземпляра, скажем, Vertex Cover с вершинами, и создаю экземпляр Set Cover с множествами и наземным множеством размера , где - решение к ? Это определенно работает в поли-времени. По общему признанию, я никогда не видел такого сокращения, но это не кажется логически невозможным. Или я не прав? Конечно, на мой оригинальный вопрос уже дан ответ, поэтому не стесняйтесь игнорировать этот. Мне просто любопытно ...

k

$k$

m = k^{3}

$m = k^3$

n

$n$

n

$n$

n^{\log n} = m

$n^{\log n} = m$

Эдит Элкинд

Неприменимость набора покрытия: могу ли я считать, что m = poly (n)?

Ответы: