b'\n_START_ARTICLE_\nComplexidade computacional\n_START_PARAGRAPH_\nA teoria da complexidade computacional \xc3\xa9 um ramo da teoria da computa\xc3\xa7\xc3\xa3o em ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o te\xc3\xb3rica e matem\xc3\xa1tica que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si. Neste contexto, um problema computacional \xc3\xa9 entendido como uma tarefa que \xc3\xa9, em princ\xc3\xadpio, pass\xc3\xadvel de ser resolvida por um computador (o que basicamente significa que o problema pode ser descrito por um conjunto de instru\xc3\xa7\xc3\xb5es matem\xc3\xa1ticas). Informalmente, um problema computacional consiste de inst\xc3\xa2ncias do problema e solu\xc3\xa7\xc3\xb5es para essas inst\xc3\xa2ncias do problema. Por exemplo, o teste de primalidade \xc3\xa9 o problema de determinar se um dado n\xc3\xbamero \xc3\xa9 primo ou n\xc3\xa3o. As inst\xc3\xa2ncias deste problema s\xc3\xa3o n\xc3\xbameros naturais, e a solu\xc3\xa7\xc3\xa3o para uma inst\xc3\xa2ncia \xc3\xa9 sim ou n\xc3\xa3o, dependendo se o n\xc3\xbamero \xc3\xa9 primo ou n\xc3\xa3o._NEWLINE_Um problema \xc3\xa9 considerado como inerentemente dif\xc3\xadcil se a sua solu\xc3\xa7\xc3\xa3o requer recursos significativos, qualquer que seja o algoritmo usado. A teoria formaliza esta intui\xc3\xa7\xc3\xa3o atrav\xc3\xa9s da introdu\xc3\xa7\xc3\xa3o de modelos matem\xc3\xa1ticos de computa\xc3\xa7\xc3\xa3o para estudar estes problemas e quantificar os recursos necess\xc3\xa1rios para resolv\xc3\xaa-los, tais como tempo e armazenamento. Outras medidas de complexidade tamb\xc3\xa9m s\xc3\xa3o utilizadas, tais como a quantidade de comunica\xc3\xa7\xc3\xa3o (usada em complexidade de comunica\xc3\xa7\xc3\xa3o), o n\xc3\xbamero de portas em um circuito (usado na complexidade de circuito) e o n\xc3\xbamero de processadores (usados em computa\xc3\xa7\xc3\xa3o paralela). Um dos pap\xc3\xa9is da teoria da complexidade computacional \xc3\xa9 determinar os limites pr\xc3\xa1ticos do que os computadores podem e n\xc3\xa3o podem fazer._NEWLINE_Campos intimamente relacionados com a ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o te\xc3\xb3rica s\xc3\xa3o a an\xc3\xa1lise de algoritmos e a teoria da computabilidade. Uma distin\xc3\xa7\xc3\xa3o chave entre a an\xc3\xa1lise de algoritmos e teoria da complexidade computacional \xc3\xa9 que a primeira \xc3\xa9 dedicada a analisar a quantidade de recursos necess\xc3\xa1rios para um determinado algoritmo resolver um problema, enquanto o segundo faz uma pergunta mais geral sobre todos os poss\xc3\xadveis algoritmos que podem ser usados para resolver o mesmo problema. Mais precisamente, ele tenta classificar os problemas que podem ou n\xc3\xa3o podem ser resolvidos com os recursos devidamente restritos. Por sua vez, impondo restri\xc3\xa7\xc3\xb5es sobre os recursos dispon\xc3\xadveis \xc3\xa9 o que distingue a complexidade computacional da teoria da computabilidade: a segunda pergunta que tipos de problemas podem, em princ\xc3\xadpio, ser resolvidos atrav\xc3\xa9s de algoritmos.\n_START_SECTION_\nInst\xc3\xa2ncias de Problema\n_START_PARAGRAPH_\nUm problema computacional pode ser visto como uma cole\xc3\xa7\xc3\xa3o infinita de inst\xc3\xa2ncias em conjunto com uma solu\xc3\xa7\xc3\xa3o para cada inst\xc3\xa2ncia. A sequ\xc3\xaancia de entrada para um problema computacional \xc3\xa9 referido como uma inst\xc3\xa2ncia do problema, e n\xc3\xa3o deve ser confundido com o problema em si. Na teoria da complexidade computacional, um problema se refere \xc3\xa0 quest\xc3\xa3o abstrata para ser resolvido. Em contraste, uma inst\xc3\xa2ncia deste problema \xc3\xa9 uma express\xc3\xa3o concreta, que pode servir como entrada para um problema de decis\xc3\xa3o. Por exemplo, considere o problema de teste de primalidade. A inst\xc3\xa2ncia \xc3\xa9 um n\xc3\xbamero (por exemplo, 10) e a solu\xc3\xa7\xc3\xa3o \xc3\xa9 "sim" se o n\xc3\xbamero \xc3\xa9 primo e "n\xc3\xa3o" se for o contr\xc3\xa1rio (neste caso "n\xc3\xa3o"). Alternativamente, a inst\xc3\xa2ncia \xc3\xa9 uma entrada especial para o problema, e a solu\xc3\xa7\xc3\xa3o \xc3\xa9 a sa\xc3\xadda correspondente \xc3\xa0 entrada._NEWLINE_Para real\xc3\xa7ar ainda mais a diferen\xc3\xa7a entre um problema e uma inst\xc3\xa2ncia, considere a seguinte inst\xc3\xa2ncia da vers\xc3\xa3o de decis\xc3\xa3o do problema do caixeiro viajante: Existe um percurso de, no m\xc3\xa1ximo, 2000\xc2\xa0km de comprimento passando por todas as 15 maiores cidades da Alemanha? A resposta a esta determinada inst\xc3\xa2ncia do problema \xc3\xa9 de pouca utilidade para a resolu\xc3\xa7\xc3\xa3o de outras inst\xc3\xa2ncias do problema, como pedir uma ida e volta atrav\xc3\xa9s de todos os lugares de Mil\xc3\xa3o cujo comprimento total \xc3\xa9 no m\xc3\xa1ximo 10\xc2\xa0km. Por esta raz\xc3\xa3o, a teoria da complexidade aborda problemas computacionais e n\xc3\xa3o inst\xc3\xa2ncias particulares do problema.\n_START_SECTION_\nRepresentando inst\xc3\xa2ncias de problema\n_START_PARAGRAPH_\nAo considerar problemas computacionais, uma inst\xc3\xa2ncia de problema \xc3\xa9 uma cadeia sobre um alfabeto. Normalmente, o alfabeto \xc3\xa9 considerado como sendo o alfabeto bin\xc3\xa1rio (ou seja, o conjunto {0,1}), e, assim, as cadeias s\xc3\xa3o bitstrings. Como em um computador do mundo real, objetos matem\xc3\xa1ticos que n\xc3\xa3o s\xc3\xa3o bitstrings devem ser devidamente codificados. Por exemplo, n\xc3\xbameros inteiros podem ser representados em nota\xc3\xa7\xc3\xa3o bin\xc3\xa1ria, e grafos podem ser codificados diretamente via suas matrizes de adjac\xc3\xaancia, ou por codifica\xc3\xa7\xc3\xa3o de suas listas de adjac\xc3\xaancia em bin\xc3\xa1rio._NEWLINE_Apesar de algumas provas de complexidade-te\xc3\xb3rica de teoremas regularmente assumir alguma escolha concreta de codifica\xc3\xa7\xc3\xa3o de entrada, tenta-se manter a discuss\xc3\xa3o abstrata o suficiente para ser independente da escolha da codifica\xc3\xa7\xc3\xa3o. Isto pode ser conseguido assegurando que diferentes representa\xc3\xa7\xc3\xb5es possam ser transformadas em outra de forma eficiente.\n_START_SECTION_\nProblemas de decis\xc3\xa3o como linguagens formais\n_START_PARAGRAPH_\nProblemas de decis\xc3\xa3o s\xc3\xa3o um dos objetos de estudo centrais na teoria da complexidade computacional. Um problema de decis\xc3\xa3o \xc3\xa9 um tipo especial de problema computacional cuja resposta \xc3\xa9 sim ou n\xc3\xa3o, ou alternativamente 1 ou 0. Um problema de decis\xc3\xa3o pode ser visto como uma linguagem formal, onde os membros da linguagem s\xc3\xa3o inst\xc3\xa2ncias cuja resposta \xc3\xa9 sim, e os n\xc3\xa3o membros da linguagem s\xc3\xa3o aquelas inst\xc3\xa2ncias cuja sa\xc3\xadda \xc3\xa9 n\xc3\xa3o. O objetivo \xc3\xa9 decidir, com a ajuda de um algoritmo, se uma dada sequ\xc3\xaancia de entrada \xc3\xa9 um membro da linguagem formal em considera\xc3\xa7\xc3\xa3o. Se o algoritmo decidir este problema, ele retorna a resposta sim, diz-se que o algoritmo aceita a sequ\xc3\xaancia de entrada, caso contr\xc3\xa1rio, diz-se que rejeita a entrada._NEWLINE_Um exemplo de um problema de decis\xc3\xa3o \xc3\xa9 o seguinte. A entrada \xc3\xa9 um grafo arbitr\xc3\xa1rio. O problema consiste em decidir se o dado grafo \xc3\xa9 conexo ou n\xc3\xa3o. A linguagem formal associada a este problema de decis\xc3\xa3o \xc3\xa9 ent\xc3\xa3o o conjunto de todos os grafos conexos\xe2\x80\x94obviamente, para obter uma defini\xc3\xa7\xc3\xa3o precisa dessa linguagem, \xc3\xa9 preciso decidir como grafos s\xc3\xa3o codificados como cadeias bin\xc3\xa1rias.\n_START_SECTION_\nProblemas de fun\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nUm problema de fun\xc3\xa7\xc3\xa3o \xc3\xa9 um problema computacional, onde uma \xc3\xbanica sa\xc3\xadda (de uma fun\xc3\xa7\xc3\xa3o total) \xc3\xa9 esperada para cada entrada, mas a sa\xc3\xadda \xc3\xa9 mais complexa do que a de um problema de decis\xc3\xa3o, isto \xc3\xa9, n\xc3\xa3o \xc3\xa9 apenas sim ou n\xc3\xa3o. Exemplos not\xc3\xa1veis incluem o problema do caixeiro viajante e o problema de fatora\xc3\xa7\xc3\xa3o de inteiros._NEWLINE_\xc3\x89 tentador pensar que a no\xc3\xa7\xc3\xa3o de problemas de fun\xc3\xa7\xc3\xa3o \xc3\xa9 muito mais rica do que a no\xc3\xa7\xc3\xa3o de problemas de decis\xc3\xa3o. No entanto, o caso realmente n\xc3\xa3o \xc3\xa9 esse, j\xc3\xa1 que problemas de fun\xc3\xa7\xc3\xa3o podem ser reformulados como problemas de decis\xc3\xa3o. Por exemplo, a multiplica\xc3\xa7\xc3\xa3o de dois n\xc3\xbameros inteiros pode ser expressa como o conjunto (a,\xc2\xa0b,\xc2\xa0c) tal qual a rela\xc3\xa7\xc3\xa3o a\xc2\xa0\xc3\x97\xc2\xa0b\xc2\xa0=\xc2\xa0c descreve. Decidir se uma dada tripla \xc3\xa9 membro deste conjunto corresponde a resolver o problema da multiplica\xc3\xa7\xc3\xa3o de dois n\xc3\xbameros.\n_START_SECTION_\nMensura\xc3\xa7\xc3\xa3o  do tamanho de uma inst\xc3\xa2ncia\n_START_PARAGRAPH_\nPara 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\xc3\xa7\xc3\xa3o pode, em geral, depender da inst\xc3\xa2ncia. Em particular, inst\xc3\xa2ncias maiores exigir\xc3\xa3o mais tempo para resolver. Assim, o tempo necess\xc3\xa1rio para resolver um problema (ou o espa\xc3\xa7o necess\xc3\xa1rio, ou qualquer outra medida de complexidade) \xc3\xa9 calculado em fun\xc3\xa7\xc3\xa3o do tamanho da inst\xc3\xa2ncia. Isso geralmente leva em considera\xc3\xa7\xc3\xa3o o tamanho da entrada em bits. A Teoria da Complexidade est\xc3\xa1 interessada em como os tempos de execu\xc3\xa7\xc3\xa3o de algoritmos crescem com um aumento no tamanho da entrada. Por exemplo, no problema de descobrir se um grafo \xc3\xa9 conectado, quanto tempo a mais leva para resolver um problema para um grafo com 2n v\xc3\xa9rtices comparado ao tempo levado para um grafo com n v\xc3\xa9rtices?_NEWLINE_Se o tamanho da entrada \xc3\xa9 n, o tempo gasto pode ser expresso como uma fun\xc3\xa7\xc3\xa3o de n. J\xc3\xa1 que o tempo gasto em diferentes entradas de mesmo tamanho pode ser diferente, o pior caso em complexidade de tempo T(n) \xc3\xa9 definido como sendo o tempo m\xc3\xa1ximo dentre todas as entradas de tamanho n. Se T(n) \xc3\xa9 um polin\xc3\xb4mio em n, ent\xc3\xa3o o algoritmo \xc3\xa9 dito ser um algoritmo de tempo polinomial. A tese de Cobham diz que um problema pode ser resolvido com uma quantidade fact\xc3\xadvel de recursos se ele admite um algoritmo de tempo polinomial.\n_START_SECTION_\nM\xc3\xa1quina de Turing\n_START_PARAGRAPH_\nUma m\xc3\xa1quina de Turing \xc3\xa9 um modelo matem\xc3\xa1tico de uma m\xc3\xa1quina de computa\xc3\xa7\xc3\xa3o em geral. \xc3\x89 um dispositivo te\xc3\xb3rico que manipula s\xc3\xadmbolos contidos em uma tira de fita. M\xc3\xa1quinas de Turing n\xc3\xa3o pretendem ser uma tecnologia de computa\xc3\xa7\xc3\xa3o na pr\xc3\xa1tica, mas sim uma experi\xc3\xaancia de pensamento que representa uma m\xc3\xa1quina de computa\xc3\xa7\xc3\xa3o. Acredita-se que se um problema pode ser resolvido por um algoritmo, ent\xc3\xa3o existe uma m\xc3\xa1quina de Turing que resolve o problema. Na verdade, esta \xc3\xa9 a afirma\xc3\xa7\xc3\xa3o da tese de Church-Turing. Al\xc3\xa9m disso, sabe-se que tudo o que pode ser computado em outros modelos de computa\xc3\xa7\xc3\xa3o conhecido por n\xc3\xb3s hoje, como uma m\xc3\xa1quina RAM, Jogo da Vida de Conway, aut\xc3\xb4mato celular ou qualquer linguagem de programa\xc3\xa7\xc3\xa3o pode ser computado em uma m\xc3\xa1quina de Turing. Como as m\xc3\xa1quinas de Turing s\xc3\xa3o f\xc3\xa1ceis de analisar matematicamente, e acredita-se que sejam t\xc3\xa3o poderosas quanto qualquer outro modelo de computa\xc3\xa7\xc3\xa3o, a m\xc3\xa1quina de Turing \xc3\xa9 o modelo mais comumente usado em teoria da complexidade._NEWLINE_Muitos tipos de m\xc3\xa1quinas de Turing s\xc3\xa3o usados para definir as classes de complexidade, tais como m\xc3\xa1quinas de Turing determin\xc3\xadsticas, m\xc3\xa1quinas de Turing probabil\xc3\xadsticas, m\xc3\xa1quinas de Turing n\xc3\xa3o-determin\xc3\xadsticas, m\xc3\xa1quinas de Turing qu\xc3\xa2nticas, m\xc3\xa1quinas de Turing sim\xc3\xa9tricas e m\xc3\xa1quinas de Turing alternadas. Todas elas s\xc3\xa3o igualmente poderosas, em princ\xc3\xadpio, mas quando os recursos (tais como tempo e espa\xc3\xa7o) s\xc3\xa3o limitados, algumas destas podem ser mais poderosas do que outras._NEWLINE_Uma m\xc3\xa1quina de Turing determin\xc3\xadstica \xc3\xa9 a m\xc3\xa1quina de Turing do tipo mais b\xc3\xa1sico, que utiliza um conjunto fixo de regras para determinar suas a\xc3\xa7\xc3\xb5es futuras. Uma m\xc3\xa1quina de Turing probabil\xc3\xadstica \xc3\xa9 uma m\xc3\xa1quina de Turing determin\xc3\xadstica com um suprimento extra de bits aleat\xc3\xb3rios. A capacidade de tomar decis\xc3\xb5es probabil\xc3\xadsticas muitas vezes ajuda algoritmos a resolverem problemas de forma mais eficiente. Algoritmos que usam bits aleat\xc3\xb3rios s\xc3\xa3o chamados algoritmos probabil\xc3\xadsticos. A m\xc3\xa1quina de Turing n\xc3\xa3o-determin\xc3\xadstica \xc3\xa9 uma m\xc3\xa1quina de Turing determin\xc3\xadstica com uma caracter\xc3\xadstica adicional de n\xc3\xa3o-determinismo, que permite que uma m\xc3\xa1quina de Turing tenha v\xc3\xa1rias poss\xc3\xadveis a\xc3\xa7\xc3\xb5es futuras a partir de um determinado estado. Uma maneira de entender o n\xc3\xa3o-determinismo \xc3\xa9 visualizar os ramos da m\xc3\xa1quina de Turing como os v\xc3\xa1rios caminhos computacionais poss\xc3\xadveis a cada passo, e se ela resolve o problema em qualquer um desses ramos, diz-se ter resolvido o problema. Evidentemente, este modelo n\xc3\xa3o pretende ser um modelo fisicamente realiz\xc3\xa1vel, \xc3\xa9 apenas uma m\xc3\xa1quina abstrata teoricamente interessante que d\xc3\xa1 origem a classes de complexidade particularmente interessantes. Por exemplo, veja algoritmo n\xc3\xa3o-determin\xc3\xadstico.\n_START_SECTION_\nOutros modelos de m\xc3\xa1quinas\n_START_PARAGRAPH_\nMuitos modelos de m\xc3\xa1quinas diferentes do padr\xc3\xa3o de m\xc3\xa1quinas de Turing multi-fitas t\xc3\xaam sido propostos na literatura, por exemplo, m\xc3\xa1quinas de acesso aleat\xc3\xb3rio. Talvez surpreendentemente, cada um desses modelos pode ser convertido para outro, sem fornecer qualquer poder computacional extra. O consumo de tempo e mem\xc3\xb3ria desses modelos alternativos pode variar. O que todos estes modelos t\xc3\xaam em comum \xc3\xa9 que as m\xc3\xa1quinas funcionam de forma determin\xc3\xadstica._NEWLINE_No entanto, alguns problemas computacionais s\xc3\xa3o mais f\xc3\xa1ceis de analisar em termos de recursos mais incomuns. Por exemplo, uma m\xc3\xa1quina de Turing n\xc3\xa3o-determin\xc3\xadstica \xc3\xa9 um modelo computacional em que \xc3\xa9 permitido ramificar-se para verificar muitas possibilidades diferentes de uma s\xc3\xb3 vez. A m\xc3\xa1quina de Turing n\xc3\xa3o-determin\xc3\xadstica tem muito pouco a ver com a forma como n\xc3\xb3s queremos fisicamente computar algoritmos, mas a sua ramifica\xc3\xa7\xc3\xa3o capta exatamente muitos dos modelos matem\xc3\xa1ticos que queremos analisar, de modo que o tempo n\xc3\xa3o-determin\xc3\xadstico \xc3\xa9 um recurso muito importante na an\xc3\xa1lise de problemas computacionais.\n_START_SECTION_\nMedidas de complexidade\n_START_PARAGRAPH_\nPara uma defini\xc3\xa7\xc3\xa3o precisa do que significa resolver um problema utilizando uma determinada quantidade de tempo e espa\xc3\xa7o, um modelo computacional tal como a m\xc3\xa1quina de Turing determin\xc3\xadstica \xc3\xa9 utilizado. O tempo exigido por uma m\xc3\xa1quina de Turing determin\xc3\xadstica M na entrada x \xc3\xa9 o n\xc3\xbamero total de transi\xc3\xa7\xc3\xb5es de estado, ou etapas, que a m\xc3\xa1quina faz antes de parar e responder com a sa\xc3\xadda ("sim" ou "n\xc3\xa3o"). Diz-se que a m\xc3\xa1quina de Turing M opera dentro do tempo f(n), se o tempo exigido por M em cada entrada de comprimento n \xc3\xa9 no m\xc3\xa1ximo f(n). Um problema de decis\xc3\xa3o A pode ser resolvido em tempo f(n) se existe uma opera\xc3\xa7\xc3\xa3o da m\xc3\xa1quina de Turing em tempo f(n) que resolve o problema. Como a teoria da complexidade est\xc3\xa1 interessada em classificar problemas com base na sua dificuldade, definem-se conjuntos de problemas com base em alguns crit\xc3\xa9rios. Por exemplo, o conjunto de problemas solucion\xc3\xa1veis no tempo f(n) em uma m\xc3\xa1quina de Turing determin\xc3\xadstica \xc3\xa9 ent\xc3\xa3o indicado por DTIME(f(n))._NEWLINE_Defini\xc3\xa7\xc3\xb5es an\xc3\xa1logas podem ser feitas para os requisitos de espa\xc3\xa7o. Embora o tempo e o espa\xc3\xa7o sejam os mais conhecidos recursos de complexidade, qualquer medida de complexidade pode ser vista como um recurso computacional. Medidas de complexidade s\xc3\xa3o geralmente definidas pelos axiomas de complexidade de Blum. Outras medidas de complexidade utilizadas na teoria da complexidade incluem a complexidade de comunica\xc3\xa7\xc3\xa3o, a complexidade do circuito e a complexidade da \xc3\xa1rvore de decis\xc3\xa3o.\n_START_SECTION_\nLimites superior e inferior da complexidade dos problemas\n_START_PARAGRAPH_\nPara classificar o tempo de computa\xc3\xa7\xc3\xa3o (ou recursos semelhantes, como o consumo de espa\xc3\xa7o), \xc3\xa9 necess\xc3\xa1rio provar os limites superiores e inferiores sobre a quantidade m\xc3\xadnima de tempo exigida pelo algoritmo mais eficiente para resolver um determinado problema. A complexidade de um algoritmo \xc3\xa9 geralmente entendida como a sua complexidade de pior caso, a menos que seja especificado o contr\xc3\xa1rio. A an\xc3\xa1lise de um determinado algoritmo cai sob o campo de an\xc3\xa1lise de algoritmos. Para mostrar um limite superior T(n) sobre a complexidade de tempo de um problema, \xc3\xa9 necess\xc3\xa1rio mostrar apenas que h\xc3\xa1 um determinado algoritmo com tempo de funcionamento, no m\xc3\xa1ximo, T(n). No entanto, provar limites inferiores \xc3\xa9 muito mais dif\xc3\xadcil, uma vez que limites inferiores fazem uma declara\xc3\xa7\xc3\xa3o sobre todos os poss\xc3\xadveis algoritmos que resolvem um determinado problema. A frase "todos os algoritmos poss\xc3\xadveis" inclui n\xc3\xa3o 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)._NEWLINE_Limites superiores  s\xc3\xa3o geralmente indicados usando a nota\xc3\xa7\xc3\xa3o O-grande, que desconsidera fatores constantes e termos menores. Isso faz com que os limites independam dos detalhes espec\xc3\xadficos do modelo computacional utilizado. Por exemplo, T(n)\xc2\xa0=\xc2\xa07n\xc2\xb2\xc2\xa0+\xc2\xa015n\xc2\xa0+\xc2\xa040, em nota\xc3\xa7\xc3\xa3o O-grande seria escrito da seguinte forma T(n)\xc2\xa0=\xc2\xa0O(n\xc2\xb2)._NEWLINE_Limites inferiores s\xc3\xa3o geralmente indicados usando a nota\xc3\xa7\xc3\xa3o \xce\xa9\n_START_SECTION_\nTeoremas de hierarquia\n_START_PARAGRAPH_\nPara as classes de complexidade definidas desta forma, \xc3\xa9 desej\xc3\xa1vel provar que relaxar os requisitos em fun\xc3\xa7\xc3\xa3o (digamos) do tempo de computa\xc3\xa7\xc3\xa3o realmente define um conjunto maior de problemas. Em particular, embora DTIME(n) esteja contido em DTIME(n\xc2\xb2), seria interessante saber se a inclus\xc3\xa3o \xc3\xa9 estrita. Para requisitos de tempo e de espa\xc3\xa7o, a resposta a tais perguntas \xc3\xa9 dada pelo teorema de hierarquia para a complexidade de tempo e pelo teorema de hierarquia para a complexidade de espa\xc3\xa7o, respectivamente. Eles s\xc3\xa3o 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\xc3\xa1 propriamente contida na outra. Depois de ter deduzido assim as rela\xc3\xa7\xc3\xb5es de pertin\xc3\xaancia estrita de conjuntos, podemos continuar a fazer declara\xc3\xa7\xc3\xb5es quantitativas sobre quanto mais tempo adicional ou espa\xc3\xa7o \xc3\xa9 necess\xc3\xa1rio para aumentar o n\xc3\xbamero de problemas que podem ser resolvidos._NEWLINE_Mais precisamente, o teorema de hierarquia de tempo afirma que:_NEWLINE_ _NEWLINE_O teorema de hierarquia de espa\xc3\xa7o afirma que:_NEWLINE_ _NEWLINE_Os teoremas de hierarquia de tempo e de espa\xc3\xa7o formam a base para a maioria dos resultados de separa\xc3\xa7\xc3\xa3o de classes de complexidade. Por exemplo, o teorema da hierarquia de tempo nos diz que P est\xc3\xa1 estritamente contida em EXPTIME, e o teorema hierarquia do espa\xc3\xa7o nos diz que L est\xc3\xa1 estritamente contida em PSPACE.\n_START_SECTION_\nRedu\xc3\xa7\xc3\xa3o\n_START_PARAGRAPH_\nMuitas classes de complexidade s\xc3\xa3o definidas usando o conceito de redu\xc3\xa7\xc3\xa3o. Uma redu\xc3\xa7\xc3\xa3o \xc3\xa9 uma transforma\xc3\xa7\xc3\xa3o de um problema em outro problema. Ela captura a no\xc3\xa7\xc3\xa3o informal de um problema que seja pelo menos t\xc3\xa3o dif\xc3\xadcil quanto outro problema. Por exemplo, se um problema X pode ser resolvido usando um algoritmo para Y, X n\xc3\xa3o \xc3\xa9 mais dif\xc3\xadcil do que Y, e dizemos que X se reduz a Y. Existem muitos tipos diferentes de redu\xc3\xa7\xc3\xa3o, com base no m\xc3\xa9todo de redu\xc3\xa7\xc3\xa3o, como redu\xc3\xa7\xc3\xb5es de Cook, redu\xc3\xa7\xc3\xb5es de Karp e redu\xc3\xa7\xc3\xb5es Levin, e no limite da complexidade das redu\xc3\xa7\xc3\xb5es, como redu\xc3\xa7\xc3\xb5es de tempo polinomial ou redu\xc3\xa7\xc3\xb5es log-space._NEWLINE_A redu\xc3\xa7\xc3\xa3o mais comumente usada \xc3\xa9 uma redu\xc3\xa7\xc3\xa3o em tempo polinomial. Isso significa que o processo de redu\xc3\xa7\xc3\xa3o leva tempo polinomial. Por exemplo, o problema do quadrado de um inteiro pode ser reduzido para o problema da multiplica\xc3\xa7\xc3\xa3o de dois n\xc3\xbameros 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\xc3\xa7\xc3\xa3o. Assim, vemos que o problema do quadrado de um inteiro n\xc3\xa3o \xc3\xa9 mais dif\xc3\xadcil do que o problema da multiplica\xc3\xa7\xc3\xa3o, j\xc3\xa1 que o problema do quadrado de um inteiro pode ser reduzido ao problema da multiplica\xc3\xa7\xc3\xa3o._NEWLINE_Isso motiva o conceito de um problema que ser dif\xc3\xadcil para uma classe de complexidade. Um problema X \xc3\xa9 dif\xc3\xadcil para uma classe de problemas C se todo problema em C pode ser reduzido a X. Assim, nenhum problema em C \xc3\xa9 mais dif\xc3\xadcil do que X, uma vez que um algoritmo para X nos permite resolver qualquer problema em C. \xc3\x89 claro que a no\xc3\xa7\xc3\xa3o de problemas dif\xc3\xadceis depende do tipo de redu\xc3\xa7\xc3\xa3o a ser utilizado. Para as classes de complexidade maiores do que P, redu\xc3\xa7\xc3\xb5es em tempo polinomial s\xc3\xa3o comumente usados. Em particular, o conjunto de problemas que s\xc3\xa3o dif\xc3\xadceis para NP \xc3\xa9 o conjunto de problemas NP-dif\xc3\xadcil._NEWLINE_Se um problema X est\xc3\xa1 em C e \xc3\xa9 dif\xc3\xadcil para C, ent\xc3\xa3o diz-se que X \xc3\xa9 completo para C. Isto significa que X \xc3\xa9 o problema mais dif\xc3\xadcil em C. (Uma vez que muitos problemas poderiam ser igualmente dif\xc3\xadceis, pode-se dizer que X \xc3\xa9 um dos os problemas mais dif\xc3\xadceis em C.) Assim, a classe de problemas NP-completo cont\xc3\xa9m os problemas mais dif\xc3\xadceis em NP, nesse sentido eles s\xc3\xa3o os mais propensos a n\xc3\xa3o estarem em P. Como o problema P\xc2\xa0=\xc2\xa0NP n\xc3\xa3o foi resolvido, ser capaz de reduzir um conhecido problema NP-completo, \xce\xa0\xe2\x82\x82, para outro problema, \xce\xa0\xe2\x82\x81, indicaria que n\xc3\xa3o h\xc3\xa1 nenhuma solu\xc3\xa7\xc3\xa3o conhecida em tempo polinomial para \xce\xa0\xe2\x82\x81. Isso ocorre porque uma solu\xc3\xa7\xc3\xa3o em tempo polinomial para \xce\xa0\xe2\x82\x81 renderia uma solu\xc3\xa7\xc3\xa3o em tempo polinomial para \xce\xa0\xe2\x82\x82. Da mesma forma que todos os problemas NP podem ser reduzidos ao conjunto, encontrar um problema NP-completo que pudesse ser resolvido em tempo polinomial significaria que P\xc2\xa0=\xc2\xa0NP.\n_START_SECTION_\nO problema P versus NP\n_START_PARAGRAPH_\nA classe de complexidade P \xc3\xa9 muitas vezes vista como uma abstra\xc3\xa7\xc3\xa3o matem\xc3\xa1tica de modelagem dessas tarefas computacionais que admitem um algoritmo eficiente. Esta hip\xc3\xb3tese \xc3\xa9 chamada de tese de Cobham-Edmonds. A classe de complexidade NP, por outro lado, cont\xc3\xa9m muitos problemas que as pessoas gostariam de resolver de forma eficiente, mas para os quais nenhum algoritmo eficiente \xc3\xa9 conhecido, como o problema da satisfatibilidade booleana, o problema do caminho hamiltoniano e o problema da cobertura de v\xc3\xa9rtices. Como as m\xc3\xa1quinas de Turing determin\xc3\xadstica s\xc3\xa3o m\xc3\xa1quinas de Turing n\xc3\xa3o-determin\xc3\xadsticas especiais, \xc3\xa9 f\xc3\xa1cil observar que cada problema em P tamb\xc3\xa9m \xc3\xa9 membro da classe NP._NEWLINE_A quest\xc3\xa3o de saber se P \xc3\xa9 igual a NP \xc3\xa9 uma das quest\xc3\xb5es mais importantes em aberto na ci\xc3\xaancia da computa\xc3\xa7\xc3\xa3o te\xc3\xb3rica por causa da gama de implica\xc3\xa7\xc3\xb5es de uma solu\xc3\xa7\xc3\xa3o. Se a resposta for sim, para muitos problemas importantes pode ser mostrado que h\xc3\xa1 solu\xc3\xa7\xc3\xb5es mais eficientes para eles. Estes incluem v\xc3\xa1rios tipos de problemas de programa\xc3\xa7\xc3\xa3o inteira em investiga\xc3\xa7\xc3\xa3o operacional, muitos problemas na \xc3\xa1rea de log\xc3\xadstica, previs\xc3\xa3o da estrutura de prote\xc3\xadnas na biologia, e capacidade de encontrar provas formais de teoremas da matem\xc3\xa1tica pura. O problema P versus NP \xc3\xa9 um dos Problemas do Pr\xc3\xaamio Millenium (Millenium Prize Problems) proposto pelo Instituto Clay de Matem\xc3\xa1tica (Clay Mathematics Institute). Existe um pr\xc3\xaamio de um milh\xc3\xa3o de d\xc3\xb3lares para resolver o problema.\n_START_SECTION_\nProblemas em NP que n\xc3\xa3o se sabe se pertencem a P ou a NP-completo\n_START_PARAGRAPH_\nFoi mostrado por Ladner que, se P \xe2\x89\xa0 NP, ent\xc3\xa3o existem problemas em NP que n\xc3\xa3o est\xc3\xa3o nem em P nem em NP-completo. Tais problemas s\xc3\xa3o chamados de problemas NP-intermedi\xc3\xa1rio. O problema do isomorfismo de grafos, o problema do logaritmo discreto e o problema de fatora\xc3\xa7\xc3\xa3o de inteiros s\xc3\xa3o exemplos de problemas que acredita-se que sejam NP-intermedi\xc3\xa1rio. Eles s\xc3\xa3o alguns dos muito poucos problemas NP que n\xc3\xa3o se sabe se est\xc3\xa3o em P ou em NP-completo._NEWLINE_O problema do isomorfismo de grafos \xc3\xa9 o problema computacional para determinar se dois grafos finitos s\xc3\xa3o isomorfos. Um importante problema n\xc3\xa3o resolvido na teoria da complexidade \xc3\xa9 se o problema do isomorfismo de grafos est\xc3\xa1 em P, NP-completo, ou NP-intermedi\xc3\xa1rio. A resposta n\xc3\xa3o \xc3\xa9 conhecida, mas acredita-se que o problema n\xc3\xa3o seja, pelo menos, NP-completo. Se o isomorfismo de grafos for NP-completo, a hierarquia de tempo polinomial colapsa para seu segundo n\xc3\xadvel. Uma vez que acredita-se veemente que a hierarquia polinomial n\xc3\xa3o colapse para nenhum n\xc3\xadvel finito, acredita-se que o isomorfismo de grafos n\xc3\xa3o seja NP-completo. O melhor algoritmo para este problema, de acordo com Laszlo Babai e Eugene Luks tem tempo de execu\xc3\xa7\xc3\xa3o 2 para grafos com n v\xc3\xa9rtices._NEWLINE_O problema da fatora\xc3\xa7\xc3\xa3o de inteiros \xc3\xa9 o problema computacional para determinar a fatora\xc3\xa7\xc3\xa3o prima de um dado inteiro. Formulado como um problema de decis\xc3\xa3o, \xc3\xa9 o problema para decidir se a entrada tem um fator menor que k. Nenhum algoritmo de fatora\xc3\xa7\xc3\xa3o de inteiro eficiente \xc3\xa9 conhecido, e este fato \xc3\xa9 a base de v\xc3\xa1rios sistemas criptogr\xc3\xa1ficos modernos, como o algoritmo RSA. O problema da fatora\xc3\xa7\xc3\xa3o de inteiros est\xc3\xa1 em NP e em co-NP (e at\xc3\xa9 mesmo em UP e co-UP ). Se o problema \xc3\xa9 NP-completo, a hierarquia de tempo polinomial colapsar\xc3\xa1 para seu primeiro n\xc3\xadvel (ou seja, NP ser\xc3\xa1 igual a co-NP). O melhor algoritmo conhecido para fatora\xc3\xa7\xc3\xa3o de inteiros \xc3\xa9 o GNFS (general number field sieve), que leva tempo O(e) para fatorar um inteiro de n-bit. No entanto, o melhor algoritmo qu\xc3\xa2ntico conhecido para este problema, o algoritmo de Shor, \xc3\xa9 executado em tempo polinomial. Infelizmente, este fato n\xc3\xa3o diz muito sobre onde est\xc3\xa1 o problema com rela\xc3\xa7\xc3\xa3o a classes de complexidade n\xc3\xa3o-qu\xc3\xa2ntica.\n_START_SECTION_\nSepara\xc3\xa7\xc3\xb5es entre outras classes de complexidade\n_START_PARAGRAPH_\nMuitas classes de complexidade conhecidas s\xc3\xa3o suspeitas de n\xc3\xa3o serem iguais, mas isso n\xc3\xa3o foi provado. Por exemplo, P \xe2\x8a\x86 NP \xe2\x8a\x86 PP \xe2\x8a\x86 PSPACE, mas \xc3\xa9 poss\xc3\xadvel que P = PSPACE. Se P n\xc3\xa3o for igual a NP, ent\xc3\xa3o P n\xc3\xa3o ser\xc3\xa1 igual \xc3\xa0 PSPACE tamb\xc3\xa9m. Uma vez que existem muitas classes de complexidade conhecidas entre P e PSPACE, tais como RP, BPP, PP, BQP, MA, PH, etc, \xc3\xa9 poss\xc3\xadvel que todas estas classes de complexidade colapsem para uma \xc3\xbanica classe. Provar que qualquer uma destas classes n\xc3\xa3o s\xc3\xa3o iguais seria um grande avan\xc3\xa7o na teoria da complexidade._NEWLINE_Na mesma linha, co-NP \xc3\xa9 a classe que cont\xc3\xa9m os problemas do complemento (ou seja, problemas com as respostas sim / n\xc3\xa3o invertidas) dos problemas NP. Acredita-se  que NP n\xc3\xa3o seja igual a co-NP, no entanto, ainda n\xc3\xa3o foi comprovado. Tem sido mostrado que, se essas duas classes de complexidade n\xc3\xa3o s\xc3\xa3o iguais, ent\xc3\xa3o P n\xc3\xa3o \xc3\xa9 igual a NP._NEWLINE_Da mesma forma, n\xc3\xa3o se sabe se L (o conjunto de todos os problemas que podem ser resolvidos no espa\xc3\xa7o logar\xc3\xadtmico) est\xc3\xa1 contido estritamente em P ou \xc3\xa9 igual a P. Novamente, existem muitas classes de complexidade entre elas, tais como NL e NC, e n\xc3\xa3o se sabe se elas s\xc3\xa3o classes iguais ou distintas._NEWLINE_Suspeita-se que P e BPP sejam iguais. No entanto, \xc3\xa9 um problema em aberto, no momento, se BPP = NEXP.\n_START_SECTION_\nIntratabilidade\n_START_PARAGRAPH_\nProblemas que podem ser resolvidos na teoria (por exemplo, dado um tempo infinito), mas que na pr\xc3\xa1tica levam muito tempo para as suas solu\xc3\xa7\xc3\xb5es sejam \xc3\xbateis, s\xc3\xa3o conhecidos como problemas intrat\xc3\xa1veis. Na teoria da complexidade, os problemas que n\xc3\xa3o apresentam solu\xc3\xa7\xc3\xb5es em tempo polinomial s\xc3\xa3o considerados intrat\xc3\xa1veis 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\xc3\xadvel por algum dispositivo computacional. Problemas que s\xc3\xa3o conhecidos por serem intrat\xc3\xa1veis neste sentido incluem aqueles que s\xc3\xa3o EXPTIME-dif\xc3\xadcil. Se NP n\xc3\xa3o \xc3\xa9 o mesmo que P, ent\xc3\xa3o os problemas NP-completo s\xc3\xa3o tamb\xc3\xa9m intrat\xc3\xa1veis neste sentido. Para ver porque algoritmos de tempo exponencial podem ser impratic\xc3\xa1veis, considere um programa que faz 2\xe2\x81\xbf opera\xc3\xa7\xc3\xb5es antes de parar. Para n pequeno, digamos 100, e assumindo, por exemplo, que o computador faz 10\xc2\xb9\xc2\xb2 opera\xc3\xa7\xc3\xb5es por segundo, o programa seria executado por cerca de 4\xc2\xa0\xc3\x97\xc2\xa010\xc2\xb9\xe2\x81\xb0 anos, que \xc3\xa9 aproximadamente a idade do universo. Mesmo com um computador muito mais r\xc3\xa1pido, o programa s\xc3\xb3 seria \xc3\xbatil para casos muito pequenos e, nesse sentido, a intratabilidade de um problema \xc3\xa9 um tanto independente do progresso tecnol\xc3\xb3gico. No entanto, um algoritmo de tempo polinomial n\xc3\xa3o \xc3\xa9 sempre pr\xc3\xa1tico. Se seu tempo de execu\xc3\xa7\xc3\xa3o \xc3\xa9, digamos "n"\xc2\xb9\xe2\x81\xb5, n\xc3\xa3o \xc3\xa9 razo\xc3\xa1vel consider\xc3\xa1-lo eficiente e ainda \xc3\xa9 in\xc3\xbatil, salvo em casos de pequeno porte._NEWLINE_O que intratabilidade significa na pr\xc3\xa1tica est\xc3\xa1 aberto em debate. Dizer que um problema n\xc3\xa3o est\xc3\xa1 em P n\xc3\xa3o implica que todos os grandes casos de problemas s\xc3\xa3o dif\xc3\xadceis ou at\xc3\xa9 mesmo que a maioria deles s\xc3\xa3o. Por exemplo, o problema da decis\xc3\xa3o na Aritm\xc3\xa9tica de Presburger tem demonstrado n\xc3\xa3o estar em P, ainda foram escritos algoritmos que resolvem o problema em tempos razo\xc3\xa1veis na maioria dos casos. Da mesma forma, os algoritmos podem resolver o problema da mochila NP-completo em uma ampla faixa de tamanhos em menos que o tempo quadr\xc3\xa1tico e resolvedores de SAT rotineiramente lidam com grandes inst\xc3\xa2ncias do problema de satisfatibilidade booleana NP-completo.\n_START_SECTION_\nTeoria da complexidade cont\xc3\xadnua\n_START_PARAGRAPH_\nA teoria da complexidade cont\xc3\xadnua pode se referir \xc3\xa0 teoria da complexidade dos problemas que envolvem fun\xc3\xa7\xc3\xb5es cont\xc3\xadnuas que s\xc3\xa3o aproximadas por discretiza\xc3\xa7\xc3\xb5es, como estudado em an\xc3\xa1lise num\xc3\xa9rica. Uma abordagem para a teoria da complexidade da an\xc3\xa1lise num\xc3\xa9rica  \xc3\xa9 a complexidade baseada em informa\xc3\xa7\xc3\xa3o (IBC)._NEWLINE_A teoria da complexidade cont\xc3\xadnua tamb\xc3\xa9m pode se referir \xc3\xa0 teoria da complexidade do uso da computa\xc3\xa7\xc3\xa3o anal\xc3\xb3gica, que utiliza sistemas din\xc3\xa2micos cont\xc3\xadnuos e equa\xc3\xa7\xc3\xb5es diferenciais. A teoria de controle pode ser considerada uma forma de computa\xc3\xa7\xc3\xa3o e equa\xc3\xa7\xc3\xb5es diferenciais s\xc3\xa3o usadas na modelagem de sistemas de tempo cont\xc3\xadnuo e h\xc3\xadbridos de tempo discreto-cont\xc3\xadnuo.\n_START_SECTION_\nHist\xc3\xb3ria\n_START_PARAGRAPH_\nAntes de a pesquisa propriamente dita explicitamente dedicada \xc3\xa0 complexidade dos problemas algor\xc3\xadtmicos come\xc3\xa7ar, os numerosos fundamentos foram estabelecidos por v\xc3\xa1rios pesquisadores. O mais influente entre estes foi a defini\xc3\xa7\xc3\xa3o das m\xc3\xa1quinas de Turing por Alan Turing em 1936, que acabou por ser uma no\xc3\xa7\xc3\xa3o muito robusta e flex\xc3\xadvel de computador._NEWLINE_Fortnow & Homer (2003) datam o in\xc3\xadcio dos estudos sistem\xc3\xa1ticos em complexidade computacional com o importante artigo "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard Stearns (1965), que estabeleceu as defini\xc3\xa7\xc3\xb5es de complexidade de tempo e de espa\xc3\xa7o e provou os teoremas de hierarquia._NEWLINE_De acordo com Fortnow & Homer (2003), trabalhos anteriores que estudaram problemas solucion\xc3\xa1veis por m\xc3\xa1quinas de Turing com recursos espec\xc3\xadficos limitados inclui a defini\xc3\xa7\xc3\xa3o de John Myhill de aut\xc3\xb4matos linearmente limitados (Myhill 1960), o estudo de Raymond Smullyan sobre conjuntos rudimentares (1961), assim como o artigo de Hisao Yamada  sobre computa\xc3\xa7\xc3\xa3o em tempo real (1962). Um pouco mais cedo, Boris Trakhtenbrot (1956), um pioneiro no campo da URSS, estudou outra medida espec\xc3\xadfica de complexidade. Como lembra ele:_NEWLINE_Contudo, [meu] interesse inicial [na teoria dos aut\xc3\xb4matos] era cada vez mais posto de lado em detrimento \xc3\xa0 complexidade computacional, uma excitante fus\xc3\xa3o de m\xc3\xa9todos combinatoriais, herdada da teoria da comuta\xc3\xa7\xc3\xa3o, com o arsenal conceitual da teoria de algoritmos. Essas ideias me ocorreram antes, em 1955, quando eu cunhei o termo "fun\xc3\xa7\xc3\xa3o de sinaliza\xc3\xa7\xc3\xa3o", que hoje \xc3\xa9 comumente conhecido como "medida de complexidade"._NEWLINE_\xe2\x80\x94\xe2\x80\x89Boris Trakhtenbrot, From Logic to Theoretical Computer Science \xe2\x80\x93 An Update. In: Pillars of Computer Science, LNCS 4800, Springer 2008._NEWLINE_Em 1967, Manuel Blum desenvolveu uma teoria da complexidade axiom\xc3\xa1tica com base em seus axiomas e provou um resultado importante, o ent\xc3\xa3o chamado, teorema da acelera\xc3\xa7\xc3\xa3o de Blum (speed-up theorem). O campo realmente come\xc3\xa7ou a florescer quando o pesquisador norte-americano Stephen Cook e, trabalhando independentemente, Leonid Levin na URSS, provaram que existem importantes problemas pratic\xc3\xa1veis que s\xc3\xa3o NP-completos. Em 1972, Richard Karp partiu desta ideia e deu um salto \xc3\xa0 frente com seu artigo hist\xc3\xb3rico, "Reducibility Among Combinatorial Problems", no qual ele mostrou que 21 diferentes problemas de combinat\xc3\xb3ria e problemas te\xc3\xb3ricos de grafos, famosos por sua intratabilidade computacional, s\xc3\xa3o NP-completos.'