Complexidade computacional

A Teoría da Complexidade Computacional é unha rama da teoría da computación que se centra na clasificación dos problemas computacionais de acordo á súa dificultade inherente, e na relación entre devanditas clases de complexidade.

Un problema catalógase como "inherentemente difícil" se a súa solución require dunha cantidade significativa de recursos computacionais, sen importar o algoritmo empregado. A teoría da complexidade computacional formaliza dita aseveración, introducindo modelos de cómputo matemáticos para o estudo destes problemas e a cuantificación da cantidade de recursos necesarios para resolvelos, como tempo e memoria.

Un dos fins da teoría da complexidade computacional é determinar os límites prácticos de que é o que se pode facer nunha computadora e que non. Outros campos relacionados coa teoría da complexidade computacional son a análise de algoritmos e a teoría da computabilidade. Unha diferenza significativa entre a análise de algoritmos e a teoría da complexidade computacional, é que a primeira se dedica a determinar a cantidade de recursos requiridos por un algoritmo en particular para resolver un problema, mentres que a segunda, analiza todos os posibles algoritmos que puidesen ser usados para resolver o mesmo problema.

A teoría da complexidade computacional trata de clasificar os problemas que poden ou non poden ser resoltos cunha cantidade determinada de recursos. Á súa vez, a imposición de restricións sobre estes recursos é o que a distingue da teoría da computabilidade, que se preocupa por que tipo de problemas poden ser resoltos de maneira algorítmica.

Historia

Antes de que se realizasen investigacións ao redor da complexidade dos algoritmos, creáronse os cimentos desta teoría por varios investigadores. Unha das achegas máis influentes foi a definición das máquinas de Turing en 1936, que resultaron ser unha noción de computadora moi flexible e robusta. A medida que as computadoras se desenvolvían nas décadas de 1940 e 1950, a máquina de Turing demostrou ser o modelo teórico correcto de cómputo.

Con todo, rapidamente descubriuse que o modelo básico da máquina de Turing fallaba ao cuantificar o tempo e a memoria requirida por unha computadora, un problema crítico. A idea de medir o tempo e espazo como unha función da lonxitude da entrada, orixinouse a principios da década de 1960 por Hartmanis e Stearns e así naceu a teoría da complexidade computacional.

Nos inicios, os investigadores trataban de entender as novas medidas de complexidade, e como se relacionaban unhas coas outras. En 1965, Edmonds definiu un "bo" algoritmo como un cun tempo de execución limitado por un polinomio, é dicir, cun tempo de execución polinómico.^[1] Isto conduciu ao xurdimento dun dos conceptos máis importantes da teoría da complexidade computacional: a NP-completitude e a súa pregunta fundamental, se P=NP.

O campo comezou a florecer cando os investigadores Stephen Cook e Leonid Levin, traballando de xeito independente, probaron que existen problemas relevantes que son NP-completos. En 1972, Richard Karp levou esta idea un paso máis adiante, demostrando que 21 problemas combinatorios e de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.^[2] Tamén na década de 1970, produciuse un crecemento das clases de complexidade a medida que os investigadores trataban de comprender os distintos modelos de cómputo existentes.

Na década de 1980 produciuse un auxe dos modelos finitos, que analizaban o proceso de cómputo dunha maneira inherentemente distinta. Xurdiu un novo achegamento a problemas como P=NP, e aínda cando estes modelos tiñan as súas limitacións separando as clases de complexidade, esta aproximación introduciu técnicas combinatorias que permitiron un mellor entendemento dos límites destes modelos.

Xa na década de 1990 estudáronse novos modelos de cómputo como as computadoras cuánticas, onde unha mesma tarefa pode ter diferente complexidade na computación clásica e na computación cuántica. Con todo, existen varias limitacións, entre elas, a de desenvolver un hardware para este modelo, e que se requiren grandes cantidades de espazo para realizar os cálculos.

Problemas, algoritmos e complexidade

Para poder referirse a problemas como "inherentemente intratables" e problemas de dificultade "equivalente", é necesario comprender algúns termos máis básicos.

Problema computacional

Percorrido dun viaxante polas 15 cidades máis grandes de Alemaña

Un problema computacional constitúe unha pregunta que debe ser respondida, tendo xeralmente varios parámetros, ou variables libres, con valores que non se especificaron. Un problema descríbese mediante:

Unha descrición xeral de todos os seus parámetros (poden ser de entrada ou de saída).
Unha sentenza que describa as propiedades que a resposta, ou a solución, debe cumprir.

Unha instancia dun problema obtense cando se especifican valores particulares para todos os parámetros do problema. Por exemplo, considérese o problema do test de primalidade. A instancia é un número e a solución é "si" se o número é primo, e "non" en caso contrario. Visto doutra maneira, a instancia é unha entrada particular do problema, e a solución é a saída correspondente para a entrada dada.

Problemas de decisión

Un problema de decisión só ten dúas posibles saídas, si ou non para cada entrada

Un problema de decisión é un tipo especial de problema computacional que ten como resposta soamente "si" ou "non" (ou, de maneira máis formal, "1" ou "0").

Un problema de decisión podería verse como unha linguaxe formal, onde os elementos que pertencen á linguaxe son as instancias do problema con resposta "si" e os que non pertencen á linguaxe son aquelas instancias con resposta "non". O obxectivo é decidir, coa axuda dun algoritmo, se unha determinada entrada é un elemento da linguaxe formal considerada. Se o algoritmo devolve como resposta "si", dise que o algoritmo acepta a entrada, pola contra dise que a rexeita.

Os problemas de decisión constitúen un dos principais obxectos de estudo da teoría da complexidade computacional, pois a NP-completitude aplícase directamente a estes tipos de problemas no canto de a problemas de optimización. Estes problemas teñen grande importancia porque case calquera problema pode transformarse nun problema de decisión.

Algoritmos

Pódese dicir informalmente, que os algoritmos son procedementos paso a paso para resolver problemas. Pódese pensar neles como simples programas de computadora, escritos nunha linguaxe artificial específica.^[3]

Dise que un algoritmo resolve un problema A, se devandito algoritmo se pode aplicar a calquera instancia I de A, e garántese que sempre produce unha solución para esa instancia. De maneira xeral, interésanos atopar o algoritmo máis "eficiente" para resolver certo problema. No seu sentido máis amplo, a noción de eficiencia involucra a todos os recursos computacionais necesarios para a execución dun algoritmo.

Por algoritmo "máis eficiente" usualmente refírese ao máis rápido. Debido a que os requirimentos de tempo son habitualmente un factor dominante cando se trata de determinar se un algoritmo é o suficientemente eficiente para ser útil na práctica, haberá que concentrarse neste recurso.

Algoritmos de tempo polinómico e problemas intratables

Os científicos da computación realizan a distinción entre algoritmos de tempo polinómico e algoritmos de tempo exponencial cando se trata de caracterizar os algoritmos como "suficientemente eficiente" e "moi ineficiente" respectivamente.

Un algoritmo de tempo polinómico defínese como aquel con función de complexidade temporal en O(p(n)) para algunha función polinómica p, onde n denota o tamaño da entrada. Calquera algoritmo cunha función de complexidade temporal que non poida ser limitada desta maneira, denomínase algoritmo de tempo exponencial.

A maioría dos algoritmos de tempo exponencial son simples variacións dunha procura exhaustiva, mentres que os algoritmos de tempo polinómico, adoitan obterse mediante unha análise máis profunda da estrutura do problema. Na teoría da complexidade computacional, existe o consenso de que un problema non está "ben resolto" ata que se coñeza un algoritmo de tempo polinómico que o resolva. Polo tanto, refírese a un problema como intratable se é tan difícil que non existe algoritmo de tempo polinómico capaz de resolvelo.^[4]

Clases de complexidade

Unha clase de complexidade é un conxunto de problemas que posúen a mesma complexidade computacional.

Definindo clases de complexidade

As clases de complexidade máis sinxelas defínense tendo en conta factores como:

O tipo de problema computacional: Os problemas máis comunmente empregados son os problemas de decisión, pero as clases de complexidade pódense definir para outros tipos de problemas.
O modelo de cómputo: O modelo de cómputo máis común é a máquina de Turing determinista, pero moitas clases de complexidade baséanse en máquinas de Turing non deterministas, máquinas de Turing cuánticas etc.
O recurso (ou recursos) que está(n) sendo limitado(s) e a(s) cota(s): Estas dúas propiedades adoitan empregarse xuntas, por exemplo, "tempo polinómico", "espazo logarítmico", "profundidade constante" etc.

Máquinas de Turing deterministas e a clase P

A clase P contén aqueles problemas que son solubles en tempo polinómico por unha máquina de Turing determinista.^[5]

Para a definición anterior fixouse o modelo de cómputo: a máquina de Turing determinista. Existen distintas variantes da máquina de Turing e coñécese que a máis débil delas pode simular a máis forte, engadindo como máximo un tempo polinómico. Nas décadas posteriores á tese de Church-Turing xurdiron outros modelos de cómputo, e púidose mostrar que a máquina de Turing tamén podía simulalos como máximo engadindo tamén un tempo polinómico. Polo tanto, a clase análoga a P para devanditos modelos non é maior que a clase P para o modelo de cómputo da máquina de Turing.

A clase P xoga un papel importante na teoría da complexidade computacional debido a que:

P é invariante para todos os modelos de cómputo que son polinomicamente equivalentes á máquina de Turing determinista.
A grandes liñas, P corresponde á clase de problemas que, de maneira realista, son solubles nunha computadora.

Computación non determinista e a clase NP

Moitas veces pódese evitar empregar a forza bruta nos problemas para obter solucións en tempo polinómico. Con todo, para algúns problemas isto non puido lograrse, é dicir, non se coñecen algoritmos que os resolvan en tempo polinómico. Quizais estes problemas teñan algoritmos en tempo polinómico que se basean en principios por agora descoñecidos, ou quizais estes problemas non poden ser resoltos en tempo polinómico, debido a que son "inherentemente difíciles".

A clase de complexidade NP consta dos problemas "verificables" en tempo polinómico. Por verificable enténdese un problema tal que dado un certificado de solución (candidato a solución), pódese verificar que devandito certificado é correcto nun tempo polinómico no tamaño da entrada. Os problemas na clase NP adoitan chamarse problemas NP.^[6]

O termo NP provén de non determinista en tempo polinómico e derívase dun caracterización alternativa desta clase, onde se utilizan máquinas de Turing non deterministas. Informalmente, pódese definir a clase NP en termos dun algoritmo non determinista (dada a equivalencia entre algoritmo e máquina de Turing).

O algoritmo mencionado está composto por dúas etapas separadas. Dada unha instancia do problema I, a primeira etapa simplemente "adiviña" un candidato a solución S. Entón, a etapa de verificación recibe como entrada I e S, e procede a realizar o cómputo dunha maneira determinista, finalmente deténdose coa resposta "si", ou coa resposta "non", ou continúa a computar sen deterse.

Do mesmo xeito que a clase P, a clase NP é insensible á elección do modelo de cómputo non determinista, debido a que devanditos modelos son equivalentes polinomicamente.

Clases de complexidade importantes

Representación da relación entre as clases de complexidade

Moitas clases de complexidade importantes poden ser definidas limitando o tempo ou o espazo utilizado polo algoritmo. Algunhas destas clases de problemas de decisión son:

Clase de complexidade	Modelo de cómputo	Restrición de recurso
DTIME(f(n))	Máquina de Turing determinista	Tiempof(n)
P	Máquina de Turing determinista	Tempo poly(n)
EXPTIME	Máquina de Turing determinista	Tempo 2^poly(n)
NTIME(f(n))	Máquina de Turing non determinista	Tempo f(n)
NP	Máquina de Turing non determinista	Tempo poly(n)
NEXPTIME	Máquina de Turing non determinista	Tempo 2^poly(n)
DSPACE(f(n))	Máquina de Turing determinista	Espazo f(n)
L	Máquina de Turing determinista	Espazo O(log n)
PSPACE	Máquina de Turing determinista	Espazo poly(n)
EXPSPACE	Máquina de Turing determinista	Espazo 2^poly(n)
NSPACE(f(n))	Máquina de Turing non determinista	Espazo f(n)
NL	Máquina de Turing non determinista	Espazo O(log n)
NPSPACE	Máquina de Turing non determinista	Espazo poly(n)
NEXPSPACE	Máquina de Turing non determinista	Espazo 2^poly(n)

A pregunta P=NP

Artigo principal: P versus NP.

A relación entre as clases P e NP é fundamental para a teoría da NP-completitude. Intuitivamente, crese que P é un subconxunto de NP. E, efectivamente, cada problema de decisión resolto por un algoritmo de tempo polinómico determinista, tamén pode ser resolto por un algoritmo de tempo polinómico non determinista. Simplemente necesítase observar que calquera algoritmo determinista pode ser empregado na etapa de verificación dun algoritmo non determinista. Se B é un problema de P, e A é un algoritmo de tempo polinómico para B, entón pódese construír un algoritmo de tempo polinómico non determinista para B, simplemente utilizando A na etapa de verificación e ignorando a etapa de adiviñación. Polo tanto, se B pertence a P, entón B tamén pertence a NP.

A pregunta P=NP é unha das máis importantes no campo das ciencias da computación, debido ás grandes repercusións que habería, en caso de atoparse unha solución. Se P=NP, calquera problema polinomicamente verificable sería polinomicamente decidible. A maioría dos investigadores cre que estas clases non son iguais, porque se realizaron bastantes esforzos, sen éxito, para atopar algoritmos de tempo polinómico para varios problemas en NP. Os investigadores tamén trataron de probar que as clases son distintas, pero iso levaría a mostrar que non existe un algoritmo «eficiente» para substituír a procura por forza bruta.

NP-Completitud

Redución polinómico

Unha redución é unha transformación dun problema noutro problema. Intuitivamente, un problema Q pode ser reducido a outro problema Q', se calquera instancia do problema Q pode ser "facilmente" expresada como unha instancia do problema Q', e cuxa solución proporcione unha solución para a instancia de Q.^[7]

Existen moitos tipos de reducións: baseadas no método de redución, como as reducións de Cook, as reducións de Karp e as reducións de Levin, e as baseadas na cota da complexidade, como a redución en tempo polinómico ou a redución de espazo logarítmica. Unha das reducións máis utilizadas é a redución en tempo polinómica, o cal significa que o proceso de redución toma un tempo polinómico.

Problemas NP-completos

As reducións en tempo polinómico ofrecen elementos para probar, dunha maneira formal, que un problema é polo menos tan difícil coma outro, cunha diferenza dun factor polinómico. Estas son esenciais para definir os problemas NP-completos, ademais de axudar a comprender os mesmos.

A clase dos problemas NP-completos contén os problemas máis difíciles en NP, no sentido de que son os que estean máis lonxe de estar en P. Debido a que o problema P=NP non foi resolto, o feito de reducir un problema B, a outro problema A, indicaría que non se coñece solución en tempo polinómico para A. Isto é debido a que unha solución en tempo polinómico para A, tería como consecuencia a existencia dunha solución polinómica para B. De xeito semellante, debido a que todos os problemas NP poden ser reducidos a este conxunto, atopar un problema NP-completo que poida ser resolto nun tempo polinómico significaría que P=NP.

Importancia da NP-completitude

Quizais a razón de maior peso pola cal os científicos da computación cren que P é distinto de NP, é a existencia da clase de problemas "NP-completos". Esta clase ten a propiedade de que se algún problema NP-completo pode ser resolto en tempo polinómico, entón todo problema en NP ten unha solución en tempo polinómico, é dicir, P=NP. A pesar de anos de estudo, non se descubriu ningún algoritmo de tempo polinómico para ningún problema NP-completo.

Dende o punto de vista teórico, un investigador que tente mostrar que a clase P é distinta da clase NP, podería enfocarse nun problema NP-completo. Se algún problema en NP require máis que un tempo polinómico, entón un NP-completo tamén. Ademais, un investigador que tente demostrar que P=NP só necesita atopar un algoritmo de tempo polinómico para un problema NP-completo para logralo.

Dende o punto de vista práctico, o fenómeno da NP-completitude pode previr a perda de tempo cando se busca un algoritmo de tempo polinómico non existente para resolver un problema determinado. Aínda cando non se posúan os elementos matemáticos para demostrar que certo problema non se pode resolver en tempo polinómico, crese que P non é igual a NP, así que demostrar que o problema é NP-completo, é unha forte evidencia da súa non "polinomicidade".

Facendo fronte a problemas NP

Tendo en conta a definición de problema intratable, se non se cumpre que P=NP, entón os problemas NP-completos son intratables.

Moitos problemas da práctica son NP-completos, e son moi importantes como para desistir simplemente porque non se sabe como atopar unha solución óptima en tempo polinómico. Aínda que un problema sexa NP-completo, pode haber esperanza. Existen tres estratexias fundamentais para enfrontarse a un problema NP-completo:

Se a entrada é pequena, un algoritmo con tempo de execución exponencial podería ser perfectamente aceptable.
Se se puidesen illar algúns casos especiais que se puidesen resolver en tempo polinómico.
Poderíanse empregar aproximacións para atopar solucións o suficientemente próximas ao óptimo en tempo polinómico. Na práctica, obter solucións próximas ao óptimo é bastante aceptable. A estes algoritmos denomínaselles algoritmos de aproximación, e en moitos casos apóianse en heurísticas e metaheurísticas.

Notas

↑ Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.
↑ Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). En R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. Arquivado dende o orixinal (PDF) o 29 de xuño de 2011. Consultado o 04 de agosto de 2017. .
↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 4).
↑ Garey, Michael R., Johnson David S., (1979), A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 8).
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press e McGraw-Hill, (páxina 1049).
↑ Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 28).
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (páxina 1067).

Véxase tamén

Bibliografía

Artigos

Cook, Stephen (1983). An overview of computational complexity. Commun. ACM 26 (ACM). pp. 400–408. ISSN 0001-0782.
Fortnow, Lance; Homer, Steven (2002). A Short History of Computational Complexity (PDF). Bulletin of the EATCS 80. pp. 95–133.

Libros de texto

Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: A Modern Approach. Cambridge. ISBN 978-0-521-42426-4. Zbl 1193.68112.
Sipser, Michael (2006). Introduction to the Theory of Computation (2.ª ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3.
Garey, Michael R.; Johnson, David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2010). Introduction to Algorithms (3.ª ed.). Cambridge, MA: MIT Press and McGraw-Hill. ISBN 0-262-03384-4.

Outros artigos

[1] Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture.

[2] Richard M. Karp (1972). "Reducibility Among Combinatorial Problems" (PDF). En R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. Arquivado dende o orixinal (PDF) o 29 de xuño de 2011. Consultado o 04 de agosto de 2017. .

[3] Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 4).

[4] Garey, Michael R., Johnson David S., (1979), A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 8).

[5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press e McGraw-Hill, (páxina 1049).

[6] Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 28).

[7] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (páxina 1067).

[1]

[2]

[3]

[4]

[5]

[6]

[7]