Teoria da complexidade computacional - Computational complexity theory

A teoria da complexidade computacional se concentra em classificar problemas computacionais de acordo com o uso de recursos e relacionar essas classes entre si. 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 sua solução requer recursos significativos, qualquer que seja o algoritmo usado. A teoria formaliza essa intuição, ao introduzir modelos matemáticos de computação para estudar esses problemas e quantificar 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 (usados ​​na computação paralela ). Uma das funções da teoria da complexidade computacional é determinar os limites práticos do que os computadores podem ou não fazer. O problema P versus NP , um dos sete problemas do Prêmio Millennium , é 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 se dedica a analisar a quantidade de recursos necessários para um algoritmo específico para resolver um problema, enquanto a última faz uma pergunta mais geral sobre todos os algoritmos possíveis que poderiam ser usados ​​para resolver o mesmo problema. Mais precisamente, a teoria da complexidade computacional tenta classificar problemas que podem ou não podem ser resolvidos com recursos apropriadamente restritos. Por sua vez, a imposição de restrições aos recursos disponíveis é o que distingue a complexidade computacional da teoria da computabilidade: a última teoria pergunta que tipos de problemas podem, em princípio, ser resolvidos algoritmicamente.

Problemas computacionais

Viagem de caixeiro-viajante por 14 cidades alemãs.

Instâncias problemáticas

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 é chamada de instância de problema e não deve ser confundida com o problema em si. Na teoria da complexidade computacional, um problema se refere à 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 fornecida.

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 de problema em particular é de pouca utilidade para resolver outras instâncias do problema, como solicitar uma viagem de ida e volta por todos os locais em Milão cujo comprimento total é de no máximo 10 km. Por esta razão, a teoria da complexidade trata de problemas computacionais e não de instâncias de problemas particulares.

Representando instâncias problemáticas

Ao considerar problemas computacionais, uma instância de 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 bitstrings devem ser adequadamente codificados. Por exemplo, os inteiros podem ser representados em notação binária e os gráficos podem ser codificados diretamente por meio de suas matrizes de adjacência ou pela codificação de suas listas de adjacência em binário.

Mesmo que algumas provas de teoremas da teoria da complexidade regularmente assumam alguma escolha concreta de codificação de entrada, tenta-se manter a discussão abstrata o suficiente para ser independente da escolha de codificação. Isso pode ser alcançado garantindo que diferentes representações possam ser transformadas umas nas outras com eficiência.

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 o auxílio de um algoritmo , se uma dada string de entrada é um membro da linguagem formal em consideração. Se o algoritmo que está decidindo esse problema retornar a resposta sim , diz-se que o algoritmo aceita a string de entrada, caso contrário, diz que rejeita a entrada.

Um exemplo de problema de decisão é o seguinte. A entrada é um gráfico arbitrário . O problema consiste em decidir se um dado grafo está conectado 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 cadeias binárias.

Problemas de função

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 da 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, esse 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 ) de modo que a relação a  ×  b  =  c seja mantida. Decidir se um dado 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. Porém, 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 são escalonados com um aumento no tamanho da entrada. Por exemplo, no problema de descobrir se um gráfico está conectado, quanto tempo mais leva para resolver um problema para um gráfico com 2 n vértices em comparação com o tempo gasto para um gráfico com n vértices?

Se o tamanho da entrada for n , o tempo gasto pode ser expresso como uma função de n . Uma vez que 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 é considerado um algoritmo de tempo polinomial . A tese de Cobham argumenta que um problema pode ser resolvido com uma quantidade viável de recursos se 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 se destinam a 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 a um matemático com um 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. Na verdade, esta é a declaraçã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 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 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 a uma máquina de Turing ter várias ações futuras possíveis a partir 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 em cada etapa e, se ela resolve 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 exemplos, consulte algoritmo não determinístico .

Outros modelos de máquina

Muitos modelos de máquinas diferentes das máquinas de Turing de fita múltipla padrão têm sido 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 tempo e o consumo de memória desses modelos alternativos podem 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 de uma vez. 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 exatamente muitos dos modelos matemáticos que desejamos 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 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 realiza antes de parar e dar 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 houver uma máquina de Turing operando no tempo f ( n ) que resolva o problema. Visto que a teoria da complexidade está interessada em classificar problemas com base em sua dificuldade, define-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 a complexidade da comunicação , a complexidade do circuito e a complexidade da árvore de decisão .

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

Complexidade de caso melhor, pior e média

Visualização do algoritmo de classificação rápida que tem desempenho médio de caso . ${\ displaystyle {\ mathcal {O}} (n \ log n)}$

O melhor, o pior caso e a complexidade média referem-se a três maneiras diferentes de medir a complexidade do 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:

1. Complexidade do melhor caso: Esta é a complexidade de resolver o problema para a melhor entrada de tamanho n .
2. Complexidade de caso médio: Esta é a complexidade de resolver o problema em média. Essa complexidade é definida apenas em relação a uma distribuição de probabilidade sobre as entradas. Por exemplo, se todas as entradas do mesmo tamanho são assumidas como tendo a mesma probabilidade de aparecer, a complexidade média do caso pode ser definida com respeito à distribuição uniforme sobre todas as entradas de tamanho n .
3. Análise amortizada : a análise amortizada considera as operações mais caras e menos caras ao longo de toda a série de operações do algoritmo.
4. Complexidade de pior caso: Esta é a complexidade de resolver o problema para a pior entrada de tamanho n .

A ordem de barato para caro é: Melhor, médio (de distribuição uniforme discreta ), amortizado, pior.

Por exemplo, considere o algoritmo de classificação determinística quicksort . Isso resolve o problema de ordenar uma lista de inteiros que é fornecida como entrada. O pior caso é quando o pivô é sempre o maior ou o menor valor da lista (portanto, a lista nunca é dividida). Nesse 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 classificação é O ( n log n ). O melhor caso ocorre quando cada pivotamento divide a lista pela metade, também precisando de tempo O ( n log n ).

Limites superior e inferior na complexidade dos problemas

Para classificar o tempo de computação (ou recursos semelhantes, como 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 como seu pior caso de complexidade, a menos que especificado de outra forma. A análise de um determinado algoritmo cai no campo da análise de algoritmos . Para mostrar um limite superior T ( n ) na complexidade de tempo de um problema, é necessário mostrar apenas que existe um algoritmo particular com tempo de execução no máximo T ( n ). No entanto, provar os limites inferiores é muito mais difícil, uma vez que 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 inferior a T ( n ).

Os limites superior e inferior são geralmente declarados usando a notação grande 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 ) = 7 n ²  + 15 n  + 40, em grande notação O escreveríamos T ( n ) = O ( n ² ).

Classes 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 os problemas de decisão. No entanto, as 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 de computação mais comum é a máquina de Turing determinística, mas muitas classes de complexidade são baseadas em máquinas de Turing não determinísticas, circuitos booleanos , máquinas de Turing quânticas , circuitos monótonos , etc.
• O recurso (ou recursos) que está sendo limitado e o limite: essas duas propriedades geralmente são 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 nesta estrutura. Assim, uma classe de complexidade típica tem uma definição como a seguinte:

O conjunto de problemas de decisão solucionáveis ​​por uma máquina de Turing determinística dentro do tempo f ( n ). (Esta classe de complexidade é conhecida como DTIME ( f ( n )).)

Mas limitar o tempo de cálculo 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 de fita múltipla, 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 do 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 .

Classes de complexidade importantes

Uma representação da relação entre as classes de complexidade

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

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

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í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 no (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 questões é 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. Portanto, existem pares de classes de complexidade, de modo que uma é incluída adequadamente na outra. Tendo deduzido essas inclusões de conjuntos adequadas, podemos prosseguir para fazer afirmações quantitativas sobre quanto mais tempo ou espaço adicional é necessário para aumentar o número de problemas que podem ser resolvidos.

Mais precisamente, o teorema da hierarquia do 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 )){\grande )}}$.

Os teoremas da 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 é a transformação de um problema em outro problema. Ele captura a noção informal de que um problema é no máximo tão difícil quanto outro problema. Por exemplo, se um problema X podem ser resolvidos 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 na 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 um 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 inteiros pode ser usado para elevar ao quadrado um inteiro. Na verdade, isso pode ser feito fornecendo a mesma entrada para ambas as entradas do algoritmo de multiplicação. Assim, vemos que a quadratura não é mais difícil do que a multiplicação, uma vez que a quadratura pode ser reduzida à 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 cada problema em C pode ser reduzido a X . Assim, não há problema em C é mais difícil do que X , uma vez que 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 usada. Para classes de complexidade maiores que P, 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 para ser completo para C . Isto significa que X é o mais difícil problema em C . (Uma vez que 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 em NP, no sentido de que eles são os mais prováveis não estar em P. Como o problema P = NP não foi resolvido, ser capaz de reduzir um problema NP-completo conhecido, Π ₂ , a outro problema, Π ₁ , indicaria que não há solução em tempo polinomial conhecida 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 pode ser resolvido em tempo polinomial significaria que P = NP.

Problemas abertos importantes

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 é freqüentemente 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 satisfatibilidade 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, é facilmente observado 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 por causa das amplas implicações de uma solução. Se a resposta for sim, muitos problemas importantes podem ter 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 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-completos . Esses problemas são chamados de problemas intermediários NP . O problema do isomorfismo de grafos , o problema do logaritmo discreto e o problema da fatoração de inteiros são exemplos de problemas que se acredita serem NP-intermediários. Eles são alguns dos poucos problemas NP que não se sabe estarem em P ou como NP-completos .

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

O problema de fatoração de inteiros é o problema computacional de determinar a fatoração principal de um dado inteiro. Formulado como um problema de decisão, é o problema de decidir se a entrada tem um fator primo menor que k . Nenhum algoritmo de fatoração de números inteiros eficiente é conhecido, e esse fato forma a base de vários sistemas criptográficos modernos, como o algoritmo RSA . O problema de fatoração de inteiros está em NP e em co-NP (e mesmo em UP e co-UP). Se o problema for NP-completo , a hierarquia de tempo polinomial entrará em colapso para seu primeiro nível (ou seja, NP será igual a co-NP ). O algoritmo mais conhecido para fatoração de inteiros é a peneira de campo de número geral , que leva tempo para fatorar um inteiro ímpar n . No entanto, o algoritmo quântico mais conhecido para esse problema, o algoritmo de Shor , é executado em tempo polinomial. Infelizmente, esse fato não diz muito sobre onde está o problema com relação às classes de complexidade não quântica. ${\ displaystyle O (e ^ {\ left ({\ sqrt [{3}] {\ frac {64} {9}}} \ right) {\ sqrt [{3}] {(\ log n)}} { \ sqrt [{3}] {(\ log \ log n) ^ {2}}}})}$

Separações entre outras classes de complexidade

Muitas classes de complexidade conhecidas são suspeitas de serem desiguais, 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 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 colapsem em 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) dos problemas NP . Acredita-se que NP não seja igual a co-NP ; no entanto, ainda não foi comprovado. É 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 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ítmica) é estritamente contido em P ou igual a P . Novamente, existem muitas classes de complexidade entre os dois, 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, dados grandes, mas finitos recursos, especialmente tempo), mas para o qual na prática qualquer solução requer muitos recursos para ser útil, é conhecido como um problema intratável . Por outro lado, um problema que pode ser resolvido na prática é chamado deproblema tratável , literalmente "um problema que pode ser tratado". O termo inviável (literalmente "não pode ser feito") às vezes é usado de forma intercambiável com intratável , embora isso possa ser confundido com umasolução viávelemotimização matemática.

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

No entanto, essa identificação é inexata: uma solução de tempo polinomial com alto grau ou grande coeficiente líder cresce rapidamente e pode ser impraticável para problemas práticos de tamanho; inversamente, uma solução de tempo exponencial que cresce lentamente pode ser prática em dados realistas, ou uma solução que leva muito tempo no pior caso pode levar um tempo curto 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, o problema de decisão na aritmética de Presburger mostrou não estar em P, embora algoritmos tenham sido escritos para resolver 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 do que o tempo quadrático e os solucionadores SAT rotineiramente lidam 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 pequeno , digamos 100, e supondo, por exemplo, que o computador faça 10 ¹² operações a cada segundo, o programa seria executado por cerca de 4 × 10 ¹⁰ anos, que é a mesma ordem de magnitude que a 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 se torne 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 pequenas instâncias. De fato, na prática, mesmo n ³ ou n ² algoritmos são freqüentemente 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 da teoria da complexidade da análise numérica é a complexidade baseada na informação .

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 exemplo inicial 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 do início da pesquisa real explicitamente dedicada à complexidade dos problemas algorítmicos, várias bases foram estabelecidas por vários pesquisadores. O mais influente entre eles foi a definição de máquinas de Turing por Alan Turing em 1936, que acabou sendo 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 "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard E. Stearns , de 1965 , que expôs 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 algoritmo "bom" como aquele cujo 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 John Myhill de autômatos lineares limitados (Myhill 1960), o estudo de Raymond Smullyan de conjuntos rudimentares (1961), bem como o artigo de Hisao Yamada sobre real- cálculos de tempo (1962). Um pouco antes, Boris Trakhtenbrot (1956), um pioneiro na área da URSS, estudou outra medida de complexidade específica. Como ele se lembra:

No entanto, [meu] interesse inicial [na teoria dos autômatos] foi cada vez mais deixado de lado em favor da complexidade computacional, uma excitante fusão 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 cunhei 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 da 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 nessa ideia com seu artigo de referência, "Reducibility entre Combinatorial Problems", no qual ele mostrou que 21 problemas combinatórios e teóricos de gráficos diversos , cada um deles infame por sua intratabilidade computacional, são NP-completos.

Veja também

Trabalha na complexidade

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

Referências

Citações

Livros didáticos

• Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge University Press, ISBN 978-0-521-42426-4, Zbl  1193.68112
• Downey, Rod; Fellows, Michael (1999), Complexidade parametrizada , Monografias em Ciência da Computação, Berlim, Nova York: Springer-Verlag, ISBN 9780387948836
• Du, Ding-Zhu; Ko, Ker-I (2000), Teoria da Complexidade Computacional , John Wiley & Sons, ISBN 978-0-471-34506-0
• 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
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective , Cambridge University Press
• van Leeuwen, Jan , ed. (1990), Manual de ciência da computação teórica (vol. A): algoritmos e complexidade , MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (1ª ed.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Introdução à Teoria da Computação (2ª ed.), EUA: Thomson Course Technology, ISBN 978-0-534-95097-2

pesquisas

• Khalil, Hatem; Ulery, Dana (1976), "A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations" , Proceedings of the Annual Conference on - ACM 76 , ACM '76: 197–201, doi : 10.1145 / 800191.805573 , S2CID  15497394
• Cook, Stephen (1983), "Uma visão geral da complexidade computacional", Commun. ACM , 26 (6): 400-408, doi : 10.1145 / 358141.358144 , ISSN  0001-0782 , S2CID  14323396
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity" (PDF) , Bulletin of the EATCS , 80 : 95-133
• Mertens, Stephan (2002), "Computational Complexity for Physicists", Computing in Science and Eng. , 4 (3): 31-47, arXiv : cond-mat / 0012185 , bibcode : 2002CSE ..... 4c..31M , doi : 10,1109 / 5992,998639 , ISSN  1521-9615 , S2CID  633346

links externos

• The Complexity Zoo
• "Classes de complexidade computacional" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Quais são os resultados (e artigos) mais importantes na teoria da complexidade que todos devem saber?
• Scott Aaronson: por que os filósofos devem se preocupar com a complexidade computacional