Posso vincular a cardinalidade de um conjunto se o teste de associação a ele for conhecido como NP-complete?

Eu gostaria de ter um limite na cardinalidade do conjunto de gráficos de disco unitário com vértices. Sabe-se que verificar se um gráfico é membro desse conjunto é difícil para o NP. Isso leva a um limite inferior da cardinalidade, assumindo P NP? $N$ $\neq$

Por exemplo, suponha que exista uma ordem em todos os gráficos com vértices. A dureza NP implicaria então que a cardinalidade excede , caso contrário você poderia testar a associação no tempo polinomial fazendo uma pesquisa binária no conjunto? Eu acho que isso pressupõe que você tenha armazenado o conjunto na memória ... Isso é permitido? $N$ $2^N$

Definição: Um gráfico é um gráfico de disco unitário se cada vértice puder ser associado a um disco unitário no plano, de modo que os vértices sejam conectados sempre que seus discos se cruzarem.

Aqui está uma referência sobre a dureza NP dos testes de associação para gráficos de disco unitário: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
fonte

Gostaria de saber, existe um exemplo em que essa técnica fornece o limite inferior mais conhecido do tamanho de um conjunto? Isso seria uma aplicação combinatória indireta legal da teoria da complexidade.

Sasho Nikolov

Obrigado por sua ajuda. Ambas as respostas foram úteis e perspicazes; Eu teria aceitado qualquer um na ausência do outro.

David Choi

Respostas:

Não tenho certeza se você está fazendo esta pergunta pela técnica ou pela resposta, mas há um artigo recente de McDiarmid e Mueller em que eles mostram que o número de gráficos de disco unitário (rotulados) em vértices é ; consulte http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf . $n$ $2^{(2 + o(1))n}$

Bart Jansen
fonte

O Teorema de Mahaney afirma que existem conjuntos esparsos de NP-completos, se P = NP. Portanto, assumindo implica um super-polinomial limite inferior para o número de casos de tamanho em conjuntos -Complete, para infinitamente muitas . Isto é, se , em seguida, qualquer conjunto -completo deve ter algum de tal modo que para infinitamente muitas inteiros , o conjunto contém pelo menos cadeias de comprimento . $P \neq NP$ $n$ $NP$ $n$ $P \neq NP$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

$2^{n^{\epsilon}}$

[1] H. Buhrman e JM Hitchcock, NP-Hard Sets são exponencialmente densos, a menos que coNP ⊆ NP / poly, Na IEEE Conference on Computational Complexity, páginas 1–7, 2008

[2] Eric Allender, Um relatório de status da pergunta P Versus NP, Avanços em computadores, volume 77, 2009, páginas 117-147

Mohammad Al-Turkistany
fonte

[Mah82] SR Mahaney. Conjuntos completos esparsas para NP: Solução de uma conjectura por Berman e Hartmanis , Journal of computador eo sistema Sciences 25: 130-143, 1982.

Marzio De Biasi

n

$n$

n

$n$

2^{(\log n)^{2}}

$2^{(\log n)^2}$

Obrigado András, seu comentário está incorporado na resposta.

Mohammad Al-Turkistany

2^{ω (\log n)}

$2^{\omega(\log n)}$

n^{ω (1)}

$n^{\omega(1)}$

2^{n^{ϵ}}

$2^{n^{\epsilon}}$