¿Puedo vincular la cardinalidad de un conjunto si se sabe que la prueba de pertenencia a este es NP-completa?

Me gustaría tener un límite en la cardinalidad del conjunto de gráficos de unidades de disco con vértices. Se sabe que verificar si un gráfico es miembro de este conjunto es NP-hard. ¿Esto conduce a un límite inferior en la cardinalidad, suponiendo P NP? $N$ $\neq$

Por ejemplo, suponga que hay un orden en todos los gráficos con vértices. ¿La dureza NP implicaría entonces que la cardinalidad excede los , de lo contrario podría probar la membresía en tiempo polinómico haciendo una búsqueda binaria a través del conjunto? Creo que esto supondría que de alguna manera ha almacenado el conjunto en la memoria ... ¿Está permitido? $N$ $2^N$

Definición: Un gráfico es un gráfico de unidad de disco si cada vértice se puede asociar con una unidad de disco en el plano, de modo que los vértices se conectan cada vez que sus discos se cruzan.

Aquí hay una referencia sobre la dureza NP de las pruebas de membresía para gráficos de unidades de disco: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
fuente

Me pregunto, ¿hay algún ejemplo en el que esta técnica proporcione el límite inferior más conocido en el tamaño de algún conjunto? Esa sería una buena aplicación combinatoria indirecta de la teoría de la complejidad.

Sasho Nikolov

Gracias por su amable asistencia. Ambas respuestas fueron útiles y perspicaces; Hubiera aceptado cualquiera de ellos en ausencia del otro.

David Choi

Respuestas:

No estoy seguro de si está haciendo esta pregunta para la técnica o la respuesta, pero hay un artículo reciente de McDiarmid y Mueller donde muestran el número de gráficos de unidad de disco (etiquetados) en vértices es ; verhttp://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf. $n$ $2^{(2 + o(1))n}$

Bart Jansen
fuente

El teorema de Mahaney establece que existen conjuntos escasos de NP completos si P = NP. Por lo tanto, suponiendo que implica un límite inferior súper polinomial en el número de instancias de tamaño en conjuntos completos de , para infinitamente . Es decir, si , entonces cualquier conjunto -Complete debe tener algún tal que para infinitamente muchos enteros $P \neq NP$ $n$ $NP$ $n$ $P \neq NP$ $NP$ $\epsilon \gt 0$ $n\ge 0$ , el conjunto contenga al menos cadenas de longitud . $2^{n^{\epsilon}}$ $n$

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

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

[2] Eric Allender, Informe de estado sobre la pregunta P versus NP, Avances en computadoras, Volumen 77, 2009, Páginas 117-147

Mohammad Al-Turkistany
fuente

[Mah82] SR Mahaney. Conjuntos completos escasos para NP: solución de una conjetura de Berman y Hartmanis , Journal of Computer and System Sciences 25: 130-143, 1982.

Marzio De Biasi

n

$n$

n

$n$

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

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

Gracias András, tu comentario está incorporado en la respuesta.

Mohammad Al-Turkistany

2^{ω (\log n)}

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

n^{ω (1)}

$n^{\omega(1)}$

2^{n^{ϵ}}

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