Inaproximabilidade da cobertura do conjunto: posso assumir m = poli (n)?

Eu estou tentando mostrar que um determinado problema é incompreensível devido a uma redução da cobertura do conjunto. Minha redução transforma uma instância com o conjunto de aterramento de tamanho e em uma instância do meu problema em que um determinado parâmetro é do tamanho . Em seguida, posso mostrar que uma instância de cobertura do conjunto em que o tamanho da capa é s corresponde a uma instância do meu problema em que o tamanho da solução ideal é (ou algo assim) e vice-versa. Gostaria de invocar Raz-Safra para concluir que meu problema é incompreensível até um fator de , para uma constante . Isso funcionaria bem se eu pudesse assumir que $n$ é delimitada por um polinômio fixo de $m$ $r$ $O(n+m)$ $2s$ $c \log{r}$ $c$ $m$ $n$ . Alguém sabe se é kosher assumir isso? Isso certamente é verdadeiro para a família de instâncias usadas na prova de dureza NP padrão para cobertura de conjunto, mas não tenho certeza se esse ainda é o caso do tipo de redução de PCP empregada por Raz e Safra.

cc.complexity-theory approximation-hardness set-cover Edith Elkind
fonte

Sim, o número de conjuntos m em uma instância de conjunto de capa é polinomial no número de elementos.

A propósito - os resultados da dureza de última geração para Set-Cover são:

Com Noga Alon e Muli Safra, mostramos como usar o PCP Raz-Safra / Arora-Sudan para obter uma constante melhor no fator de dureza $c$ $c\log n$ .

http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps
Feige mostrou como obter o fator de dureza ideal , assumindo $(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
Publiquei recentemente uma nota sobre como adaptar a redução de Feige a um resultado de dureza NP (ou seja, um resultado baseado em $P\neq NP$ ), assumindo uma conjectura plausível sobre PCPs (uma conjectura que chamo de "The Projection Games Conjecture" - uma especialização da 1993 "Slject Scale Conjecture" para jogos de projeção).

http://eccc.hpi-web.de/report/2011/112/ (mais tarde descobri que a redução oferece uma troca ideal entre e a explosão da redução). $\epsilon$

Dana Moshkovitz
fonte

Qual é a suposição de separação mais fraca que ainda produzirá uma dureza

(1 - ϵ) \log n

$(1-\epsilon)\log n$

Suresh Venkat

Dana, obrigado pela sua resposta! Uma pergunta de acompanhamento, se você não se importa: essa é uma pergunta "estúpida", ou seja, existem considerações de alto nível que impliquem m = poly (n), ou é o caso de alguém realmente saber o Prova de dureza Raz-Safra para responder à minha pergunta?

Edith Elkind

@ Suresh: Suponho que você queira dizer

. A suposição de Feige (

) e a minha suposição ( "a projecção Jogos conjectura") são incomparável. Acredito que minha suposição seria provada no futuro próximo.

(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})$

Dana Moshkovitz 02/10/19

@lostinjungle: Se m não tivesse sido polinomial em n, você não poderia considerar a redução uma "redução de tempo poli". A razão específica pela qual um PCP Raz-Safra / Arora-Sudão produz m = poli (n) é que existe um conjunto por variável / restrição + PCP e atribuição a eles, e o número de variáveis e restrições, bem como a o tamanho do alfabeto é polinomial e o número de consultas é constante.

Dana Moshkovitz

@DanaMoshkovitz: Obrigado! Não sei se entendi sua primeira afirmação. O que há de errado com a seguinte redução (hipotética): Começo com uma instância de (digamos) Vertex Cover com

vértices e crio uma instância de Set Cover com

sets e ground set do tamanho

, onde

é a solução para

? Definitivamente, isso funciona em poli-time. É certo que nunca vi uma redução como essa, mas não parece logicamente impossível. Ou eu estou errado? Obviamente, minha pergunta original já foi respondida, portanto, fique à vontade para ignorar esta. Só estou curioso ...

k

$k$

m = k^{3}

$m = k^3$

n

$n$

n

$n$

n^{\log n} = m

$n^{\log n} = m$

Edith Elkind

Inaproximabilidade da cobertura do conjunto: posso assumir m = poli (n)?

Respostas: