Puis-je limiter la cardinalité d'un ensemble si le test d'adhésion à celui-ci est connu pour être NP-complet?

Je voudrais avoir une limite sur la cardinalité de l'ensemble des graphes d'unité de disque avec sommets. Il est connu que vérifier si un graphe est membre de cet ensemble est NP-difficile. Cela conduit-il à une borne inférieure de la cardinalité, en supposant P NP? $N$ $\neq$

Par exemple, supposons qu'il existe un ordre sur tous les graphiques avec sommets. La dureté NP impliquerait-elle alors que la cardinalité dépasse , dans le cas contraire, vous pourriez tester l'appartenance au temps polynomial en faisant une recherche binaire à travers l'ensemble? Je pense que cela supposerait que vous avez en quelque sorte stocké l'ensemble en mémoire ... Est-ce autorisé? $N$ $2^N$

Définition: Un graphe est un graphe de disque unitaire si chaque sommet peut être associé à un disque unitaire dans le plan, de telle sorte que les sommets sont connectés chaque fois que leurs disques se croisent.

Voici une référence sur la dureté NP des tests d'appartenance pour les graphiques de disques unitaires: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
la source

Je me demande, y a-t-il un exemple où cette technique fournit la borne inférieure la plus connue sur la taille d'un ensemble? Ce serait une application combinatoire indirecte cool de la théorie de la complexité.

Sasho Nikolov

Merci beaucoup pour votre aide précieuse. Les deux réponses étaient utiles et perspicaces; J'aurais accepté l'un ou l'autre en l'absence de l'autre.

David Choi

Réponses:

Je ne sais pas si vous posez cette question pour la technique ou pour la réponse, mais il y a un article récent de McDiarmid et Mueller où ils montrent que le nombre de graphes d'unité de disque (étiquetés) sur sommets est de ; voir http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf . $n$ $2^{(2 + o(1))n}$

Bart Jansen
la source

Le théorème de Mahaney déclare qu'il existe des ensembles clairsemés NP-complets si P = NP. Par conséquent, en supposant que implique une borne inférieure super-polynomiale sur le nombre d'instances de taille dans des ensembles complets , pour une infinité de . Autrement dit, si , alors tout ensemble complet doit avoir un tel que pour un nombre infini d'entiers , l'ensemble contient au moins cordes de longueur . $P \neq NP$ $n$ $NP$ $n$ $P \neq NP$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

H. Buhrman et JM Hitchcock ont prouvé que la borne inférieure ( ) est serrée, à moins que la hiérarchie polynomiale ne s'effondre. $2^{n^{\epsilon}}$

[1] H. Buhrman et JM Hitchcock, Les ensembles NP-durs sont exponentiellement denses sauf si coNP ⊆ NP / poly, dans IEEE Conference on Computational Complexity, pages 1–7, 2008

[2] Eric Allender, Un rapport d'étape sur la question P contre NP, Advances in Computers, Volume 77, 2009, Pages 117-147

Mohammad Al-Turkistany
la source

[Mah82] SR Mahaney. Ensembles complets clairsemés pour NP: Solution d'une conjecture par Berman et Hartmanis , Journal of Computer and System Sciences 25: 130-143, 1982.

Marzio De Biasi

Chaque ensemble NP-complet a une cardinalité infiniment innombrable. Vous vouliez probablement dire que P ≠ NP implique une borne inférieure super-polynomiale sur le nombre d'instances de taille

, pour une infinité de

. Notez également que

est super polynomial sans être de la forme que vous donnez.

n

$n$

n

$n$

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

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

András Salamon

Merci András, votre commentaire est intégré dans la réponse.

Mohammad Al-Turkistany

@Mohammad: faites la borne inférieure

, ou

: c'est ce que signifie superpolynomial.

2^{ω (\log n)}

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

n^{ω (1)}

$n^{\omega(1)}$

Sasho Nikolov

2^{n^{ϵ}}

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