thumb|260px|Diagrama de clases de complexidá pal casu en que P ≠ NP. La esistencia de problemes fuera tanto de P como de NP-completos, foi determinada por Richard E. Ladner.R. Y. Ladner "On the structure of polynomial time reducibility," Journal ACM, 22, páxs. 151–171, 1975, Corollary 1.1, sitiu web de ACM.
La rellación ente les clases de complexidá P y NP ye una entruga que la teoría de la complexidá computacional entá nun pudo responder. N'esencia, la entruga ¿ye P = NP ? significa: si ye posible "verificar" rápido soluciones positives a un problema del tipu SI/NON (onde "rápido" significa "en tiempu polinómico"), ¿ye qu'entós tamién se pueden "llograr" les respuestes rápido?
Los recursos comúnmente estudiaos en complexidá computacional son:
– El tiempu: por aciu un aproximamientu al númberu de pasos d'execución qu'un algoritmu emplega pa resolver un problema.
– L'espaciu: por aciu un aproximamientu a la cantidá de memoria utilizada pa resolver el problema.
Los problemes clasificar en conxuntos o clases de complexidá (L, NL, P, PCompleto, NP, NP-Completu, NP Duru...). Esti artículu va centrar nes clases P y NP.
Considérase'l problema más importante nesti campu, el Clay Mathematics Institute ufiertó un premiu d'un millón de dólares d'Estaos Xuníos para quien desenvuelva la primer demostración correuta.
Exemplu
Consideremos, por casu, el Problema de la suma de subconxuntos, que ye un exemplu d'un problema fácil de verificar, pero que la so respuesta se cree (pero nun foi demostráu) ye malo de calcular/topar. Dau un conxuntu de númberos enteros, ¿Esiste un subconxuntu non vacíu d'ellos onde la suma de los sos elementos ye igual a 0? por casu, ¿Esiste un subconxuntu del conxuntu {−2, −3, 15, 14, 7, −10} tal que la suma de los sos elementos seya 0? La respuesta ye SI, magar puede llevar dalgún tiempu atopar un subconxuntu que satisfai'l requerimientu, según cual sía'l tamañu del conxuntu y subconxuntu. Per otra parte, si daquién afirma que la respuesta ye: «sí, porque la suma de {−2, −3, −10, 15} ye igual a cero», entós podemos comprobar en forma bien rápida y por aciu unes poques cuentes. Verificar que la suma del subconxuntu ye cero ye un procesu muncho más rápido qu'atopar el subconxuntu. La información necesaria pa verificar un resultáu positiva/afirmativu ye llamada un certificáu. Polo que podemos concluyir que dau los certificaos apropiaos, ye posible verificar rápido les respuestes afirmatives del nuesu problema (en tiempu polinomial) y ye ésta la razón pola que'l problema atópase en NP. Una respuesta a la entruga P = NP sería determinar si en problemes del tipu SUMA-SUBCONXUNTU ye tan fácil topar la solución como verificala. Si s'atopa que P nun ye igual a NP, ello significa que dellos problemes NP seríen significativamente más difíciles de topar la so solución que verificar la mesma. La respuesta sería aplicable a tou esti tipu de problemes, non solo al exemplu específicu de SUMA-SUBCONXUNTU.
La restricción a problemes de tipu SI/NON realmente nun ye importante; entá si déxense respuestes más complicaes, el problema resultante resulta equivalente (esto ye si FP = FNP).como esta por casu (m×q)×(n×p) esta de aqui si ye colos sos valores m=-2 n=5 p=-7 q=-10
Contestu del problema
La rellación ente les clases de complexidá P y NP ye estudiada pola teoría de la complexidá computacional, la parte de la teoría de la computación que trata de los recursos riquíos mientres el cálculu pa resolver un problema dau. Los recursos más avezaos son tiempu (¿cuántos pasos son necesarios pa resolver un problema?) y espaciu (¿cuánta memoria ye necesaria pa resolver un problema?).
Nesti tipu d'analís, ríquese un modelu del ordenador pa la que desea estudiar el requerimientu en términos de tiempu. Típicamente, dichos modelos suponen que l'ordenador ye determinista (dau l'estáu actual del ordenador y les variables d'entrada, esiste una única aición posible que l'ordenador puede tomar) y secuencial (realiza les aiciones una dempués de la otra). Estos camientos son afeches pa representar el comportamientu de tolos ordenadores esistentes, entá inclúi a les máquines con computación en paralelu.
Nesta teoría, la clase P consiste de toos aquellos problemes de decisión que pueden ser resueltos nuna máquina determinista secuencial nun periodu de tiempu polinomial en proporción a los datos d'entrada. Na teoría de complexidá computacional, la clase P ye una de les más importantes; la clase NP consiste de toos aquellos problemes de decisión que les sos soluciones positives/afirmatives pueden ser verificaes en tiempu polinómico a partir de ser alimentaes cola información apropiada, o en forma equivalente, que la so solución puede ser topada en tiempu polinómico nuna máquina non determinista. Poro, la principal entruga entá ensin respuesta na teoría de la computación ta referida a la rellación ente estos dos clases:
¿Ye P igual a NP?
Nuna encuesta realizada nel 2002 ente 100 investigadores, 61 creíen que la respuesta yera NON, 9 creíen que la respuesta yera SI, 22 nun taben seguros, y 8 creíen que la entruga podía ser independiente de los axomes anguaño aceptaos, y polo tanto imposible de demostrar pol SI o pol NON.
Definiciones formales
Más precisamente, un problema de decisión ye un problema qu'especifica una cadena de calteres de datos d'entrada y requier como solución una respuesta pol SI o pol NON. Si esiste un algoritmu (por casu una máquina de Turing, o un programa en llinguaxes Lisp o Pascal con memoria irrestricta) que ye capaz d'apurrir la respuesta correuta pa toa cadena de datos de llargor n n'a lo sumo pasos, onde k y c son constantes independientes del conxuntu de datos, entós dizse que'l problema puede ser resueltu en tiempu polinómico y clasificar como perteneciente a la clase P. En forma intuitiva, consideramos que los problemes conteníos en P son aquellos que pueden ser resueltos en forma razonablemente rápida.
P suel ser la clase de problemes computacionales que son “eficientemente resolubles” o “tratables”, anque haya clases potencialmente más grandes que tamién se consideren tratables, como RP Y BPP. Anque tamién esisten problemes en P que nun son tratables en términos práuticos; por casu, unos requiern siquier operaciones.
En forma intuitiva, puede pensase que NP ye un problema de decisión que ye malo de resolver si nun se tener nengún otru datu o información adicional. Sicasí, si recibe la información adicional llamada un certificáu, entós el problema puede ser resueltu fácilmente. Por casu, si dásenos el númberu 323 y preguntar si 323 ye un númberu factorizable, ensin danos nengún datu o información adicional, tendríamos d'analizar tolos númberos enteros positivos mayores que 2 pero menores que 323 pa estudiar si dalgunu d'ellos estrema esautamente al 323. Sicasí, si dásenos el númberu 17, podemos estremar 323 por 17 y rápido verificar que 323 ye factorizable. El númberu 17 ye llamáu un certificáu. El procesu de división pa verificar que 323 ye factorizable ye n'esencia una máquina Turing y nesti casu ye denomináu'l verificador pa 323. Téunicamente dizse que'l problema ye bon si puede resolvese en tiempu polinómico y que ye mal si resuélvese en tiempu esponencial. Formalmente, defínese NP como un conxuntu de llinguaxes que satisfaen ciertes condiciones.
Sía L un llinguaxe definíu sobre un alfabetu finito, .
Si esiste una rellación binaria y un enteru positivu tal que pa tou , satisfáense les siguientes condiciones:
tal que y (O simboliza cota cimera asintótica). El llinguaxe = en ye decidible por una máquina de Turing en tiempu polinomial.
Entós, la máquina de Turing que decide (que la llamaremos ) ye llamada'l Verificador pa y ye llamáu'l Certificáu de membresía de en .
Finalmente, atópase en NP "si y solu si" cuerre en tiempu polinómico.
Exemplu.
Sía
Claramente, la entruga de si un dadu x ye factorizable ye equivalente a la entruga sobre si x ye un miembru de COMPOSITE. Ello ye que puede demostrase fácilmente que si verifícase que COMPOSITE satisfai la condición indicada primero.
(Nota. Apocayá demostróse que COMPOSITE taba dientro de P)
La clase P
P ye conocíu por contener munchos problemes naturales, incluyendo les versiones de decisión de programa llinial, cálculu del máximu común divisor, y atopar una correspondencia máxima.
Problemes notables en P
Dellos problemes naturales son completos pa P, incluyendo la conectividad (o l'accesibilidá) en grafos non empobinaos.
Una xeneralización de P ye NP, que ye la clase de llinguaxes decidibles en tiempu polinómico sobre una máquina de Turing non determinista. De forma trivial, tenemos que P ye un subconxuntu de NP. Anque nun ta demostráu, la mayor parte de los espertos creen qu'esto ye un subconxuntu estrictu.
Equí, EXPTIME ye la clase de problemes resolubles en tiempu esponencial. De toles clases amosaes enriba, namái se conocen dos contenciones estrictes:
P puramente ta conteníu en EXPTIME. L puramente ta contenida en PSPACE.
Los problemes más difíciles en P son los problemes P-completos
Otra xeneralización de P ye'l Tiempu polinómico Non uniforme (P/Poly). Si un problema ta en P/poly, entós puede solucionase nun tiempu polinomial determináu'l cual, dau una cadena, esti solu depende del llargor de la entrada. A diferencia de NP, nun se comprueben les cadenes defectuoses qu'entren na máquina de Turing, yá que nun ye un verificador.
P/poly ye una clase grande que contién cuasi tolos algoritmos práuticos, incluyendo tol BPP. Si esta contién a NP, la xerarquía polinomial colapsar col segundu nivel. Per otra parte, esta tamién contién dellos algoritmos pocu práuticos, incluyendo dellos problemes non decidibles.
Propiedaes
Los algoritmos de tiempu polinómico son cerraos al respective de la composición. Intuitivamente, esto quier dicir que si unu escribe una función con un determináu tiempu polinómico y consideramos que les llamaes a esa mesma función son constantes y, de tiempu polinómico, entós l'algoritmu completu ye de tiempu polinómico. Esto ye unu de los motivos principales polos que P considérase una máquina independiente; delles traces d'esta máquina, como l'accesu aleatoriu, ye que puede calcular en tiempu polinómico el tiempu polinómico del algoritmu principal amenorgándolo a una máquina más básica.
Les pruebes esistenciales d'algoritmos de tiempu polinómico
Conozse que dellos problemes son resolubles en tiempu polinómico, pero nun se conoz nengún algoritmu concretu pa solucionalos. Por casu, el teorema Robertson-Seymour garantiza qu'hai una llista finita de los menores dexaos que compón (por casu) el conxuntu de los grafos que pueden ser integraos sobre un toroide; amás, Robertson y Seymour demostraron qu'hai una complexidá O (n³) nel algoritmu pa determinar si un grafo tien un grafo incluyíu. Esto danos una prueba non constructiva de qu'hai un algoritmu de tiempu polinómico pa determinar si dau un grafo puede ser integráu sobre un toroide, a pesar de nun conocese nengún algoritmu concretu pa esti problema.
Exemplos
Camín Mínimu: atopar el camín mínimu dende un vértiz orixe al restu de los vértices.
Ciclu Euleriano: Atopar un ciclu que pase per cada arcu d'un grafo una única vegada.
La clase NP
La clase NP ta compuesta polos problemes que tienen un certificáu sucinto (tamién llamáu testigu polinómico) para toles instancies que la so respuesta ye un SÍ. La única forma de que tengan un tiempu polinomial ye realizando una etapa aleatoria, incluyendo l'azar de dalguna manera pa escoyer una posible solución, y entós n'etapes posteriores comprueba si esa solución ye correuta.
N'otres pallabres, dada una solución pa una cierta instancia, ye posible comprobar que ye válida en TIME (n^k). Nel casu de SAT (Problema de satisfacibilidad booleana), dau una asignación de valores de verdá, puede comprobase fácilmente si la fórmula ye cierta o non. Una nMT puede "aldovinar" la solución n'O (n) y verificala en tiempu polinómico.
Completitud de NP