¿Es el número de problemas de NP-completos finitos?

Question

Debe ser directo para demostrar que hay infinitos problemas de NP:

Prueba: Tome el problema Eliminar 1 vértice 3-col ( $ r1v3col $ ) que realiza un gráfico $ G= (v, e) $ como una instancia y produce una respuesta de sí, un vértice $ x \ in v $ existe que, cuando se retira de < Span Class="Math-contenedor"> $ v $ produce un nuevo gráfico $ g '= (v \ backslash \ {x \}, \ {(u, v ) \ in e \, | \, U \ NEQ X \ Land V \ NEQ X \ \ \ \ span> es una instancia positiva de $ 3col $ .

$ r1v3col $ se puede reducir al problema de 3 capacidad de capacidad (que se ha comprobado que se ha completado) por (como una reducción de ejemplo) simplemente eliminando un vértice Desde $ g $ y pruebas si $ g $ es 3-colorable. Si $ G $ no es 3-colorable Elimine otro vértice de $ g $ y pruebe. Repita hasta que no queden vértices para pruebas.

Por lo tanto, sabemos $ r1v3col $ es un problema de NP-DURS.

Ahora podemos reducir $ r2v3col $ a un $ r1v3col $ problema (por un concepto similar como Se muestra arriba para $ r1v3col $ a $ 3col $ para mostrar que $ R2v3col $ está en NP-HARD y, por lo tanto, para cada problema de eliminar los vértices 3-col . En otras palabras, siempre podemos reducir siempre $ R (n) v3col $ a $ r (n-1) v3col $ . Por lo tanto, sabemos que hay que haber infinitamente muchos problemas de NP-DURS y estamos terminados.

ahora a mi lemma: No puedo pensar en una prueba simple para demostrar que un determinado problema con infinitamente muchas variaciones (como $ r (n) v3col $ ) también está en NP para probar la integridad NP y por lo tanto, demuestre que los problemas infinitos se encuentran en la subclase NP-Completa.

Answer 1

Como en el comentario, considere la colección de problemas $ n $ -sat (es $ \ phi $ , una fórmula lógica en $ n $ -cnf, satisfactoria?).O $ n $ -coloring of grafns, para $ n \ ge 3 $ (¿puede ser coloreado el gráficoCon $ n $ colores?).Muchos problemas completos de NP tienen algún parámetro (¿hay una clama de tamaño $ k $ en el gráfico? Tiene el digraph un conjunto de vértices de retroalimentación de tamaño $ K $ ?).

Answer 2

Para cada entero k, tome el problema del vendedor ambulante con N> 1 ciudades donde n es un poder de k.(Eligió el problema de esa manera porque todas las instancias son distintas, por lo que podemos decir con buena conciencia que estos son problemas distintos).