Recuerde que P [math] \ subseteq [/ math] NP. Tenga en cuenta que, por razones pragmáticas, supongo que P! = NP, por lo tanto, debe mirar la imagen que vinculé a continuación para obtener la imagen completa si desea si P = NP. Si no hace esta distinción, creo que la respuesta de Dave Buchfuhrer a ¿Cuáles son algunos problemas de NP que no son NP-hard? esto cubre bien esa base.
Fuente: NP-hardness – Wikipedia
- ¿Qué precauciones podemos tomar para limitar el poder de la inteligencia artificial?
- ¿Las computadoras cuánticas son realmente reales ahora? ¿Cuándo lo usarán para calcular el significado de la vida? ¿Cuándo resolverá las otras preguntas filosóficas?
- ¿Necesitas ser bueno en matemáticas para crear el próximo Spotify, Facebook o Dropbox?
- ¿Es seguro que mi dispositivo de almacenamiento externo se expulse después de apagar mi PC?
- ¿Cuál es un escenario de la vida real en el que [matemática] e ^ x [/ matemática] podría usarse?
Claro, así es como puede mostrar que la variante de decisión del problema del Árbol de expansión mínimo está en NP. Suponiendo que P! = NP, entonces este es un problema que no es NP-hard.
Expresaré el problema MST de la siguiente manera:
Dado un gráfico conectado [matemática] G [/ matemática], ¿existe un árbol de expansión mínimo con un peso total como máximo [matemática] k [/ matemática]?
Sabemos cómo resolver este problema en tiempo polinómico (el problema de optimización y la versión de decisión de este problema), por lo tanto, se encuentra en P. No es NP-hard.
Demostremos que está en NP dada una posible solución al problema. A continuación se explica cómo puede verificar si es una respuesta SÍ / NO en tiempo polinómico.
- Primero verifique que el gráfico proporcionado es un árbol de expansión. Si no es un árbol de expansión, rechace y diga NO. No es difícil ver cómo puedes comprobar esto.
- Verifique la suma de los pesos en el árbol de expansión, si excede [math] k [/ math], luego diga NO.
Si ninguno de los pasos anteriores devuelve NO, entonces debe ser una instancia SÍ.
Muchos de los problemas de optimización solucionable de tiempo polinómico que generalmente encuentra en los cursos de pregrado son problemas de NP que satisfacen lo que está buscando bajo los supuestos que he hecho. Cosas como el problema del camino más corto, el problema del flujo máximo, entre muchos otros.
