En primer lugar, NP es una clase de complejidad . Una clase de complejidad es una familia de problemas de decisión (o, de manera equivalente, idiomas); Los problemas de decisión tienen respuestas sí / no. El problema que tiene en mente es un problema de conteo cuya respuesta es un número.
Sin embargo, podemos considerar el problema de decisión relacionado
¿La red [matemática] L [/ matemática] tiene [matemática] n [/ matemática] puntos?
- ¿Cómo se usan los modelos gráficos probabilísticos en la comprensión de imágenes?
- ¿Cómo mantienen los administradores de paquetes de Linux el gráfico acíclico dirigido que forman los paquetes?
- ¿Es Linux más avanzado que Windows?
- ¿Puede explicar, en términos simples y con ejemplos, qué funciones sapply () y lappy () hacen en R?
- ¿Qué tan serios son los revisores y los presidentes de área con refutación en una conferencia de renombre?
y quizás descubra más sobre el límite de complejidad superior del problema de conteo relacionado a través de esto.
En segundo lugar, el término enrejado tiene varios significados diferentes en matemáticas.
La siguiente lista está citada de Wikipedia:
- Lattice (orden), un conjunto parcialmente ordenado con límites superiores mínimos únicos y límites inferiores mayores
- Celosía (grupo), una disposición repetitiva de puntos
- Enrejado (subgrupo discreto), un subgrupo discreto de un grupo topológico con covolumen finito
- Lattice (módulo), un módulo sobre un anillo incrustado en un espacio vectorial sobre un campo
- Gráfico de celosía, un gráfico que se puede dibujar dentro de una disposición repetitiva de puntos
- Multiplicación de celosía, un algoritmo de multiplicación adecuado para el cálculo manual.
- Celosía sesgada, una generalización no conmutativa de arreglos repetidos de puntos
No está del todo claro para mí qué estás pensando aquí. Mencionas la palabra nodos, lo que me lleva a creer que estás pensando en un gráfico reticular o en la representación gráfica de un orden parcial. En cualquier caso (suponiendo que la red es finita), puede contar el número de puntos en la red mediante, por ejemplo, la búsqueda de profundidad primero. Dado que el algoritmo habitual de búsqueda de profundidad primero tiene una complejidad de tiempo que es polinómica en el tamaño del gráfico de entrada, por supuesto, se puede contar el número de puntos en tiempo polinómico.
Si mis suposiciones en lo anterior sobre el significado de la palabra “celosía” son correctas, entonces el problema de decisión
¿La red [matemática] L [/ matemática] tiene [matemática] n [/ matemática] puntos ?
está en P.
