Después de de nuestra extensa selección de datos solucionamos este asunto que pueden tener muchos los usuarios. Te ofrecemos la solución y esperamos resultarte de mucha apoyo.
Solución:
Supongo que está buscando definiciones intuitivas, ya que las definiciones técnicas requieren bastante tiempo para comprenderlas. En primer lugar, recordemos un concepto preliminar necesario para comprender esas definiciones.
- Problema de decisión: Un problema con un sí o no respuesta.
Ahora, definamos esos clases de complejidad.
PAG
P es una clase de complejidad que representa el conjunto de todos los problemas de decisión que se pueden resolver en tiempo polinomial.
Es decir, dada una instancia del problema, la respuesta sí o no se puede decidir en tiempo polinomial.
Ejemplo
Dado un gráfico conectado G, ¿se pueden colorear sus vértices con dos colores para que ningún borde sea monocromático?
Algoritmo: comience con un vértice arbitrario, coloréelo de rojo y todos sus vecinos de azul y continúe. Deténgase cuando se quede sin vértices o se vea obligado a hacer que un borde tenga ambos extremos del mismo color.
notario público
NP es una clase de complejidad que representa el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es “sí” tienen pruebas que se pueden verificar en tiempo polinomial.
Esto significa que si alguien nos da una instancia del problema y un certificado (a veces llamado testigo) de que la respuesta es sí, podemos verificar que sea correcto en tiempo polinomial.
Ejemplo
Factorización de enteros está en NP. Este es el problema que dados los enteros n y m, hay un entero f con 1 < f < m, tal que f divide n (f es un pequeño factor de n)?
Este es un problema de decisión porque las respuestas son sí o no. Si alguien nos da una instancia del problema (entonces nos da enteros n y m) y un entero f con 1 < f < my afirmar que f es un factor de n (el certificado), podemos comprobar la respuesta en tiempo polinomial realizando la división n / f.
NP-Completo
NP-Complete es una clase de complejidad que representa el conjunto de todos los problemas X en NP para lo cual es posible reducir cualquier otro problema de NP Y para X en tiempo polinomial.
Intuitivamente, esto significa que podemos resolver Y rapido si sabemos como solucionar X rápidamente. Precisamente, Y es reducible a X, si hay un algoritmo de tiempo polinomial f para transformar instancias y de Y a instancias x = f(y) de X en tiempo polinomial, con la propiedad de que la respuesta a y es sí, si y solo si la respuesta a f(y) Es sí.
Ejemplo
3-SAT. Este es el problema en el que se nos da una conjunción (AND) de disyunciones de 3 cláusulas (OR), declaraciones de la forma
(x_v11 OR x_v21 OR x_v31) AND
(x_v12 OR x_v22 OR x_v32) AND
... AND
(x_v1n OR x_v2n OR x_v3n)
donde cada x_vij es una variable booleana o la negación de una variable de una lista predefinida finita (x_1, x_2, ... x_n).
Se puede demostrar que cada problema de NP se puede reducir a 3-SAT. La prueba de esto es técnica y requiere el uso de la definición técnica de NP (basado en máquinas de Turing no deterministas). Esto se conoce como Teorema de Cook.
Lo que hace que los problemas NP-completos sean importantes es que si se puede encontrar un algoritmo de tiempo polinomial determinista para resolver uno de ellos, todos los problemas NP se pueden resolver en tiempo polinomial (un problema para gobernarlos a todos).
NP-duro
Intuitivamente, estos son los problemas que al menos tan difícil como los problemas NP-completos. Tenga en cuenta que los problemas NP-hard no tienes que estar en NP, y no tienen por qué ser problemas de decisión.
La definición precisa aquí es que un problema X es NP-hard, si hay un problema NP-complete Y, tal que Y es reducible a X en tiempo polinomial.
Pero dado que cualquier problema NP-completo se puede reducir a cualquier otro problema NP-completo en tiempo polinomial, todos los problemas NP-completo se pueden reducir a cualquier problema NP-difícil en tiempo polinomial. Entonces, si hay una solución para un problema NP-difícil en tiempo polinomial, existe una solución para todos los problemas NP en tiempo polinomial.
Ejemplo
El problema de la detención es un problema NP-difícil. Este es el problema que dado un programa P y entrada I, ¿se detendrá? Este es un problema de decisión pero no está en NP. Está claro que cualquier problema de NP-completo se puede reducir a este. Como otro ejemplo, cualquier problema NP-completo es NP-difícil.
Mi problema NP-completo favorito es el problema del Buscaminas.
P = NP
Éste es el problema más famoso de la informática y una de las cuestiones pendientes más importantes de las ciencias matemáticas. De hecho, el Clay Institute está ofreciendo un millón de dólares para una solución al problema (el artículo de Stephen Cook en el sitio web de Clay es bastante bueno).
Está claro que P es un subconjunto de NP. La pregunta abierta es si los problemas de NP tienen o no soluciones de tiempo polinomiales deterministas. En gran parte se cree que no es así. Aquí hay un artículo reciente sobresaliente sobre lo último (y la importancia) del problema P = NP: El estado del problema P versus NP.
El mejor libro sobre el tema es Computadoras e intratabilidad por Garey y Johnson.
He estado mirando a mi alrededor y he visto muchas explicaciones largas. Aquí hay un pequeño cuadro que puede ser útil para resumir:
Observe cómo aumenta la dificultad de arriba a abajo: cualquier NP se puede reducir a NP-Completey cualquier NP-Complete se puede reducir a NP-Hard, todo en tiempo P (polinomio).
Si puede resolver una clase de problema más difícil en el tiempo P, eso significará que encontró cómo resolver todos los problemas más fáciles en el tiempo P (por ejemplo, demostrando P = NP, si averigua cómo resolver cualquier problema NP-Completo en Tiempo P).
____________________________________________________________ | Problem Type | Verifiable in P time | Solvable in P time | Increasing Difficulty ___________________________________________________________| | | P | Yes | Yes | | | NP | Yes | Yes or No * | | | NP-Complete | Yes | Unknown | | | NP-Hard | Yes or No ** | Unknown *** | | ____________________________________________________________ V
Notas sobre Yes o No entradas:
- * Un problema NP que también es P se puede resolver en P tiempo.
- ** Un problema NP-Hard que también es NP-Complete es verificable en tiempo P.
- *** Los problemas NP-Complete (todos los cuales forman un subconjunto de NP-hard) podrían ser. El resto de NP duro no lo es.
También encontré este diagrama bastante útil para ver cómo todos estos tipos se corresponden entre sí (preste más atención a la mitad izquierda del diagrama).
Esta es una respuesta muy informal a la pregunta formulada.
¿Se puede escribir 3233 como el producto de otros dos números mayores que 1? ¿Hay alguna forma de caminar por un sendero alrededor de los Siete Puentes de Königsberg sin tomar ningún puente dos veces? Estos son ejemplos de preguntas que comparten un rasgo común. Puede que no sea obvio cómo determinar eficientemente la respuesta, pero si la respuesta es 'sí', entonces hay una prueba breve y rápida de verificar. En el primer caso, una factorización no trivial de 51; en el segundo, una ruta para caminar por los puentes (ajustando las limitaciones).
A problema de decisión es una colección de preguntas con respuestas de sí o no que varían solo en un parámetro. Di que el problema COMPOSITE = "es n compuesto": n es un número entero o EULERPATH = "¿El gráfico G ¿Tienes un camino de Euler? ": G es un gráfico finito.
Ahora bien, algunos problemas de decisión se prestan a algoritmos eficientes, si no obvios. Euler descubrió un algoritmo eficiente para problemas como los "Siete puentes de Königsberg" hace más de 250 años.
Por otro lado, para muchos problemas de decisión, no es obvio cómo obtener la respuesta, pero si conoce alguna información adicional, es obvio cómo demostrar que tiene la respuesta correcta. COMPOSITE es así: la división de prueba es el algoritmo obvio, y es lento: para factorizar un número de 10 dígitos, debes probar algo así como 100.000 divisores posibles. Pero si, por ejemplo, alguien le dijo que 61 es un divisor de 3233, la división larga simple es una forma eficiente de ver que son correctos.
La clase de complejidad notario público es la clase de problemas de decisión en los que las respuestas "sí" tienen pruebas breves y rápidas para comprobar. Como COMPUESTO. Un punto importante es que esta definición no dice nada sobre la gravedad del problema. Si tiene una forma correcta y eficiente de resolver un problema de decisión, simplemente escribir los pasos en la solución es prueba suficiente.
La investigación de algoritmos continúa y continuamente se crean nuevos algoritmos inteligentes. Un problema que quizás no sepa cómo resolver de manera eficiente hoy puede resultar en una solución eficiente (si no obvia) mañana. De hecho, los investigadores tardaron hasta 2002 en encontrar una solución eficaz para COMPOSITE. Con todos estos avances, uno realmente tiene que preguntarse: ¿Es esto de tener pruebas cortas solo una ilusión? Quizás cada ¿Problema de decisión que se presta a pruebas eficientes tiene una solución eficiente? Nadie lo sabe.
Quizás la mayor contribución a este campo vino con el descubrimiento de una clase peculiar de problemas de NP. Al jugar con modelos de circuitos para la computación, Stephen Cook encontró un problema de decisión de la variedad NP que era probablemente tan difícil o más difícil que cada otro problema NP. Se podría utilizar una solución eficiente para el problema de satisfacibilidad booleana para crear una solución eficiente para cualquier otro problema en NP. Poco después, Richard Karp demostró que otros problemas de decisión podrían tener el mismo propósito. Estos problemas, en cierto sentido los problemas "más difíciles" en NP, se conocieron como NP-completo problemas.
Por supuesto, NP es solo una clase de problemas de decisión. Muchos problemas no se expresan naturalmente de esta manera: "encuentre los factores de N", "encuentre la ruta más corta en el gráfico G que visita cada vértice", "proporcione un conjunto de asignaciones de variables que generen la siguiente expresión booleana true". Aunque uno puede hablar informalmente de que algunos de estos problemas están" en NP ", técnicamente eso no tiene mucho sentido, no son problemas de decisión. Algunos de estos problemas pueden incluso tener el mismo tipo de poder que un NP- problema completo: una solución eficiente a estos problemas (sin decisión) conduciría directamente a una solución eficiente a cualquier problema de NP. Un problema como este se llama NP-duro.
Nos puedes reafirmar nuestra ocupación exponiendo un comentario y dejando una valoración te lo agradecemos.