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$

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).