Inaproximidad de la cubierta del conjunto: ¿puedo suponer m = poli (n)?

Estoy tratando de mostrar que un cierto problema no es posible por una reducción de la cobertura establecida. Mi reducción transforma una instancia con conjuntos de tierra de conjuntos de tamaño $n$ y $m$ en una instancia de mi problema donde un determinado parámetro $r$ es de tamaño $O(n+m)$ . Entonces puedo mostrar que una instancia de la cubierta del conjunto donde el tamaño de la cubierta es s corresponde a una instancia de mi problema donde el tamaño de la solución óptima es $2s$ (o algo así), y viceversa. Me gustaría invocar a Raz-Safra para concluir que mi problema es inabordable hasta un factor de $c \log{r}$ , por alguna constante $c$. Esto funcionaría bien si pudiera suponer que $m$ está delimitada por un polinomio fijo de $n$ . ¿Alguien sabe si es kosher asumir esto? Esto es ciertamente cierto para la familia de instancias utilizadas en la prueba de dureza NP estándar para la cobertura del conjunto, pero no estoy seguro de si este sigue siendo el caso para el tipo de reducciones de PCP empleadas por Raz y Safra.

Sí, el número de conjuntos m en una instancia de cubierta de conjunto es polinomial en el número de elementos.

Por cierto, los resultados de dureza de última generación para Set-Cover son:

• Con Noga Alon y Muli Safra, mostramos cómo usar el PCP Raz-Safra / Arora-Sudan para obtener una mejor constante $c$ en el factor de dureza $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

• Recientemente publiqué una nota sobre cómo adaptar la reducción de Feige a un resultado de dureza NP (es decir, un resultado basado en ), asumiendo una conjetura plausible sobre PCP (una conjetura que llamo "La Conjetura de los Juegos de Proyección" - una especialización de la "Conjetura de escala móvil" de 1993 a los juegos de proyección).$P\neq NP$

  http://eccc.hpi-web.de/report/2011/112/ (más tarde descubrí que la reducción ofrece una compensación óptima entre y la reducción de la reducción).$\epsilon$