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.Richard M. Karp, "Combinatorics, Complexity, and Randomness", 1985 Turing Award Lecture. 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.. 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 miniatura|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 miniatura|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.Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 4).
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.Garey, Michael R., Johnson David S., (1979), A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 8).
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.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).
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.Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, (páxina 28).