Problemas p y NP
p es un problema que se puede resolver en tiempo polinómico, y NP es un problema que puede verificar la exactitud de una respuesta dada en tiempo polinómico. Aunque la definición es complicada, P=NP en realidad pregunta:
Si se puede verificar rápidamente si la respuesta es correcta o incorrecta, ¿también se puede calcular rápidamente?
p es la primera letra de la palabra inglesa polinomio. ¿Qué tipo de problema se llama problema tipo P?
Si en un problema se puede encontrar un algoritmo que se pueda resolver en tiempo polinómico, entonces pertenece al problema tipo P.
Las preguntas de la Olimpiada de Información son todas problemas de tipo P, porque un programa de tiempo de espera no polinómico obtenido mediante el método exhaustivo no cubrirá ningún algoritmo valioso. ! ¿Cuál es el problema NP correspondiente?
Para una solución a un problema, la corrección de la solución se puede verificar en tiempo polinomial.
Un ejemplo:
Alguien recibió una pregunta sobre cómo encontrar el camino más corto, preguntando si hay un camino con una longitud inferior a 100 unidades desde el punto inicial hasta el punto final. Dibujó un mapa basado en el conjunto de datos. En ese momento, tuvo tanta suerte que encontró un camino uno tras otro y contó 96 unidades. La respuesta a esta pregunta viene ahora dada por una prueba.
En este problema, es difícil encontrar una solución y fácil verificarla. Solo requiere complejidad de tiempo O (n). Para una ruta determinada, se puede verificar en tiempo polinómico, lo cual es un problema NP.
¿Hay algún problema que no sea NP-hard? seguro. Mientras la solución del problema no pueda verificarse en tiempo polinomial, el problema no es NP-difícil. Problema del ciclo hamiltoniano porque es muy fácil verificar si un camino pasa por cada vértice. Si el problema hamiltoniano se cambia a este: pregunte si no hay un ciclo hamiltoniano en una gráfica. No puedes responder esta pregunta a menos que hayas probado todos los caminos.
Normalmente sólo los problemas NP pueden ser problemas de tipo P. No esperamos que un algoritmo de nivel polinomial resuelva un problema que ni siquiera puede verificarse en tiempo polinomial. En este punto, se dará cuenta de que el "problema NP" en realidad está discutiendo la relación entre el problema NP y el problema P.
Preguntas y respuestas:
¿NP significa no polinomio? (NP significa no polinomio)
Polinomio no determinista (polinomio no determinista, si es un polinomio determinista, se convierte en un problema P)
Zhihu-Quantum Communication- Dirección de referencia
Entrada de blog de referencia sobre cuestiones de P y n P