Niedopuszczalność pokrycia zestawu: czy mogę założyć m = poli (n)?

Staram się pokazać, że pewien problem jest nie do przyjęcia przez redukcję z zestawu. Moja redukcja przekształca instancję z zestawem naziemnym o rozmiarach i w instancję mojego problemu, w której pewien parametr ma rozmiar . Mogę następnie pokazać, że wystąpienie zestawu okładki, w którym rozmiar okładki jest s, odpowiada wystąpieniu mojego problemu, w którym rozmiar optymalnego rozwiązania wynosi (lub coś takiego) i odwrotnie. Chciałbym przywołać Raz-Safrę, aby dojść do wniosku, że mój problem jest niemożliwy do oszacowania do współczynnika , dla niektórych stałych . To działałoby dobrze, gdybym mógł założyć, że $n$ $m$ $r$ $O(n+m)$ $2s$ $c \log{r}$ $c$ $m$ jest ograniczony stałym wielomianem . Czy ktoś wie, czy to koszerne? Jest to z pewnością prawda dla rodziny instancji zastosowanych w standardowym proofie twardości NP dla zestawu osłon, ale nie jestem pewien, czy tak jest w przypadku redukcji PCP zastosowanych przez Raz i Safrę. $n$

cc.complexity-theory approximation-hardness set-cover

— Edith Elkind
źródło

Tak, liczba zestawów m w instancji set-cover jest wielomianowa pod względem liczby elementów.

Nawiasem mówiąc - najnowocześniejsze wyniki twardości dla Set-Cover to:

Dzięki Noga Alon i Muli Safra pokazaliśmy, jak korzystać z Raz-Safra / Arora-Sudan PCP, aby uzyskać lepszą stałą $c$ we współczynniku twardości $c\log n$ .

http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps
Feige pokazał, jak uzyskać optymalny współczynnik twardości $(1-\epsilon)\ln n$ , zakładając $NP\not\subseteq DTIME(n^{\log\log n})$ .

http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf
Niedawno opublikowałem notatkę, w jaki sposób dostosować redukcję Feige'a do wyniku twardości NP (tj. Wyniku opartego na $P\neq NP$ ), zakładając prawdopodobną hipotezę na temat PCP (przypuszczenie, które nazywam „The Conject Games Conjecture” - specjalizacja „Sliding Scale Conjecture” z 1993 roku do gier projekcyjnych).

http://eccc.hpi-web.de/report/2011/112/ (później dowiedziałem się, że redukcja zapewnia optymalny kompromis między $\epsilon$ i powiększenie redukcyjne).

— Dana Moshkovitz
źródło

Jakie jest najsłabsze założenie separacji, które wciąż da

(1 - ϵ) \log n

$(1-\epsilon)\log n$ twardość?

— Suresh Venkat

Dana, dziękuję za odpowiedź! Dalsze pytanie, jeśli nie masz nic przeciwko: czy jest to „głupie” pytanie, tj. Czy są jakieś uwagi na wysokim poziomie, które sugerują m = poli (n), czy też tak naprawdę trzeba znać Dowód twardości Raz-Safra, aby odpowiedzieć na moje pytanie?

— Edith Elkind,

@Suresh: Zakładam, że masz na myśli

(1 - ϵ) \ln n

$(1-\epsilon)\ln n$ . Założenie Feige (

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

$NP\not\subseteq DTIME(n^{\log\log n})$ ) i moje założenie („The Projection Games Conjecture”) są nieporównywalne. Wierzę, że moje założenie zostanie udowodnione w dającej się przewidzieć przyszłości.

— Dana Moshkovitz

@lostinjungle: Gdyby m nie było wielomianowe in, nie można by uznać redukcji za „redukcję wielomianową”. Szczególnym powodem, dla którego Raz-Safra / Arora-Sudan PCP daje m = poli (n) jest to, że istnieje zestaw na zmienną PCP / ograniczenie + i przypisanie do nich, a także liczbę zmiennych i ograniczeń, a także wielkość alfabetu jest wielomianowa, a liczba zapytań jest stała.

— Dana Moshkovitz

@DanaMoshkovitz: Dzięki! Nie jestem jednak pewien, czy rozumiem twoje pierwsze roszczenie. Co jest nie tak z następującą (hipotetyczną) redukcją: Zaczynam od wystąpienia (powiedzmy) osłony wierzchołków za pomocą

k

$k$ wierzchołki i utwórz instancję Set Cover za pomocą

m = k^{3}

$m = k^3$ zestawy i zestaw rozmiarów podłoża

n

$n$ , gdzie

n

$n$ jest rozwiązaniem

n^{\log n} = m

$n^{\log n} = m$ ? To zdecydowanie działa w czasie wieloczasowym. Wprawdzie nigdy nie widziałem takiej redukcji, ale nie wydaje się to logicznie niemożliwe. A może się mylę? Oczywiście na moje pierwotne pytanie już udzielono odpowiedzi, więc zignoruj to. Jestem po prostu ciekawy ...

— Edith Elkind