Classes de complexitat P i NP

La relació entre les classes de complexitat NP i P és una pregunta per primera volta formulada pel científic computacional Stephen Cook que la teoria de la complexitat computacional encara no ha pogut respondre. En essència, la pregunta <<¿és P = NP complet?>> significa: <<Si és possible "verificar" ràpidament les solucions d'un problema (és dir, és un problema de tipo NP), ¿això implica que també és possible "obtindre" les respostes en la mateixa rapidea? (és dir, és un problema de tipo P)>>, a on "ràpidament" significa "en temps polinòmic".

Els recursos comunament estudiats en complexitat computacional són:

– El temps: per mig d'una aproximació al número de passos d'eixecució que un algoritme ampra per a resoldre un problema.

– El espai: per mig d'una aproximació a la cantitat de memòria utilisada per a resoldre el problema.

Els problemes es classifiquen en conjunts o classes de complexitat (L, NL, P, PCompleto, NP, NP-Complet, NP Dur...). Este artícul se centrarà en les classes P i NP.

Es considera el problema més important en este camp, el Clay Mathematics Institute ha oferit un premi d'un milló de dólars nortamericans para qui desenrolle la primera demostració correcta.

Eixemple

Considerem, per eixemple, el problema de la suma de subconjunts, que és un eixemple d'un problema fàcil de verificar, pero la resposta del qual es «creu» (pero no ha segut demostrat) és difícil de calcular/trobar. Donat un conjunt de números sancers, ¿existix un subconjunt no buit d'ells a on la suma dels seus elements és igual a 0? per eixemple, ¿Existix un subconjunt del conjunt {−2, −3, 15, 14, 7, −10} tal que la suma dels seus elements siga 0? La resposta és SÍ, si be pot dur algun temps trobar un subconjunt que satisfà el requeriment, segons com siga el tamany del conjunt i subconjunt. Per una atra part, si algú afirma que la resposta és: «sí, perque la suma de {−2, −3, −10, 15} és igual a zero», llavors ho podem comprovar en forma molt ràpida i per mig d'uns pocs contes. Verificar que la suma del subconjunt és zero és un procés molt més ràpit que trobar el subconjunt. L'informació necessària per a verificar un resultat positiu/afirmatiu és cridada un «certificat». Per lo que podem concloure que donat els certificats apropiats, és possible verificar ràpidament les respostes afirmatives del nostre problema (en temps polinomial) i és esta la raó per la que el problema es troba en NP. Una resposta a la pregunta P = NP seria determinar si en problemes del tipo SUMA-SUBCONJUNT és tan fàcil trobar la solució com verificar-la. Si es troba que P no és igual a NP, això significa que alguns problemes NP serien significativament més difícils de trobar la seua solució que verificar la mateixa. La resposta seria aplicable a tot este tipo de problemes, no solament a l'eixemple específic de SUMA-SUBCONJUNT.

La restricció a problemes de tipo SÍ/NO realment no és important; encara si es permeten respostes més complicades, el problema resultant resulta equivalent (o siga si FNP = FP).

Context del problema

La relació entre les classes de complexitat P i NP és estudiada per la teoria de la complexitat computacional, la part de la teoria de la computació que tracta dels recursos requerits durant el càlcul per a resoldre un problema donat. Els recursos més usuals són temps (¿quants passos són necessaris per a resoldre un problema?) i espai (¿quanta memòria és necessària per a resoldre un problema?).

En este tipo d'anàlisis, es requerix un model de la computadora per a la que desija estudiar el requeriment en térmens de temps. Típicament, dits models suponen que la computadora és determinista (donat l'estat actual de la computadora i les variables d'entrada, existix una única acció possible que la computadora pot prendre) i seqüencial (realisa les accions una despuix de l'atra). Estes suposicions són adequades per a representar el comportament de totes les computadores existents, encara inclou a les màquines en computació en paralel.

En esta teoria, la classe P consistix de tots aquells problemes de decisió que poden ser resolts en una màquina determinista seqüencial en un periodo de temps polinomial en funció a les senyes d'entrada. En la teoria de complexitat computacional, la classe P és una de les més importants; la classe NP consistix de tots aquells problemes de decisió les solucions positives de la qual/afirmatives poden ser verificades en temps polinòmic a partir de ser alimentades en l'informació apropiada, o en forma equivalent, la solució de la qual pot ser trobada en temps polinòmic en una màquina no determinista. Per lo tant, la principal pregunta encara sense resposta en la teoria de la computació està referida a la relació entre estes dos classes:

¿És P igual a NP?

En una enquesta realisada en el 2002 entre 100 investigadors, 61 creïen que la resposta era NO, 9 creïen que la resposta era SI, 22 no estaven segurs, i 8 creïen que la pregunta podia ser independent dels #axioma actualment acceptats, i per lo tant impossible de demostrar pel SI o pel NO.

Definicions formals

Més precisament, un problema de decisió és un problema que especifica una cadena de caràcters de senyes d'entrada i requerix com a solució una resposta pel SI o pel NO. Si existix un algoritme (per eixemple una màquina de Turing, o un programa en llenguages Lisp o Pascal en memòria irrestricta) que és capaç d'entregar la resposta correcta per a tota cadena de senyes de llongitut n en com a molt $c\cdot n^k$ passos, a on k i c són constants independents del conjunt de senyes, llavors es diu que el problema pot ser resolt en temps polinòmic i ho classifiquem com a pertanyent a la classe P. En forma intuïtiva, considerem que els problemes continguts en P són aquells que poden ser resolts en forma raonablement ràpida.

P sol ser la classe de problemes computacionals que són “eficientemente resolubles” o “tractables”, encara que hi haja classes potencialment més grans que també es consideren tractables, com RP I BPP. Encara que també existixen problemes en P que no són tractables en térmens pràctics; per eixemple, uns requerixen a lo manco $n^{1000000}$ operacions.

En forma intuïtiva, es pot pensar que NP és un problema de decisió que és difícil de resoldre si no es posseïx cap atra senya o informació adicional. No obstant, si es rep l'informació adicional anomenada un certificat, llavors el problema pot ser resolt fàcilment. Per eixemple, si se nos dona el número 323 i se nos pregunta si 323 és un número factorisable, sense donar-nos cap senya o informació adicional, deuríem fer la raïl quadrada de 323 (+/-17.9722) redonejar al sancer menor en valor absolut (17) i intentar dividir des de 17 a 2. No obstant, si se nos dona el número 17, podem dividir 323 per 17 i ràpidament verificar que 323 és factorisable. El número 17 és cridat un certificat. El procés de divisió per a verificar que 323 és factorisable és en essència una màquina Turing i en este cas és denominat el verificador per a 323. Tècnicament es diu que el problema és fàcil si es pot resoldre en temps polinòmic i que és difícil si es resol en temps exponencial. Formalment, es definix NP com un conjunt de llenguages que satisfan certes condicions.

Siga L un llenguage definit sobre un alfabet finito, $\Sigma$.

Si existix una relació binaria $R\subset {\Sigma }^{*}\times {\Sigma }^{*}$ i un sancer positiu $k$ tal que para tot $x\in {\Sigma }^{*}$, se satisfan les següents condicions:

1. $x\in L\iff \mathrm{\exists }y\in {\Sigma }^{*}$ tal que $(x,y)\in R$ i $\left|y\right|\in O({\left|x\right|}^k)$ (O simbolisa cota superior asintòtica).
2. El llenguage $L_R$=$\{x\mathrm{\#}y:(x,y)\in R\}$ en $\Sigma \cup \{\mathrm{\#}\}$ és decidible per una màquina de Turing en temps polinomial.

Llavors, la màquina de Turing que decidix $L_R$ (que la cridarem $V$) és cridada el Verificador per a $L$ i $y$ és cridat el Certificat de membresía de $x$ en $L$.

Finalment, $L$ es troba en NP "si i solament si" $V$ corre en temps polinòmic.

Eixemple.

Siga

$\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{O}\mathrm{S}\mathrm{I}\mathrm{T}\mathrm{E}$ = $\{x\in \mathbb{N}:x=pq\text{para enteros}p,q>1\}$

$R$ = $\{(x,y)\in \mathbb{N}\times \mathbb{N}:1<y<x;y\text{divide a}x\}$

Clarament, la pregunta de si un donat x és factorisable és equivalent a la pregunta sobre si x és un membre de COMPOSITE. De fet, es pot demostrar fàcilment que $\mathrm{C}\mathrm{O}\mathrm{M}\mathrm{P}\mathrm{O}\mathrm{S}\mathrm{I}\mathrm{T}\mathrm{E}\in 𝐍𝐏$ si es verifica que COMPOSITE satisfà la condició indicada prèviament.

(Nota. Recentment es va demostrar que COMPOSITE estava dins de P)

La classe P

P és conegut per contindre molts problemes naturals, incloent les versions de decisió de programa llineal, càlcul del màxim comú divisor, i trobar una correspondència màxima.

Problemes notables en P

Alguns problemes naturals són complets per a P, incloent la conectivitat (o l'accessibilitat) en grafos no dirigits.

Una generalisació de P és NP, que és la classe de llenguages decidibles en temps polinòmic sobre una màquina de Turing no determinista. De forma trivial, tenim que P és un subconjunt de NP. Encara que no està demostrat, la major part dels experts creuen que açò és un subconjunt estricte.

Ací, EXPTIME és la classe de problemes resolubles en temps exponencial. De totes les classes mostrades dalt, només es coneixen dos #contenció estrictes:

• P estrictament està contingut en EXPTIME.
• L estrictament està continguda en PSPACE.

Els problemes més difícils en P són els problemes P-complets

Una atra generalisació de NP és el Temps polinòmic No uniforme (NP/Poly)[1]. Si un problema està en NP/poly, llavors pot solucionar-se en un temps polinomial determinat el qual, donat una cadena, este sol depén de la llongitut de l'entrada. A diferència de P, no es comproven les cadenes defectuoses que entren en la màquina de Turing, ya que no és un verificador.

NP/poly és una classe gran que conté casi tots els algoritmes pràctics, incloent tot el BPP. Si esta conté a P, la jerarquia polinomial es colapsa en el segon nivell. Per una atra part, esta també conté alguns algoritmes poc pràctics, incloent alguns problemes no decidibles.

Propietats

Els algoritmes de temps polinòmic són tancats respecte a la composició. Intuitivament, açò vol dir que si un escriu una funció en un determinat temps polinòmic i considerem que les cridades a eixa mateixa funció són constants i, de temps polinòmic, llavors l'algoritme complet és de temps polinòmic. Açò és un dels motius principals pels que P es considera una màquina independent; algunes traces d'esta màquina, com l'accés aleatori, és que pot calcular en temps polinòmic el temps polinòmic de l'algoritme principal reduint-ho a una màquina més bàsica.

Les proves existencials d'algoritmes de temps polinòmic

Es coneix que alguns problemes són resolubles en temps polinòmic, pero no es coneix cap algoritme concret per a solucionar-los. Per eixemple, la teorema Robertson-Seymour garantisa que hi ha una llista finita dels menors permesos que compon (per eixemple) el conjunt dels grafos que poden ser integrats sobre un toroide; ademés, Robertson i Seymour varen demostrar que hi ha una complexitat O (n³) en l'algoritme per a determinar si un grafo té un grafo inclós. Açò nos dona una prova no constructiva de que hi ha un algoritme de temps polinòmic per a determinar si donat un grafo pot ser integrat sobre un toroide, a pesar de no conéixer-se cap algoritme concret per a este problema.

Eixemples

Camí Mínim: trobar el camí mínim des d'un vèrtiç orige al restant dels vèrtiços.

Cicle Euleriano: Trobar un cicle que passe per cada arc d'un grafo una única volta.

La classe NP

La classe NP està composta pels problemes que tenen un certificat sucinto (també cridat testic polinòmic) para totes les instàncies la resposta de les quals és un SÍ. L'única forma de que tinguen un temps polinomial és realisant una etapa aleatòria, incloent l'encert d'alguna manera per a elegir una possible solució, i llavors en etapes posteriors comprova si eixa solució és correcta.

En atres paraules, donada una solució per a una certa instància, és possible comprovar que és vàlida en CLAVE (n^k). En el cas de SAT (Problema de satisfacibilidad booleana), donat una assignació de valors de veres, es pot comprovar fàcilment si la fòrmula és certa o no. Una nMT pot "endevinar" la solució en O (n) i verificar-la en temps polinòmic.

Completitud de NP

Per a analisar la pregunta P = NP, resulta molt útil el concepte de completitud NP. De manera informal, els problemes de completitud NP són els problemes més "difícils" en P en el sentit de que ells són els que són més provable no es troben en P. Problemes P-difícils són aquells per als quals qualsevol problema en P pot ser reduït en temps polinòmic. Els problemes de completitud P són aquells problemes P-difícil que es troben en P. Per eixemple, la versió de problema de decisió del problema del venedor viager és completament P. Aixina cap cas de cap problema en P pot ser transformat mecánicamente en una part del problema del venedor viager, en temps polinòmic. Per lo tant, si el problema del venedor viager estiguera contingut en NP, llavors P = NP. El problema del venedor viager és un de molts problemes P-complets. Si qualsevol problema P-complet es troba contingut en NP, llavors es verificaria que P = NP. Desafortunadament, s'ha demostrat que molts problemes importants són P-complets i no es coneix l'existència de cap algoritme ràpit per a ells.

La definició anterior de P permet considerar de manera natural una classe de problemes complementàries. La co-P està composta pels problemes que tenen un contraeixemple sucinto para totes les instàncies la resposta de les quals és NO.

Eixemples

Camí Màxim: Daus dos vèrtiços d'un grafo trobar el camí (simple) màxim.

Cicle Hamiltoniano: Cicle simple que conté cada vèrtiç del grafo.

NP-Complet

Per a abordar la pregunta de si P=NP, el concepte de la completitud de NP és molt útil. Informalment, els problemes de NP-complets són els problemes més difícils de NP, en el sentit de que són els més provables de no trobar-se en P. Els problemes de NP-complets són eixos problemes NP-durs que estan continguts en NP, a on els problemes NP-durs són estos que qualsevol problema en P pot ser reduït a complexitat polinomial. Per eixemple, la decisió del Problema del viajante de comerç és NP-complet, aixina que qualsevol cas de qualsevol problema en NP pot ser transformat mecánicamente en un cas del Problema del viajante de comerç, de complexitat polinomial. El Problema del viajante de comerç és dels molts problemes NP-complets existents. Si qualsevol problema NP-complet estiguera en P, llavors indicaria que P=NP. Desafortunadament, se sap que molts problemes importants són NP-complets i a data de 2008, no es coneix cap algoritme ràpit per a cap d'ells. Basant-nos solament en esta idea, no és obvi que existixca un problema NP-complet. Un problema NP-complet trivial i ideat, es pot formular com: Donada una descripció d'una màquina de Turing M que es deté en temps polinòmic, ¿existix una entrada de tamany polinòmic que M accepte? És NP perque, donada una entrada, és simple comprovar si M accepta o no l'entrada simulant M, és NP-durs perque el verificador per a qualsevol cas particular d'un problema en NP pot ser codificat com una màquina M de temps polinomial que pren la solució per a ser verificada com a entrada. Llavors la pregunta de si el cas és o no un cas, està determinat per l'existència d'una entrada vàlida. El primer problema natural que es va demostrar ser NP-complet va ser el Problema booleano de satisfacibilidad. Este resultat és conegut com el teorema de Cook-Levin; la seua prova de que la satisfacibilidad és NP-complet conté els detalls tècnics sobre màquines de Turing i com es relacionen en la definició de NP. No obstant, despuix es va demostrar que el problema era NP-complet, la prova per reducció, va proporcionar una manera més simple de demostrar que molts atres problemes estan en esta classe. Aixina, una classe extensa de problemes aparentment sense relació és reducible a una atra, i són en este sentit el mateix problema.

Solucions reclamades.

S'han publicat molts artículs intentant resoldre el problema P vs NP.

Vore també

• Ciències de la computació
• Teoria de la computació
• Teoria d'autómates
• Teoria de la computabilidad
• Teoria de la complexitat computacional
• Problemes del mileni

Bibliografia

• A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for nn chess requires clave 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.
• I. Berlekamp and D. Wolfe, Mathematical Go: Chilling Gets the Last Point, A. K. Peters, 1994. D. Wolfe, Go endgames llaure hard, MSRI Combinatorial Game Theor

i Resear

Enllaços externs

• The Clay Math Institute Millennium Prize Problems (en anglés)
• The Clay Math Institute Official Problem Description (pdf) (en anglés)

• Gerhard J. Woeginger. The P-versus-P 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 provable that all these alleged solutions llaure incorrect. (en anglés)
• Computational Complexity of Games and Puzles
• Scott Aaronson's Complexity Zoo: P, (en anglés)
• Qeden, a wiki that aims to solve the Millennium Prize Problems (en anglés)
• Scott Aaronson's Shtetl Optimized blog: Reasons to believe, a list of justifications for the belief that P ≠ NP (en anglés)