Ver la fonte de Clases de complexidá P y NP

{{wikificar|t=20140111185624}}
[[Ficheru:Complexity classes es.svg|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.<ref>R. Y. Ladner "On the structure of polynomial time reducibility," Journal ACM, 22, páxs. 151–171, 1975, Corollary 1.1, [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 sitio web de ACM].</ref>]]

La rellación ente les '''[[clase de complejidad|clases de complexidá]] [[Tiempu polinómico|P]] y [[NP (Complexidá computacional)|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.

– El '''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ólar d'Estaos Xuníos|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 [[enteru|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 [[problema de la suma de subconxuntos|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 (clase de complexidá)|FP]]''' = '''[[FNP (clase de complexidá)|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 '''[[clase de complejidad|clases de complexidá]] P y NP''' ye estudiada pola [[Complexidá computacional|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 [[Algoritmu determinista|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 [[programación paralela|computación en paralelu]]. 

Nesta teoría, la clase '''[[Tiempu polinómico|P]]''' consiste de toos aquellos [[problema de decisión|problemes de decisión]] que pueden ser resueltos nuna máquina determinista secuencial nun periodu de [[tiempu polinómico|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_(clase de complexidá)|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 [[Máquina de Turing non determinista|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.<ref name=poll>{{cita publicación|autor=William I. Gasarch |títulu=The P=?NP poll. |revista=SIGACT News |volume=33 |númberu=2 |páxines=34-47 |fecha=xunu de 2002 |url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804}}</ref>

== Definiciones formales ==

Más precisamente, un ''problema de decisión'' ye un problema qu'especifica una [[cadena de calteres]] de datos d'entrada y rique 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 [[Llinguaxe de programación Pascal|Pascal]] con memoria irrestricta) que ye capaz d'apurrir la respuesta correuta pa toa cadena de datos de llargor ''n'' n'a lo sumo <math>c \cdot n^k</math> 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 riquen siquier <math>n^{1000000}</math> 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, <math>\Sigma</math>.

Si esiste una rellación binaria <math>R\subset\Sigma^{*}\times\Sigma^{*}</math> y un enteru positivu <math>k</math> tal que pa tou <math>x\in\Sigma^{*}</math>, satisfáense les siguientes condiciones:

# <math>x\in L \Leftrightarrow\exists y\in\Sigma^{*}</math> tal que <math>(x,y)\in R\;</math> y <math>\left|y\right|\in\;O(\left|x\right|^{k})</math> (O simboliza [[cota cimera asintótica]]).
# El llinguaxe <math>L_{R}</math>=<math>\{ x\# y:(x,y)\in R\}</math> en <math>\Sigma\cup\{\#\}</math> ye decidible por una máquina de Turing en tiempu polinomial.

Entós, la máquina de Turing que decide <math>L_{R}</math> (que la llamaremos <math>V</math>) ye llamada'l Verificador pa <math>L</math> y <math>y</math> ye llamáu'l Certificáu de membresía de <math>x </math> en <math>L</math>.

Finalmente, <math>L</math> atópase en '''NP''' "si y solu si" <math>V</math> cuerre en tiempu polinómico.

'''Exemplu'''. 

Sía 

:<math>\mathrm{COMPOSITE}</math> = <math>\{x\in \N : x=pq \;\text{pa enteros}\; p, q > 1 \}</math>
:<math>R</math> = <math>\{(x,y)\in \N\times \N: 1<y<x\; ; \;y\; \text{estrema a}\; x\}</math>

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 <math>\mathrm{COMPOSITE}\in\mathbf{NP}</math> si verifícase que COMPOSITE satisfai la condición indicada primeramente.

('''Nota'''. Apocayá demostróse que COMPOSITE taba dientro de '''P'''<ref name=Agrawal>{{Cita web |autor= M. Agrawal, N. Kayal, N. Saxena |títulu=Primes is in P |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf}}</ref>)

== 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)[//en.wikipedia.org/wiki/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'''

'''[[Algoritmu de Dijkstra|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'''

P'analizar la entruga '''P''' = '''NP''', resulta bien útil el conceutu de [[NP-completu|completitud '''NP''']]. De manera informal, los problemes de completitud '''NP''' son los problemes más "difíciles" en '''NP''' nel sentíu de qu'ellos son los que son más probable nun s'atopen en '''P'''. Problemes [[NP-hard|'''NP'''-difíciles]] son aquellos pa los cualos ''cualesquier'' problema en '''NP''' puede ser amenorgáu en tiempu polinómico. Los problemes de completitud '''NP''' son aquellos problemes '''NP'''-difícil que s'atopen en '''NP'''. Por casu, la versión de problema de decisión del [[problema del vendedor viaxeru]] ye dafechu '''NP'''. Asina nengún casu de nengún problema en '''NP''' puede ser tresformáu mecánicamente nuna parte del problema del vendedor viaxeru, en tiempu polinómico. Poro, si'l problema del vendedor viaxeru tuviera conteníu en '''P''', entós '''P ''' = '''NP'''. El problema del vendedor viaxeru ye unu de munchos problemes '''NP'''-completos. Si cualquier problema '''NP'''-completu atópase conteníu en '''P''', entós verificaríase que '''P''' = '''NP'''. Desafortunadamente, demostróse que munchos problemes importantes son '''NP'''-completos y nun se conoz la esistencia de nengún algoritmu rápidu pa ellos.
<!--
Ye relativamente resalvo que la clase NP-completu nun ye vacida porque ye posible formular un problema de decisión llamáu DUH que ye trivial NP y difícil-NP: dada la descripción d'una máquina de Turing M garantizada que se va detener en tiempu polinómico, DUH correspuende a la entruga de si esiste un conxuntu de datos de dimensión polinómica que M va aceptar.<ref name=scott>{{Cita web |autor=Scott Aaronson |títulu=PHYS771 Lecture 6: P, NP, and Friends |url=http://www.scottaaronson.com/democritus/lec6.html |fechaaccesu=27 d'agostu de 2007}}</ref> Sicasí, yá que DUH is contrived y d'interés eminentemente teóricu, foi realmente un gran descubrimientu atopar que numberosos problemes esistentes bien práuticos yeren tamién NP-completos.

El primer problema natural que se demostró que ye NP-completu foi'l [[Boolean satisfiability problem]]. Esta resultancia foi demostráu por [[Stephen Cook]] en 1971, y llamar el [[teorema de Cook]]. Cook's proof that satisfiability is NP-complete is very complicated. However, after this problem was proved to be NP-complete, [[reduction (complexity)|proof by reduction]] has provided a simpler way to show that many other problems are in this class. Poro, una amplia clase de problemes en principiu inconexos son reducibles unos a otros, y polo tanto resulten en "el mesmu problema" -- un resultáu fonda ya inesperáu.
-->

La definición anterior de NP dexa considerar de manera natural una clase de problemes complementaries. La [[co-NP]] ta compuesta polos problemes que tienen un contraejemplo sucinto pa toles instancies que la so respuesta ye NON. 

'''Exemplos'''

'''Camín Máximu:''' Daos dos vértices d'un grafo atopar el camín (simple) máximu.

'''[[Ciclu Hamiltoniano]]:''' Ciclu simple que contién cada vértiz del grafo.

== NP-Completu ==

Pa encetar la entruga de si P=NP, el conceutu de la [[NP-completu|completitud de NP]] ye bien útil. Informalmente, los problemes de NP-completos son los problemes más difíciles de NP, nel sentíu de que son los más probables de nun atopase en P. Los problemes de NP-completos son esos problemes NP-duros que tán conteníos en NP, onde los problemes NP-duros son estos que cualquier problema en NP puede ser amenorgáu a complexidá polinomial. Por casu, la decisión del [[Problema del viaxante]] de comerciu ye NP-completu, asina que cualquier casu de cualquier problema en NP puede ser tresformáu mecánicamente nun casu del [[Problema del viaxante]] de comerciu, de complexidá polinomial. El [[Problema del viaxante]] de comerciu ye de los munchos problemes NP-completos esistentes. Si cualquier problema NP-completu tuviera en P, entós indicaría que P=NP. Desafortunadamente, sábese que munchos problemes importantes son NP-completos y a fecha de 2008, nun se conoz nengún algoritmu rápidu pa nengún d'ellos. Basándonos solo nesta idea, nun ye obviu qu'esista un problema NP-completu. Un problema NP-completu trivial y escurríu, puede formulase como: Dada una descripción d'una [[máquina de Turing]] M que se detién en tiempu polinómico, ¿esiste una entrada de tamañu polinómico que M acepte? Ye NP porque, dada una entrada, ye simple comprobar si M acepta o non la entrada asemeyando M, ye NP-duros porque'l verificador pa cualquier casu particular d'un problema en NP puede ser codificado como una máquina M de tiempu polinomial que toma la solución pa ser verificada como entrada. Entós la entruga de si'l casu ye o non un casu, ta determináu pola esistencia d'una entrada valida. El primer problema natural que se demostró ser NP-completu foi'l Problema booleano de satisfacibilidad. Esta resultancia ye conocíu como'l [[teorema de Cook]]-Levin; la so prueba de que la satisfacibilidad ye NP-completu contién los detalles téunicos sobre máquines de Turing y como se rellacionen cola definición de NP. Sicasí, dempués demostróse que'l problema yera NP-completu, la prueba por amenorgamientu, apurrió una manera más simple de demostrar que munchos otros problemes tán nesta clase. Asina, una clase estensa de problemes aparentemente ensin rellación ye reducible a otra, y son nesti sentíu'l mesmu problema.

== Ver tamién ==
* [[Ciencies de la computación]]
* [[Teoría de la computación]]
* [[Teoría d'autómates]]
* [[Teoría de la computabilidad]]
* [[Complexidá computacional|Teoría de la complexidá computacional]]
* [[Problemes del mileniu]]

== Referencies ==
{{llistaref}}

== Bibliografía ==
* A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. ''Automata, Languages, and Programming'', Springer LNCS 115 (1981) 278-293 and ''J. Comb. Th. A'' 31 (1981) 199-214.
* Y. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames are hard, MSRI Combinatorial Game Theory Research Worksh., 2000.
* [[Neil Immerman]]. Languages Which Prinde Complexity Classes. ''15th ACM STOC Symposium'', páxs.347-354. 1983.
* {{cita llibru | autor= [[Thomas H. Cormen]], [[Charles Y. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | títulu= [[Introduction to Algorithms]] | edición= Second Edition | editorial= [[MIT Press]] and McGraw-Hill | añu= 2001 | id= ISBN 0-262-03293-7 | capítulu= Chapter 34: NP-Completeness | páxines= 966–1021 }}
* {{cita llibru | autor= [[Christos Papadimitriou]] | añu= 1993 | títulu= Computational Complexity | editorial= Addison Wesley | edición= 1st edition | id= ISBN 0-201-53082-1 | capítulu= Chapter 14: On P vs. NP | páxines= 329–356 }}
* Apuntes de clase de l'asignatura Analís y Diseñu d'Algoritmos de la Escuela Cimera de Infórmatica de Málaga

== Enllaces esternos ==
* [https://web.archive.org/web/20051126011639/http://www.claymath.org/prizeproblems/index.htm The Clay Math Institute Millennium Prize Problems] (n'inglés)
* [https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf The Clay Math Institute Official Problem Description (pdf)] (n'inglés)
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page]. A list of links to a number of purported solutions to the problem. Some of these links state that P equals NP, some of them state the opposite. It's probable that all these alleged solutions are incorrect. (n'inglés)
* [http://www.ics.uci.edu/~eppstein/cgt/hard.html Computational Complexity of Games and Puzzles]
* Scott Aaronson's Complexity Zoo: [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#p P], (n'inglés) 
* [https://web.archive.org/web/20071212164513/http://www.qeden.com/ Qeden], a wiki that aims to solve the Millennium Prize Problems (n'inglés)
* [http://scottaaronson.com/blog/?p=122 Scott Aaronson's Shtetl Optimized blogue: Reasons to believe], a list of justifications for the belief that P ≠ NP (n'inglés)





{{Tradubot|Clases de complejidad P y NP}}

{{control d'autoridaes}}
[[Categoría:Clases de complexidá]]
[[Categoría:Problemes ensin resolver de la Matemática]]
[[Categoría:Problemes ensin resolver de les Ciencies de la Computación]]
[[Categoría:Problemes del mileniu]]
[[Categoría:Wikipedia:Páxines con enllaces interllingüísticos]]