Complexidade computacional
A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional é entendido como uma tarefa que é, em princípio, passível de ser resolvida por um computador. Informalmente, um problema computacional consiste de instâncias do problema e soluções para essas instâncias do problema. Por exemplo, o teste de primalidade é o problema de determinar se um dado número é primo ou não. As instâncias deste problema são números naturais, e a solução para uma instância é sim ou não, dependendo se o número é primo ou não.
Instâncias de Problema
Um problema computacional pode ser visto como uma coleção infinita de instâncias em conjunto com uma solução para cada instância. A sequência de entrada para um problema computacional é referido como uma instância do problema, e não deve ser confundido com o problema em si. Na teoria da complexidade computacional, um problema se refere à questão abstrata para ser resolvido. Em contraste, uma instância deste problema é uma expressão concreta, que pode servir como entrada para um problema de decisão. Por exemplo, considere o problema de teste de primalidade. A instância é um número (por exemplo, 10) e a solução é "sim" se o número é primo e "não" se for o contrário (neste caso "não"). Alternativamente, a instância é uma entrada especial para o problema, e a solução é a saída correspondente à entrada.
Representando instâncias de problema
Ao considerar problemas computacionais, uma instância de problema é uma cadeia sobre um alfabeto. Normalmente, o alfabeto é considerado como sendo o alfabeto binário (ou seja, o conjunto {0,1}), e, assim, as cadeias são bitstrings. Como em um computador do mundo real, objetos matemáticos que não são bitstrings devem ser devidamente codificados. Por exemplo, números inteiros podem ser representados em notação binária, e grafos podem ser codificados diretamente via suas matrizes de adjacência, ou por codificação de suas listas de adjacência em binário. Apesar de algumas provas de complexidade-teórica de teoremas regularmente assumir alguma escolha concreta de codificação de entrada, tenta-se manter a discussão abstrata o suficiente para ser independente da escolha da codificação. Isto pode ser conseguido assegurando que diferentes representações possam ser transformadas em outra de forma eficiente.
Problemas de decisão como linguagens formais
Problemas de decisão são um dos objetos de estudo centrais na teoria da complexidade computacional. Um problema de decisão é um tipo especial de problema computacional cuja resposta é sim ou não, ou alternativamente 1 ou 0. Um problema de decisão pode ser visto como uma linguagem formal, onde os membros da linguagem são instâncias cuja resposta é sim, e os não membros da linguagem são aquelas instâncias cuja saída é não. O objetivo é decidir, com a ajuda de um algoritmo, se uma dada sequência de entrada é um membro da linguagem formal em consideração. Se o algoritmo decidir este problema, ele retorna a resposta sim, diz-se que o algoritmo aceita a sequência de entrada, caso contrário, diz-se que rejeita a entrada.
Problemas de função
Um problema de função é um problema computacional, onde uma única saída (de uma função total) é esperada para cada entrada, mas a saída é mais complexa do que a de um problema de decisão, isto é, não é apenas sim ou não. Exemplos notáveis incluem o problema do caixeiro viajante e o problema de fatoração de inteiros. É tentador pensar que a noção de problemas de função é muito mais rica do que a noção de problemas de decisão. No entanto, o caso realmente não é esse, já que problemas de função podem ser reformulados como problemas de decisão. Por exemplo, a multiplicação de dois números inteiros pode ser expressa como o conjunto (a, b, c) tal qual a relação a × b = c descreve. Decidir se uma dada tripla é membro deste conjunto corresponde a resolver o problema da multiplicação de dois números.
Mensuração do tamanho de uma instância
Para medir a dificuldade de resolver um problema computacional, pode-se desejar ver quanto tempo o melhor algoritmo necessita para resolver o problema. No entanto, o tempo de execução pode, em geral, depender da instância. Em particular, instâncias maiores exigirão mais tempo para resolver. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer outra medida de complexidade) é calculado em função do tamanho da instância. Isso geralmente leva em consideração o tamanho da entrada em bits. A Teoria da Complexidade está interessada em como os tempos de execução de algoritmos crescem com um aumento no tamanho da entrada. Por exemplo, no problema de descobrir se um grafo é conectado, quanto tempo a mais leva para resolver um problema para um grafo com 2n vértices comparado ao tempo levado para um grafo com n vértices?
Máquina de Turing
Uma máquina de Turing é um modelo matemático de uma máquina de computação em geral. É um dispositivo teórico que manipula símbolos contidos em uma tira de fita. Máquinas de Turing não pretendem ser uma tecnologia de computação na prática, mas sim uma experiência de pensamento que representa uma máquina de computação. Acredita-se que se um problema pode ser resolvido por um algoritmo, então existe uma máquina de Turing que resolve o problema. Na verdade, esta é a afirmação da tese de Church-Turing. Além disso, sabe-se que tudo o que pode ser computado em outros modelos de computação conhecido por nós hoje, como uma máquina RAM, Jogo da Vida de Conway, autômato celular ou qualquer linguagem de programação pode ser computado em uma máquina de Turing. Como as máquinas de Turing são fáceis de analisar matematicamente, e acredita-se que sejam tão poderosas quanto qualquer outro modelo de computação, a máquina de Turing é o modelo mais comumente usado em teoria da complexidade.
Outros modelos de máquinas
Muitos modelos de máquinas diferentes do padrão de máquinas de Turing multi-fitas têm sido propostos na literatura, por exemplo, máquinas de acesso aleatório. Talvez surpreendentemente, cada um desses modelos pode ser convertido para outro, sem fornecer qualquer poder computacional extra. O consumo de tempo e memória desses modelos alternativos pode variar. O que todos estes modelos têm em comum é que as máquinas funcionam de forma determinística. No entanto, alguns problemas computacionais são mais fáceis de analisar em termos de recursos mais incomuns. Por exemplo, uma máquina de Turing não-determinística é um modelo computacional em que é permitido ramificar-se para verificar muitas possibilidades diferentes de uma só vez. A máquina de Turing não-determinística tem muito pouco a ver com a forma como nós queremos fisicamente computar algoritmos, mas a sua ramificação capta exatamente muitos dos modelos matemáticos que queremos analisar, de modo que o tempo não-determinístico é um recurso muito importante na análise de problemas computacionais.
Medidas de complexidade
Para uma definição precisa do que significa resolver um problema utilizando uma determinada quantidade de tempo e espaço, um modelo computacional tal como a máquina de Turing determinística é utilizado. O tempo exigido por uma máquina de Turing determinística M na entrada x é o número total de transições de estado, ou etapas, que a máquina faz antes de parar e responder com a saída ("sim" ou "não"). Diz-se que a máquina de Turing M opera dentro do tempo f(n), se o tempo exigido por M em cada entrada de comprimento n é no máximo f(n). Um problema de decisão A pode ser resolvido em tempo f(n) se existe uma operação da máquina de Turing em tempo f(n) que resolve o problema. Como a teoria da complexidade está interessada em classificar problemas com base na sua dificuldade, definem-se conjuntos de problemas com base em alguns critérios. Por exemplo, o conjunto de problemas solucionáveis no tempo f(n) em uma máquina de Turing determinística é então indicado por DTIME(f(n)).
Melhor, pior e caso médio de complexidade
O melhor, o pior e o caso médio de complexidade referem-se a três maneiras diferentes de medir a complexidade de tempo (ou qualquer outra medida de complexidade) de entradas diferentes do mesmo tamanho. Uma vez que algumas entradas de tamanho n podem ser mais rápidas para resolver do que outras, definimos as seguintes complexidades: Por exemplo, considere o algoritmo de ordenação quicksort. Isso resolve o problema de ordenar uma lista de inteiros que é dada como entrada. O pior caso é quando a entrada já está ordenada ou está em ordem inversa, e o algoritmo leva tempo O(n2) para este caso. Se assumirmos que todas as permutações possíveis da lista de entrada são igualmente prováveis, o tempo médio necessário para a ordenação é O(n log n). O melhor caso ocorre quando cada pivô divide a lista pela metade, também precisando tempo O(n log n).
Limites superior e inferior da complexidade dos problemas
Para classificar o tempo de computação (ou recursos semelhantes, como o consumo de espaço), é necessário provar os limites superiores e inferiores sobre a quantidade mínima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo é geralmente entendida como a sua complexidade de pior caso, a menos que seja especificado o contrário. A análise de um determinado algoritmo cai sob o campo de análise de algoritmos. Para mostrar um limite superior T(n) sobre a complexidade de tempo de um problema, é necessário mostrar apenas que há um determinado algoritmo com tempo de funcionamento, no máximo, T(n). No entanto, provar limites inferiores é muito mais difícil, uma vez que limites inferiores fazem uma declaração sobre todos os possíveis algoritmos que resolvem um determinado problema. A frase "todos os algoritmos possíveis" inclui não apenas os algoritmos conhecidos hoje, mas qualquer algoritmo que possa ser descoberto no futuro. Para mostrar um limite inferior de T(n) para um problema requer mostrar que nenhum algoritmo pode ter complexidade de tempo menor do que T(n).
Definição de classes de complexidade
Uma classe de complexidade é um conjunto de problemas de complexidade relacionados. As classes mais simples de complexidade são definidas pelos seguintes fatores: É claro, algumas classes de complexidade têm definições complexas que não se encaixam nesse quadro. Assim, uma classe de complexidade típica tem uma definição como a seguinte: Mas limitar o tempo de computação acima por alguma função concreta f(n) muitas vezes produz classes de complexidade que dependem do modelo da máquina escolhida. Por exemplo, a linguagem {xx | x é uma sequência binária qualquer} pode ser resolvida em tempo linear em uma máquina de Turing multi-fitas, mas necessariamente exige tempo quadrático no modelo de máquinas de Turing single-fita. Se permitirmos variações no tempo polinomial em execução, a tese de Cobham-Edmonds afirma que "as complexidades do tempo em quaisquer dois modelos razoáveis e gerais de computação são polinomialmente relacionados" (Goldreich 2008, Chapter 1.2). Isto forma a base para a classe de complexidade P, que é o conjunto de problemas de decisão solúveis por uma máquina de Turing determinística dentro do tempo polinomial. O conjunto correspondente de problemas de função é FP.
Importantes classes de complexidade
Muitas classes de complexidade importantes podem ser definidas por limitando o tempo ou espaço usado pelo algoritmo. Algumas importantes classes de complexidade de problemas de decisão definidas desta maneira são as seguintes: Acontece que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE pelo teorema de Savitch. Outras classes de complexidade importantes incluem BPP, ZPP e RP, que são definidas usando máquinas de Turing probabilística; AC e NC, que são definidas usando circuitos booleanos e BQP e QMA, que são definidas usando máquinas de Turing quânticas. #P é uma importante classe complexidade de problemas de contagem (que não são problemas de decisão). Classes como IP e AM são definidas usando sistemas de prova interativa. ALL é a classe de todos os problemas de decisão.
Teoremas de hierarquia
Para as classes de complexidade definidas desta forma, é desejável provar que relaxar os requisitos em função (digamos) do tempo de computação realmente define um conjunto maior de problemas. Em particular, embora DTIME(n) esteja contido em DTIME(n2), seria interessante saber se a inclusão é estrita. Para requisitos de tempo e de espaço, a resposta a tais perguntas é dada pelo teorema de hierarquia para a complexidade de tempo e pelo teorema de hierarquia para a complexidade de espaço, respectivamente. Eles são chamados teoremas de hierarquia porque induzem uma hierarquia adequada sobre as classes definidas, restringindo os respectivos recursos. Assim, existem pares de classes de complexidade tal que uma está propriamente contida na outra. Depois de ter deduzido assim as relações de pertinência estrita de conjuntos, podemos continuar a fazer declarações quantitativas sobre quanto mais tempo adicional ou espaço é necessário para aumentar o número de problemas que podem ser resolvidos.
Redução
Muitas classes de complexidade são definidas usando o conceito de redução. Uma redução é uma transformação de um problema em outro problema. Ela captura a noção informal de um problema que seja pelo menos tão difícil quanto outro problema. Por exemplo, se um problema X pode ser resolvido usando um algoritmo para Y, X não é mais difícil do que Y, e dizemos que X se reduz a Y. Existem muitos tipos diferentes de redução, com base no método de redução, como reduções de Cook, reduções de Karp e reduções Levin, e no limite da complexidade das reduções, como reduções de tempo polinomial ou reduções log-space. A redução mais comumente usada é uma redução em tempo polinomial. Isso significa que o processo de redução leva tempo polinomial. Por exemplo, o problema do quadrado de um inteiro pode ser reduzido para o problema da multiplicação de dois números inteiros. Isso significa que um algoritmo para multiplicar dois inteiros pode ser usado para o quadrado de um inteiro. De fato, isso pode ser feito dando a mesma entrada para ambas as entradas do algoritmo de multiplicação. Assim, vemos que o problema do quadrado de um inteiro não é mais difícil do que o problema da multiplicação, já que o problema do quadrado de um inteiro pode ser reduzido ao problema da multiplicação.
O problema P versus NP
A classe de complexidade P é muitas vezes vista como uma abstração matemática de modelagem dessas tarefas computacionais que admitem um algoritmo eficiente. Esta hipótese é chamada de tese de Cobham-Edmonds. A classe de complexidade NP, por outro lado, contém muitos problemas que as pessoas gostariam de resolver de forma eficiente, mas para os quais nenhum algoritmo eficiente é conhecido, como o problema da satisfatibilidade booleana, o problema do caminho hamiltoniano e o problema da cobertura de vértices. Como as máquinas de Turing determinística são máquinas de Turing não-determinísticas especiais, é fácil observar que cada problema em P também é membro da classe NP.
Problemas em NP que não se sabe se pertencem a P ou a NP-completo
Foi mostrado por Ladner que, se P ≠ NP, então existem problemas em NP que não estão nem em P nem em NP-completo. Tais problemas são chamados de problemas NP-intermediário. O problema do isomorfismo de grafos, o problema do logaritmo discreto e o problema de fatoração de inteiros são exemplos de problemas que acredita-se que sejam NP-intermediário. Eles são alguns dos muito poucos problemas NP que não se sabe se estão em P ou em NP-completo. O problema do isomorfismo de grafos é o problema computacional para determinar se dois grafos finitos são isomorfos. Um importante problema não resolvido na teoria da complexidade é se o problema do isomorfismo de grafos está em P, NP-completo, ou NP-intermediário. A resposta não é conhecida, mas acredita-se que o problema não seja, pelo menos, NP-completo. Se o isomorfismo de grafos for NP-completo, a hierarquia de tempo polinomial colapsa para seu segundo nível. Uma vez que acredita-se veemente que a hierarquia polinomial não colapse para nenhum nível finito, acredita-se que o isomorfismo de grafos não seja NP-completo. O melhor algoritmo para este problema, de acordo com Laszlo Babai e Eugene Luks tem tempo de execução 2O(√(n log(n))) para grafos com n vértices.
Separações entre outras classes de complexidade
Muitas classes de complexidade conhecidas são suspeitas de não serem iguais, mas isso não foi provado. Por exemplo, P ⊆ NP ⊆ PP ⊆ PSPACE, mas é possível que P = PSPACE. Se P não for igual a NP, então P não será igual à PSPACE também. Uma vez que existem muitas classes de complexidade conhecidas entre P e PSPACE, tais como RP, BPP, PP, BQP, MA, PH, etc, é possível que todas estas classes de complexidade colapsem para uma única classe. Provar que qualquer uma destas classes não são iguais seria um grande avanço na teoria da complexidade. Na mesma linha, co-NP é a classe que contém os problemas do complemento (ou seja, problemas com as respostas sim / não invertidas) dos problemas NP. Acredita-se que NP não seja igual a co-NP, no entanto, ainda não foi comprovado. Tem sido mostrado que, se essas duas classes de complexidade não são iguais, então P não é igual a NP.
Problemas que podem ser resolvidos na teoria (por exemplo, dado um tempo infinito), mas que na prática levam muito tempo para as suas soluções sejam úteis, são conhecidos como problemas intratáveis. Na teoria da complexidade, os problemas que não apresentam soluções em tempo polinomial são considerados intratáveis por mais pequenas que sejam suas entradas. Na verdade, a tese de Cobham-Edmonds afirma que apenas os problemas que podem ser resolvidos em tempo polinomial podem ser computados de maneira factível por algum dispositivo computacional. Problemas que são conhecidos por serem intratáveis neste sentido incluem aqueles que são EXPTIME-difícil. Se NP não é o mesmo que P, então os problemas NP-completo são também intratáveis neste sentido. Para ver porque algoritmos de tempo exponencial podem ser impraticáveis, considere um programa que faz 2n operações antes de parar. Para n pequeno, digamos 100, e assumindo, por exemplo, que o computador faz 1012 operações por segundo, o programa seria executado por cerca de 4 × 1010 anos, que é aproximadamente a idade do universo. Mesmo com um computador muito mais rápido, o programa só seria útil para casos muito pequenos e, nesse sentido, a intratabilidade de um problema é um tanto independente do progresso tecnológico. No entanto, um algoritmo de tempo polinomial não é sempre prático. Se seu tempo de execução é, digamos "n"15, não é razoável considerá-lo eficiente e ainda é inútil, salvo em casos de pequeno porte.
A teoria da complexidade contínua pode se referir à teoria da complexidade dos problemas que envolvem funções contínuas que são aproximadas por discretizações, como estudado em análise numérica. Uma abordagem para a teoria da complexidade da análise numérica é a complexidade baseada em informação (IBC). A teoria da complexidade contínua também pode se referir à teoria da complexidade do uso da computação analógica, que utiliza sistemas dinâmicos contínuos e equações diferenciais. A teoria de controle pode ser considerada uma forma de computação e equações diferenciais são usadas na modelagem de sistemas de tempo contínuo e híbridos de tempo discreto-contínuo.
Antes de a pesquisa propriamente dita explicitamente dedicada à complexidade dos problemas algorítmicos começar, os numerosos fundamentos foram estabelecidos por vários pesquisadores. O mais influente entre estes foi a definição das máquinas de Turing por Alan Turing em 1936, que acabou por ser uma noção muito robusta e flexível de computador. Fortnow & Homer (2003) datam o início dos estudos sistemáticos em complexidade computacional com o importante artigo "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard Stearns (1965), que estabeleceu as definições de complexidade de tempo e de espaço e provou os teoremas de hierarquia. De acordo com Fortnow & Homer (2003), trabalhos anteriores que estudaram problemas solucionáveis por máquinas de Turing com recursos específicos limitados inclui a definição de John Myhill de autômatos linearmente limitados (Myhill 1960), o estudo de Raymond Smullyan sobre conjuntos rudimentares (1961), assim como o artigo de Hisao Yamada sobre computação em tempo real (1962). Um pouco mais cedo, Boris Trakhtenbrot (1956), um pioneiro no campo da URSS, estudou outra medida específica de complexidade. Como lembra ele:
