Teoria da complexidade computacional

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Inerente dificuldade de problemas computacionais

Em ciência da computação teórica e matemática, a teoria da complexidade computacional se concentra na classificação de problemas computacionais de acordo com o uso de recursos e na relação dessas classes umas com as outras. Um problema computacional é uma tarefa resolvida por um computador. Um problema de computação pode ser resolvido pela aplicação mecânica de etapas matemáticas, como um algoritmo.

Um problema é considerado inerentemente difícil se a sua solução requer recursos significativos, qualquer que seja o algoritmo utilizado. A teoria formaliza essa intuição, introduzindo modelos matemáticos de computação para estudar esses problemas e quantificando sua complexidade computacional, ou seja, a quantidade de recursos necessários para resolvê-los, como tempo e armazenamento. Outras medidas de complexidade também são usadas, como a quantidade de comunicação (usada na complexidade da comunicação), o número de portas em um circuito (usado na complexidade do circuito) e o número de processadores (usado na computação paralela). Um dos papéis da teoria da complexidade computacional é determinar os limites práticos sobre o que os computadores podem ou não fazer. O problema P versus NP, um dos sete Problemas do Prêmio do Milênio, é dedicado ao campo da complexidade computacional.

Campos intimamente relacionados na ciência da computação teórica são a análise de algoritmos e a teoria da computabilidade. Uma distinção fundamental entre a análise de algoritmos e a teoria da complexidade computacional é que a primeira é dedicada a analisar a quantidade de recursos necessários para um determinado algoritmo para resolver um problema, enquanto a segunda faz uma pergunta mais geral sobre todos os algoritmos possíveis que poderiam ser usados para resolver um problema. resolver o mesmo problema. Mais precisamente, a teoria da complexidade computacional tenta classificar problemas que podem ou não ser resolvidos com recursos adequadamente restritos. Por sua vez, impor restrições aos recursos disponíveis é o que distingue a complexidade computacional da teoria da computabilidade: esta última pergunta que tipos de problemas podem, em princípio, ser resolvidos algoritmicamente.

Problemas computacionais

Uma turnê de vendedores por 14 cidades alemãs.

Instâncias de problemas

Um problema computacional pode ser visto como uma coleção infinita de instâncias junto com um conjunto (possivelmente vazio) de soluções para cada instância. A string de entrada para um problema computacional é referida como uma instância do problema e não deve ser confundida com o próprio problema. Na teoria da complexidade computacional, um problema refere-se à questão abstrata a ser resolvida. Em contraste, uma instância desse problema é um enunciado bastante concreto, que pode servir como entrada para um problema de decisão. Por exemplo, considere o problema do teste de primalidade. A instância é um número (por exemplo, 15) e a solução é "sim" se o número for primo e "não" caso contrário (neste caso, 15 não é primo e a resposta é "não"). Dito de outra forma, a instância é uma entrada específica para o problema, e a solução é a saída correspondente à entrada dada.

Para destacar ainda mais a diferença entre um problema e uma instância, considere a seguinte instância da versão de decisão do problema do caixeiro viajante: Existe uma rota de no máximo 2.000 quilômetros passando por todas as 15 maiores cidades da Alemanha ? A resposta quantitativa para esta instância específica do problema é de pouca utilidade para resolver outras instâncias do problema, como pedir uma viagem de ida e volta por todos os locais em Milão cujo comprimento total seja de no máximo 10 km. Por esta razão, a teoria da complexidade aborda problemas computacionais e não instâncias de problemas particulares.

Representando instâncias de problemas

Ao considerar problemas computacionais, uma instância do problema é uma string sobre um alfabeto. Normalmente, o alfabeto é considerado o alfabeto binário (ou seja, o conjunto {0,1}) e, portanto, as strings são bitstrings. Como em um computador do mundo real, os objetos matemáticos que não sejam cadeias de bits devem ser codificados adequadamente. Por exemplo, inteiros podem ser representados em notação binária e grafos podem ser codificados diretamente por meio de suas matrizes de adjacência ou codificando suas listas de adjacência em binário.

Embora algumas provas de teoremas da teoria da complexidade assumam regularmente 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. Isso pode ser alcançado garantindo que diferentes representações possam ser transformadas umas nas outras de forma eficiente.

Problemas de decisão como linguagens formais

Um problema de decisão tem apenas duas saídas possíveis, Sim. ou Não. (ou alternadamente 1 ou 0) em qualquer entrada.

Problemas de decisão são um dos objetos centrais de estudo 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 saída é sim, e os não membros são aquelas instâncias cuja saída é não. O objetivo é decidir, com a ajuda de um algoritmo, se uma determinada string de entrada é membro da linguagem formal em questão. Se o algoritmo que decidiu este problema retornar a resposta sim, diz-se que o algoritmo aceita a string de entrada, caso contrário, diz-se que rejeita a entrada.

Um exemplo de um problema de decisão é o seguinte. A entrada é um gráfico arbitrário. O problema consiste em decidir se o grafo dado é conexo ou não. A linguagem formal associada a esse problema de decisão é então o conjunto de todos os grafos conectados — para obter uma definição precisa dessa linguagem, é preciso decidir como os grafos são codificados como strings binárias.

Problemas de funcionamento

Um problema de função é um problema computacional em que 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 - ou seja, a saída não é apenas sim ou não. Exemplos notáveis incluem o problema do caixeiro viajante e o problema de fatoração inteira.

É tentador pensar que a noção de problemas funcionais é muito mais rica do que a noção de problemas de decisão. No entanto, este não é realmente o caso, uma vez que os problemas de função podem ser reformulados como problemas de decisão. Por exemplo, a multiplicação de dois inteiros pode ser expressa como o conjunto de triplos (a, b, c) tal que a relação a × b = c detém. Decidir se um determinado triplo é membro desse conjunto corresponde a resolver o problema da multiplicação de dois números.

Medir o tamanho de uma instância

Para medir a dificuldade de resolver um problema computacional, pode-se desejar ver quanto tempo o melhor algoritmo requer 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 serem resolvidas. Assim, o tempo necessário para resolver um problema (ou o espaço necessário, ou qualquer medida de complexidade) é calculado em função do tamanho da instância. Isso geralmente é considerado o tamanho da entrada em bits. A teoria da complexidade está interessada em como os algoritmos escalam com um aumento no tamanho da entrada. Por exemplo, no problema de descobrir se um grafo é conectado, quanto tempo leva para resolver um problema para um grafo com 2n vértices em comparação com o tempo necessário para um grafo com n vértices?

Se o tamanho de entrada for n, o tempo gasto pode ser expresso como uma função de n. Como o tempo gasto em diferentes entradas do mesmo tamanho pode ser diferente, a complexidade de tempo de pior caso T(n) é definida como o tempo máximo gasto em todas as entradas de tamanho n. Se T(n) é um polinômio em n, então o algoritmo é dito ser um algoritmo de tempo polinomial. A tese de Cobham argumenta que um problema pode ser resolvido com uma quantidade viável de recursos se ele admitir um algoritmo de tempo polinomial.

Modelos de máquinas e medidas de complexidade

Máquina de Turing

Uma ilustração de uma máquina de Turing

Uma máquina de Turing é um modelo matemático de uma máquina de computação geral. É um dispositivo teórico que manipula símbolos contidos em uma tira de fita. As máquinas de Turing não pretendem ser uma tecnologia de computação prática, mas sim um modelo geral de uma máquina de computação - qualquer coisa, desde um supercomputador avançado até um matemático com lápis e papel. Acredita-se que se um problema pode ser resolvido por um algoritmo, existe uma máquina de Turing que resolve o problema. De fato, 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 que conhecemos hoje, como uma máquina RAM, o Jogo da Vida de Conway, autômatos celulares, cálculo lambda ou qualquer linguagem de programação pode ser computado em um Máquina de Turing. Como as máquinas de Turing são fáceis de analisar matematicamente e são consideradas tão poderosas quanto qualquer outro modelo de computação, a máquina de Turing é o modelo mais comumente usado na teoria da complexidade.

Muitos tipos de máquinas de Turing são usados para definir classes de complexidade, como máquinas de Turing determinísticas, máquinas de Turing probabilísticas, máquinas de Turing não determinísticas, máquinas de Turing quânticas, máquinas de Turing simétricas e máquinas de Turing alternadas. Eles são todos igualmente poderosos em princípio, mas quando os recursos (como tempo ou espaço) são limitados, alguns deles podem ser mais poderosos do que outros.

Uma máquina de Turing determinística é a máquina de Turing mais básica, que usa um conjunto fixo de regras para determinar suas ações futuras. Uma máquina de Turing probabilística é uma máquina de Turing determinística com um suprimento extra de bits aleatórios. A capacidade de tomar decisões probabilísticas geralmente ajuda os algoritmos a resolver problemas com mais eficiência. Algoritmos que usam bits aleatórios são chamados de algoritmos aleatórios. Uma máquina de Turing não determinística é uma máquina de Turing determinística com um recurso adicional de não determinismo, que permite que uma máquina de Turing tenha múltiplas ações futuras possíveis de um determinado estado. Uma maneira de ver o não-determinismo é que a máquina de Turing se ramifica em muitos caminhos computacionais possíveis a cada etapa e, se ela resolver o problema em qualquer uma dessas ramificações, diz-se que resolveu o problema. Claramente, este modelo não pretende ser um modelo fisicamente realizável, é apenas uma máquina abstrata teoricamente interessante que dá origem a classes de complexidade particularmente interessantes. Para obter exemplos, consulte algoritmo não determinístico.

Outros modelos de máquinas

Muitos modelos de máquina diferentes das máquinas de Turing multifita padrão foram propostos na literatura, por exemplo, máquinas de acesso aleatório. Talvez surpreendentemente, cada um desses modelos pode ser convertido em outro sem fornecer nenhum poder computacional extra. O consumo de tempo e memória desses modelos alternativos pode variar. O que todos esses modelos têm em comum é que as máquinas operam 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 que pode se ramificar para verificar muitas possibilidades diferentes ao mesmo tempo. A máquina de Turing não determinística tem muito pouco a ver com a forma como queremos computar algoritmos fisicamente, mas sua ramificação captura com exatidão 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 usando uma determinada quantidade de tempo e espaço, um modelo computacional como a máquina de Turing determinística é usado. O tempo requerido 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 emite a resposta ("sim" ou "não"). Diz-se que uma máquina de Turing M opera dentro do tempo f(n) se o tempo requerido por M em cada entrada de comprimento n é no máximo f(n). Um problema de decisão A pode ser resolvido no tempo f(n) se existir uma máquina de Turing operando no tempo f(n) que resolve o problema. Como a teoria da complexidade está interessada em classificar problemas com base em sua dificuldade, definem-se conjuntos de problemas com base em alguns critérios. Por exemplo, o conjunto de problemas solucionáveis dentro do tempo f(n) em uma máquina de Turing determinística é então denotado por DTIME(f(n)).

Definições análogas podem ser feitas para requisitos de espaço. Embora o tempo e o espaço sejam os recursos de complexidade mais conhecidos, qualquer medida de complexidade pode ser vista como um recurso computacional. As medidas de complexidade são geralmente definidas pelos axiomas de complexidade de Blum. Outras medidas de complexidade usadas na teoria da complexidade incluem complexidade de comunicação, complexidade de circuito e complexidade de árvore de decisão.

A complexidade de um algoritmo geralmente é expressa usando a notação O grande.

Melhor, pior e média complexidade do caso

Visualização do algoritmo de quicksort que tem desempenho médio do caso

{displaystyle {mathcal {O}}(nlog n)}

A complexidade do melhor, do pior e do caso médio refere-se a três maneiras diferentes de medir a complexidade de tempo (ou qualquer outra medida de complexidade) de diferentes entradas do mesmo tamanho. Como algumas entradas de tamanho n podem ser mais rápidas de resolver do que outras, definimos as seguintes complexidades:

Complexidade de melhor caso: Esta é a complexidade de resolver o problema para a melhor entrada de tamanho n.
Complexidade de casos médios: Esta é a complexidade de resolver o problema em média. Esta complexidade só é definida em relação a uma distribuição de probabilidade sobre as entradas. Por exemplo, se todas as entradas do mesmo tamanho forem consideradas igualmente susceptíveis de aparecer, a complexidade média do caso pode ser definida em relação à distribuição uniforme em todas as entradas de tamanho n.
Análise amortizada: A análise amortizada considera as operações dispendiosas e menos onerosas em conjunto sobre toda a série de operações do algoritmo.
A complexidade do pior caso: Esta é a complexidade de resolver o problema para a pior entrada de tamanho n.

A ordem do barato ao caro é: Melhor, média (de distribuição uniforme discreta), amortizada, pior.

Por exemplo, considere o algoritmo de ordenação determinístico quicksort. Isso resolve o problema de classificar uma lista de inteiros fornecida como entrada. O pior caso é quando o pivô é sempre o maior ou menor valor da lista (portanto, a lista nunca é dividida). Neste caso, o algoritmo leva tempo O(n²). Se assumirmos que todas as permutações possíveis da lista de entrada são igualmente prováveis, o tempo médio gasto para ordenação é O(n log n). O melhor caso ocorre quando cada pivô divide a lista ao meio, também precisando de tempo O(n log n).

Limites superiores e inferiores da complexidade dos problemas

Para classificar o tempo de computação (ou recursos semelhantes, como o consumo de espaço), é útil demonstrar os limites superior e inferior da quantidade máxima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo geralmente é considerada a complexidade de pior caso, a menos que especificado de outra forma. A análise de um algoritmo específico se enquadra no campo de análise de algoritmos. Para mostrar um limite superior T(n) na complexidade de tempo de um problema, é preciso mostrar apenas que existe um algoritmo específico com tempo de execução no máximo T(n). No entanto, provar limites inferiores é muito mais difícil, pois os limites inferiores fazem uma declaração sobre todos os algoritmos possíveis 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, é necessário mostrar que nenhum algoritmo pode ter complexidade de tempo menor que T( n).

Limites superiores e inferiores geralmente são indicados usando a grande notação O, que oculta fatores constantes e termos menores. Isso torna os limites independentes dos detalhes específicos do modelo computacional usado. Por exemplo, se T(n) = 7n² + 15n + 40, na notação O grande, escreveríamos T(n) = O(n²).

Aulas de complexidade

Definindo classes de complexidade

Uma classe de complexidade é um conjunto de problemas de complexidade relacionada. Classes de complexidade mais simples são definidas pelos seguintes fatores:

O tipo de problema computacional: Os problemas mais comumente usados são problemas de decisão. No entanto, classes de complexidade podem ser definidas com base em problemas de função, problemas de contagem, problemas de otimização, problemas de promessa, etc.
O modelo de computação: O modelo mais comum de computação é a máquina de Turing determinística, mas muitas classes de complexidade são baseadas em máquinas de Turing não determinística, circuitos booleanos, máquinas de Turing quântica, circuitos monotone, etc.
O recurso (ou recursos) que está sendo limitado e o limite: Estas duas propriedades são geralmente declaradas juntas, como "tempo polinomial", "espaço logarítmico", "profundidade constante", etc.

Algumas classes de complexidade têm definições complicadas que não se encaixam nessa estrutura. Assim, uma classe de complexidade típica tem uma definição como a seguinte:

O conjunto de problemas de decisão solvable por uma máquina de Turing deterministic dentro do tempo f(n). (Esta classe de complexidade é conhecida como DTIME(f(n)).

Mas limitar o tempo de computação acima por alguma função concreta f(n) geralmente produz classes de complexidade que dependem do modelo de máquina escolhido. Por exemplo, o idioma {xx | x é qualquer string binária} pode ser resolvido em tempo linear em uma máquina de Turing multi-fita, mas necessariamente requer tempo quadrático no modelo de máquinas de Turing de fita única. Se permitirmos variações polinomiais no tempo de execução, a tese de Cobham-Edmonds afirma que "as complexidades de tempo em quaisquer dois modelos razoáveis e gerais de computação são polinomialmente relacionadas" (Goldreich 2008, Capítulo 1.2). Isso forma a base para a classe de complexidade P, que é o conjunto de problemas de decisão solucionáveis por uma máquina de Turing determinística em tempo polinomial. O conjunto correspondente de problemas de função é FP.

Importantes classes de complexidade

Representação da relação entre classes de complexidade

Muitas classes de complexidade importantes podem ser definidas limitando o tempo ou espaço usado pelo algoritmo. Algumas classes de complexidade importantes de problemas de decisão definidos dessa maneira são as seguintes:

Classe de complexidade	Modelo de computação	Restrição de recursos
Tempo determinado
DTIME(f(n)	Máquina de Turing Deterministic	Tempo O (f(n)

P	Máquina de Turing Deterministic	Tempo O (poly(n)
EXPTIVO	Máquina de Turing Deterministic	Tempo O(2)^poli(n))
Tempo não determinístico
NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NT1 NTf(n)	Não determinístico Máquina de Turing	Tempo O (f(n)

PN	Não determinístico Máquina de Turing	Tempo O (poly(n)
NEXPTIMA	Não determinístico Máquina de Turing	Tempo O(2)^poli(n))

Classe de complexidade	Modelo de computação	Restrição de recursos
Espaço determinante
DSPACE (f(n)	Máquina de Turing Deterministic	Espaço O(f(n)
L	Máquina de Turing Deterministic	Espaço O (log n)
PSPACE	Máquina de Turing Deterministic	Espaço O(poli(n)
EXPSPACE	Máquina de Turing Deterministic	Espaço O(2^poli(n))
Espaço não determinístico
NSPACE(f(n)	Não determinístico Máquina de Turing	Espaço O(f(n)
Países Baixos	Não determinístico Máquina de Turing	Espaço O (log n)
NPSPACE	Não determinístico Máquina de Turing	Espaço O(poli(n)
NEXPSPA	Não determinístico Máquina de Turing	Espaço O(2^poli(n))

As classes de espaço logarítmico (necessariamente) não levam em conta o espaço necessário para representar o problema.

Acontece que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE pelo teorema de Savitch.

Outras classes importantes de complexidade incluem BPP, ZPP e RP, que são definidas usando máquinas de Turing probabilísticas; AC e NC, que são definidos usando circuitos booleanos; e BQP e QMA, que são definidos usando máquinas de Turing quânticas. #P é uma importante classe de complexidade de problemas de contagem (não problemas de decisão). Classes como IP e AM são definidas usando sistemas de prova interativos. 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 de (digamos) tempo de computação de fato define um conjunto maior de problemas. Em particular, embora DTIME(n) esteja contido em DTIME(n²), seria interessante saber se a inclusão é estrita. Para requisitos de tempo e espaço, a resposta a tais perguntas é dada pelos teoremas de hierarquia de tempo e espaço, respectivamente. Eles são chamados de teoremas de hierarquia porque induzem uma hierarquia adequada nas classes definidas pela restrição dos respectivos recursos. Assim, existem pares de classes de complexidade tais que uma está devidamente incluída na outra. Tendo deduzido tais inclusões apropriadas de conjuntos, podemos proceder para fazer afirmações quantitativas sobre quanto tempo ou espaço adicional é necessário para aumentar o número de problemas que podem ser resolvidos.

Mais precisamente, o teorema da hierarquia de tempo afirma que

{displaystyle {mathsf {DTIME}}{big (}f(n){big)}subsetneq {mathsf {DTIME}}{big (}f(n)cdot log ^{2}(f(n)){big)}}

O teorema da hierarquia espacial afirma que

{displaystyle {mathsf {DSPACE}}{big (}f(n){big)}subsetneq {mathsf {DSPACE}}{big (}f(n)cdot log(f(n)){big)}}

Os teoremas de hierarquia de tempo e espaço formam a base para a maioria dos resultados de separação de classes de complexidade. Por exemplo, o teorema da hierarquia de tempo nos diz que P está estritamente contido em EXPTIME, e o teorema da hierarquia de espaço nos diz que L está estritamente contido em PSPACE.

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. Ele captura a noção informal de um problema sendo no máximo 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 reduz a Y. Existem muitos tipos diferentes de reduções, com base no método de redução, como reduções de Cook, reduções de Karp e reduções de Levin, e o limite da complexidade das reduções, como reduções de tempo polinomial ou reduções de espaço logarítmico.

A redução mais comumente usada é uma redução de tempo polinomial. Isso significa que o processo de redução leva tempo polinomial. Por exemplo, o problema de elevar ao quadrado um inteiro pode ser reduzido ao problema de multiplicar dois inteiros. Isso significa que um algoritmo para multiplicar dois números inteiros pode ser usado para elevar ao quadrado um número inteiro. Na verdade, isso pode ser feito dando a mesma entrada para ambas as entradas do algoritmo de multiplicação. Assim, vemos que o quadrado não é mais difícil do que a multiplicação, pois o quadrado pode ser reduzido à multiplicação.

Isso motiva o conceito de um problema ser difícil para uma classe de complexidade. Um problema X é difícil para uma classe de problemas C se todos os problemas em C puderem ser reduzidos a X. Portanto, nenhum problema em C é mais difícil que X, pois um algoritmo para X nos permite resolver qualquer problema em C. A noção de problemas difíceis depende do tipo de redução que está sendo usado. Para classes de complexidade maiores que P, as reduções de tempo polinomial são comumente usadas. Em particular, o conjunto de problemas difíceis para NP é o conjunto de problemas NP-difíceis.

Se um problema X está em C e difícil para C, então X é dito ser completo para C. Isso significa que X é o problema mais difícil em C. (Como muitos problemas podem ser igualmente difíceis, pode-se dizer que X é um dos problemas mais difíceis em C.) Assim, a classe de problemas NP-completos contém os problemas mais difíceis problemas em NP, no sentido de que são os que mais provavelmente não estão em P. Porque o problema P = NP não é resolvido, podendo reduzir um problema NP-completo conhecido, Π₂, para outro problema, Π₁, indicaria que não há solução conhecida em tempo polinomial para Π₁. Isso ocorre porque uma solução em tempo polinomial para Π₁ resultaria em uma solução em tempo polinomial para Π₂. Da mesma forma, como todos os problemas NP podem ser reduzidos ao conjunto, encontrar um problema NP-completo que possa ser resolvido em tempo polinomial significaria que P = NP.

Problemas importantes em aberto

Diagrama de classes de complexidade desde que P ≠ NP. A existência de problemas em NP fora de P e NP-completo neste caso foi estabelecida por Ladner.

Problema P versus NP

A classe de complexidade P é muitas vezes vista como uma abstração matemática modelando aquelas tarefas computacionais que admitem um algoritmo eficiente. Essa 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 de satisfazibilidade booleana, o problema de caminho hamiltoniano e o problema de cobertura de vértices. Como as máquinas de Turing determinísticas 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.

A questão de saber se P é igual a NP é uma das questões em aberto mais importantes na ciência da computação teórica devido às amplas implicações de uma solução. Se a resposta for sim, pode-se mostrar que muitos problemas importantes têm soluções mais eficientes. Isso inclui vários tipos de problemas de programação inteira em pesquisa operacional, muitos problemas em logística, previsão de estrutura de proteínas em biologia e a capacidade de encontrar provas formais de teoremas de matemática pura. O problema P versus NP é um dos Problemas do Prêmio do Milênio propostos pelo Clay Mathematics Institute. Há um prêmio de US$ 1.000.000 para quem resolver o problema.

Problemas em NP não conhecidos por estarem em P ou NP-completo

Foi mostrado por Ladner que se P ≠ NP então existem problemas em NP que não estão em P nem NP-completo. Tais problemas são chamados de problemas NP-intermediários. O problema do isomorfismo de grafos, o problema do logaritmo discreto e o problema da fatoração inteira são exemplos de problemas considerados NP-intermediários. Eles são alguns dos poucos problemas NP não conhecidos como P ou NP-completos.

O problema do isomorfismo do gráfico é o problema computacional de determinar se dois gráficos finitos são isomorfos. Um importante problema não resolvido na teoria da complexidade é se o problema do isomorfismo do grafo está em P, NP-completo, ou NP-intermediário. A resposta não é conhecida, mas acredita-se que o problema não é pelo menos NP-completo. Se o isomorfismo do grafo é NP-completo, a hierarquia do tempo polinomial colapsa ao seu segundo nível. Uma vez que é amplamente acreditado que a hierarquia polinomial não colapsa a nenhum nível finito, acredita-se que o isomorfismo de grafo não é NP-completo. O melhor algoritmo para este problema, devido a László Babai e Eugene Luks tem tempo de execução ${displaystyle O(2^{sqrt {nlog n}})}$ para gráficos com n vértices, embora alguns trabalhos recentes de Babai ofereçam algumas perspectivas potencialmente novas sobre isso.

O problema da fatoração do inteiro é o problema computacional de determinar a fatoração principal de um determinado inteiro. Fraseado como um problema de decisão, é o problema de decidir se a entrada tem um fator principal menos do que k. Nenhum algoritmo de fatoração de inteiro eficiente é conhecido, e este fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA. O problema da fatoração por inteiro está em PN e em co-NP (e mesmo em UP e co-UP). Se o problema for NP-completo, a hierarquia do tempo polinomial entrará em colapso em seu primeiro nível (i.e., PN igual co-NP). O algoritmo mais conhecido para a fatoração integer é a peneira de campo de número geral, que leva tempo ${displaystyle O(e^{left({sqrt[{3}]{frac {64}{9}}}right){sqrt[{3}]{(log n)}}{sqrt[{3}]{(log log n)^{2}}}})}$ para fatorar um inteiro estranho n. No entanto, o algoritmo quântico mais conhecido para este problema, o algoritmo de Shor, funciona em tempo polinomial. Infelizmente, este fato nÃ£o diz muito sobre onde o problema reside no respeito Ã s classes de complexidade nÃ£o-quantum.

Separações entre outras classes de complexidade

Suspeita-se que muitas classes de complexidade conhecidas sejam desiguais, mas isso não foi provado. Por exemplo P ⊆ NP ⊆ PP ⊆ PSPACE, mas é possível que P = ESPAÇO. Se P não for igual a NP, então P também não será igual a PSPACE. Como existem muitas classes de complexidade conhecidas entre P e PSPACE, como RP, BPP, PP , BQP, MA, PH, etc., é possível que todas essas classes de complexidade se reduzam a uma classe. Provar que qualquer uma dessas classes é desigual seria um grande avanço na teoria da complexidade.

Na mesma linha, co-NP é a classe que contém os problemas de complemento (ou seja, problemas com as respostas sim/não invertidas) de problemas NP. Acredita-se que NP não seja igual a co-NP; no entanto, ainda não foi provado. É claro que se essas duas classes de complexidade não forem iguais, então P não é igual a NP, pois P=co-P . Assim se P=NP teríamos co-P=co-NP de onde NP=P=co-P=co-NP.

Da mesma forma, não se sabe se L (o conjunto de todos os problemas que podem ser resolvidos no espaço logarítmico) está estritamente contido em P ou igual a P. Novamente, existem muitas classes de complexidade entre as duas, como NL e NC, e não se sabe se são classes distintas ou iguais.

Suspeita-se que P e BPP sejam iguais. No entanto, está atualmente aberto se BPP = NEXP.

Intratabilidade

Um problema que pode ser resolvido em teoria (por exemplo, com recursos grandes, mas finitos, especialmente tempo), mas para o qual, na prática, qualquer solução requer muitos recursos para ser útil, é conhecido como problema intratável. Por outro lado, um problema que pode ser resolvido na prática é chamado de tratável problema, literalmente "um problema que pode ser resolvido". O termo inviável (literalmente "não pode ser feito") às vezes é usado como sinônimo de intratável, embora haja risco de confusão com uma solução viável em otimização matemática.

Problemas tratáveis são frequentemente identificados com problemas que possuem soluções em tempo polinomial (P, PTIME); isso é conhecido como a tese de Cobham-Edmonds. Problemas que são conhecidos por serem intratáveis neste sentido incluem aqueles que são EXPTIME-difíceis. Se NP não é o mesmo que P, então problemas NP-difíceis também são intratáveis nesse sentido.

No entanto, esta identificação é inexata: uma solução em tempo polinomial com grau grande ou coeficiente líder grande cresce rapidamente e pode ser impraticável para problemas práticos de tamanho; por outro lado, uma solução de tempo exponencial que cresce lentamente pode ser prática em entradas realistas, ou uma solução que leva muito tempo no pior caso pode levar pouco tempo na maioria dos casos ou no caso médio e, portanto, ainda ser prática. Dizer que um problema não está em P não implica que todos os grandes casos do problema sejam difíceis ou mesmo que a maioria deles seja. Por exemplo, foi demonstrado que o problema de decisão na aritmética de Presburger não está em P, mas foram escritos algoritmos que resolvem o problema em tempos razoáveis na maioria dos casos. Da mesma forma, os algoritmos podem resolver o problema da mochila NP-completo em uma ampla gama de tamanhos em menos de tempo quadrático e os solucionadores SAT lidam rotineiramente com grandes instâncias do problema de satisfatibilidade booleana NP-completo.

Para ver por que os algoritmos de tempo exponencial são geralmente inutilizáveis na prática, considere um programa que faz 2ⁿ operações antes de parar. Para n pequenos, digamos 100, e assumindo, por exemplo, que o computador faz 10¹² operações a cada segundo, o programa seria executado por cerca de 4 × 10¹⁰ anos, que é a mesma ordem de grandeza da idade do universo. Mesmo com um computador muito mais rápido, o programa só seria útil para instâncias muito pequenas e, nesse sentido, a intratabilidade de um problema é um tanto independente do progresso tecnológico. No entanto, um algoritmo de tempo exponencial que leva 1,0001ⁿ operações é prático até que n fique relativamente grande.

Da mesma forma, um algoritmo de tempo polinomial nem sempre é prático. Se seu tempo de execução for, digamos, n¹⁵, não é razoável considerá-lo eficiente e ainda é inútil, exceto em instâncias pequenas. De fato, na prática, mesmo os algoritmos n³ ou n² geralmente são impraticáveis em tamanhos realistas de problemas.

Teoria da complexidade contínua

A teoria da complexidade contínua pode se referir à teoria da complexidade de problemas que envolvem funções contínuas que são aproximadas por discretizações, conforme estudado na análise numérica. Uma abordagem para a teoria da complexidade da análise numérica é a complexidade baseada em informações.

A teoria da complexidade contínua também pode se referir à teoria da complexidade do uso de computação analógica, que usa sistemas dinâmicos contínuos e equações diferenciais. A teoria de controle pode ser considerada uma forma de computação e as equações diferenciais são usadas na modelagem de sistemas de tempo contínuo e híbridos de tempo discreto-contínuo.

História

Um dos primeiros exemplos de análise de complexidade de algoritmo é a análise de tempo de execução do algoritmo euclidiano feita por Gabriel Lamé em 1844.

Antes que a pesquisa real explicitamente dedicada à complexidade dos problemas algorítmicos começasse, vários fundamentos foram estabelecidos por vários pesquisadores. A mais influente delas foi a definição de máquinas de Turing por Alan Turing em 1936, que se tornou uma simplificação muito robusta e flexível de um computador.

O início dos estudos sistemáticos em complexidade computacional é atribuído ao artigo seminal de 1965 "On the Computational Complexity of Algorithms" por Juris Hartmanis e Richard E. Stearns, que estabeleceu as definições de complexidade de tempo e complexidade de espaço e provou os teoremas de hierarquia. Além disso, em 1965 Edmonds sugeriu considerar um "bom" algoritmo para ser um com tempo de execução limitado por um polinômio do tamanho de entrada.

Artigos anteriores estudando problemas solucionáveis por máquinas de Turing com recursos limitados específicos incluem a definição de autômatos lineares limitados de John Myhill (Myhill 1960), o estudo de conjuntos rudimentares de Raymond Smullyan (1961), bem como Hisao Artigo de Yamada sobre cálculos em tempo real (1962). Um pouco antes, Boris Trakhtenbrot (1956), um pioneiro na área da URSS, estudou outra medida de complexidade específica. Como ele lembra:

No entanto, [meu] interesse inicial [em teoria automata] foi cada vez mais afastado em favor da complexidade computacional, uma fusão emocionante de métodos combinatórios, herdada da teoria de comutação, com o arsenal conceitual da teoria dos algoritmos. Essas ideias me ocorreram no início de 1955 quando eu cunho o termo "função de sinalização", que é hoje em dia comumente conhecido como "medida de complexidade".

Em 1967, Manuel Blum formulou um conjunto de axiomas (agora conhecidos como axiomas de Blum) especificando propriedades desejáveis de medidas de complexidade no conjunto de funções computáveis e provou um resultado importante, o chamado teorema de aceleração. O campo começou a florescer em 1971, quando Stephen Cook e Leonid Levin provaram a existência de problemas praticamente relevantes que são NP-completos. Em 1972, Richard Karp deu um salto adiante com essa ideia com seu artigo de referência, "Reducibility Among Combinatorial Problems", no qual ele mostrou que 21 diversos problemas combinatórios e teóricos de grafos, cada um famoso por sua intratabilidade computacional, são NP -completo.

Trabalha na complexidade

Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, doi:10.1142/11270, ISBN 978-981-12-0006-9, S2CID 198790362

Contenido relacionado

Más resultados...