Classe de complexidade - Complexity class

Uma representação das relações entre várias classes de complexidade importantes

Na teoria da complexidade computacional , uma classe de complexidade é um conjunto de problemas computacionais de complexidade baseada em recursos relacionados . Os dois recursos mais comumente analisados ​​são tempo e memória .

Em geral, uma classe de complexidade é definida em termos de um tipo de problema computacional, um modelo de computação e um recurso limitado como tempo ou memória . Em particular, a maioria das classes de complexidade consiste em problemas de decisão que podem ser resolvidos com uma máquina de Turing e são diferenciados por seus requisitos de tempo ou espaço (memória). Por exemplo, a classe P é o conjunto de problemas de decisão solucionáveis ​​por uma máquina de Turing determinística em tempo polinomial . Existem, no entanto, muitas classes de complexidade definidas em termos de outros tipos de problemas (por exemplo, problemas de contagem e problemas de função ) e usando outros modelos de computação (por exemplo , máquinas de Turing probabilísticas , sistemas de prova interativos , circuitos booleanos e computadores quânticos ).

O estudo das relações entre classes de complexidade é uma área importante de pesquisa na ciência da computação teórica. Freqüentemente, existem hierarquias gerais de classes de complexidade; por exemplo, sabe-se que várias classes fundamentais de complexidade de tempo e espaço se relacionam entre si da seguinte maneira: NLPNPPSPACEEXPTIMEEXPSPACE (onde ⊆ denota a relação de subconjunto ). No entanto, muitos relacionamentos ainda não são conhecidos; por exemplo, um dos mais famosos problemas em aberto na ciência da computação diz respeito se P é igual a NP . As relações entre as classes costumam responder a perguntas sobre a natureza fundamental da computação. O problema P versus NP , por exemplo, está diretamente relacionado a questões de saber se o não determinismo adiciona algum poder computacional aos computadores e se problemas com uma solução que pode ser rapidamente verificada quanto à correção também podem ser resolvidos rapidamente.

Fundo

As classes de complexidade são conjuntos de problemas computacionais relacionados . Eles são definidos em termos da dificuldade computacional de resolver os problemas contidos neles com relação a recursos computacionais específicos, como tempo ou memória. Mais formalmente, a definição de uma classe de complexidade consiste em três coisas: um tipo de problema computacional, um modelo de computação e um recurso computacional limitado. Em particular, a maioria das classes de complexidade consiste em problemas de decisão que podem ser resolvidos por uma máquina de Turing com tempo limitado ou recursos espaciais . Por exemplo, a classe de complexidade P é definida como o conjunto de problemas de decisão que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial .

Problemas computacionais

Intuitivamente, um problema computacional é apenas uma pergunta que um computador é capaz de responder. Por exemplo, "é o número natural n primo ?" é um problema que um computador pode resolver. Um problema computacional é matematicamente representado como o conjunto de respostas ao problema. No exemplo primality, o problema (chamemos-lhe PRIME ) é representado pelo conjunto de todos os números naturais que são primos: . Na teoria da computação, essas respostas são representadas como strings ; por exemplo, no exemplo da primalidade, os números naturais podem ser representados como cadeias de bits que representam números binários . Por esse motivo, os problemas computacionais são freqüentemente chamados de linguagens ; por exemplo, dizer que o problema PRIME está na classe de complexidade NP é equivalente a dizer que a linguagem PRIME está em NP .

Problemas de decisão

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

Os problemas mais comumente analisados ​​na ciência da computação teórica são os problemas de decisão - os tipos de problemas que podem ser apresentados como perguntas do tipo sim ou não . O exemplo de primalidade acima, por exemplo, é um exemplo de problema de decisão, pois pode ser representado pela pergunta sim-não "é o número natural n primo ". Em termos da teoria da computação, um problema de decisão é representado como o conjunto de strings de entrada para as quais um computador executando um algoritmo correto responderia "sim". No exemplo de primalidade, PRIME é o conjunto de strings que representam números naturais que, quando inseridos em um computador executando um algoritmo que testa corretamente a primalidade , o algoritmo responde "sim, este número é primo". Este formato "sim-não" é frequentemente declarado de forma equivalente como "aceitar-rejeitar"; ou seja, um algoritmo "aceita" uma string de entrada se a resposta ao problema de decisão for "sim" e "rejeita" se a resposta for "não".

Embora alguns problemas não possam ser facilmente expressos como problemas de decisão, eles abrangem uma ampla gama de problemas computacionais. Outros tipos de problemas para os quais certas classes de complexidade são definidas em termos de problemas de função de inclusão (por exemplo, FP ), problemas de contagem (por exemplo, #P ), problemas de otimização e problemas de promessa (consulte a seção "Outros tipos de problemas").

Modelos computacionais

Para concretizar a noção de "computador", na ciência da computação teórica os problemas são analisados ​​no contexto de um modelo computacional . Isso também é diretamente relevante para fazer noções exatas de recursos computacionais como "tempo" e "memória". Na teoria da complexidade computacional , as classes de complexidade lidam com os requisitos de recursos inerentes aos problemas e não com os requisitos de recursos que dependem de como um computador físico é construído. Por exemplo, no mundo real, diferentes computadores podem exigir diferentes quantidades de tempo e memória para resolver o mesmo problema devido à maneira como foram projetados. Ao fornecer representações matemáticas abstratas de computadores, os modelos computacionais abstraem complexidades supérfluas do mundo real (como diferenças na velocidade do processador ) que obstruem a compreensão dos princípios fundamentais.

O modelo computacional mais comumente usado é a máquina de Turing . Embora existam outros modelos e muitas classes de complexidade sejam definidas em termos deles (consulte a seção "Outros modelos de computação" ), a máquina de Turing é usada para definir a maioria das classes básicas de complexidade. Com a máquina de Turing, em vez de usar unidades de tempo padrão como a segunda (que tornam impossível separar o tempo de execução da velocidade do hardware físico) e unidades padrão de memória como bytes , a noção de tempo é abstraída como o número de etapas que uma máquina de Turing executa para resolver um problema e a noção de memória é abstraída como o número de células que são usadas na fita da máquina. Eles são explicados em mais detalhes a seguir.

Também é possível usar os axiomas de Blum para definir classes de complexidade sem se referir a um modelo computacional concreto , mas essa abordagem é menos frequentemente usada na teoria da complexidade.

Máquinas de Turing determinísticas

Uma ilustração de uma máquina de Turing. O "B" indica o símbolo em branco.

Uma máquina de Turing é um modelo matemático de uma máquina de computação geral. É o modelo mais comumente usado na teoria da complexidade, em grande parte devido ao fato de ser considerado tão poderoso quanto qualquer outro modelo de computação e fácil de analisar matematicamente. É importante ressaltar que acredita-se que se existe um algoritmo que resolve um problema específico, então também existe uma máquina de Turing que resolve esse mesmo problema (isso é conhecido como a tese de Church-Turing ); isso significa que acredita-se que todo algoritmo pode ser representado como uma máquina de Turing.

Mecanicamente, uma máquina de Turing (TM) manipula símbolos (geralmente restritos aos bits 0 e 1 para fornecer uma conexão intuitiva com computadores da vida real) contidos em uma tira infinitamente longa de fita. O TM pode ler e escrever, um de cada vez, usando um cabeçote de fita. A operação é totalmente determinada por um conjunto finito de instruções elementares, como "no estado 42, se o símbolo visto for 0, escreva 1; se o símbolo visto for 1, mude para o estado 17; no estado 17, se o símbolo visto for 0, escreva 1 e mude para o estado 6 ". A máquina de Turing começa com apenas a string de entrada em sua fita e espaços em branco em todos os outros lugares. O TM aceita a entrada se entrar em um estado de aceitação designado e rejeita a entrada se entrar em um estado de rejeição. A máquina de Turing determinística (DTM) é o tipo mais básico de máquina de Turing. Ele usa um conjunto fixo de regras para determinar suas ações futuras (por isso é chamado de " determinístico ").

Um problema computacional pode então ser definido em termos de uma máquina de Turing como o conjunto de strings de entrada que uma máquina de Turing específica aceita. Por exemplo, o problema de primalidade PRIME visto de cima é o conjunto de strings (representando números naturais) que uma máquina de Turing executando um algoritmo que testa corretamente a primalidade aceita. Diz-se que uma máquina de Turing reconhece uma linguagem (lembre-se de que "problema" e "linguagem" são em grande parte sinônimos na teoria da computabilidade e complexidade) se ela aceita todas as entradas que estão na linguagem e diz que decide uma linguagem se, adicionalmente, rejeitar todos entradas que não estão na linguagem (certas entradas podem fazer com que uma máquina de Turing funcione para sempre, então a decidibilidade coloca a restrição adicional sobre a capacidade de reconhecimento que a máquina de Turing deve parar em todas as entradas). Uma máquina de Turing que "resolve" um problema geralmente significa aquela que decide a linguagem.

As máquinas de Turing permitem noções intuitivas de "tempo" e "espaço". A complexidade de tempo de uma TM em uma entrada específica é o número de etapas elementares que a máquina de Turing executa para alcançar um estado de aceitação ou rejeição. A complexidade do espaço é o número de células em sua fita que ele usa para alcançar um estado de aceitação ou rejeição.

Máquinas de Turing não determinísticas

Uma comparação de computação determinística e não determinística. Se qualquer ramificação na computação não determinística aceitar, o NTM aceitará.

Uma variante da máquina de Turing determinística (DTM) é a máquina de Turing não determinística (NTM). Intuitivamente, um NTM é apenas uma máquina de Turing normal que possui a capacidade adicional de ser capaz de explorar várias ações futuras possíveis a partir de um determinado estado e "escolher" uma ramificação que aceita (se houver). Ou seja, enquanto um DTM deve seguir apenas um ramo de computação, um NTM pode ser imaginado como uma árvore de computação, ramificando-se em muitos caminhos computacionais possíveis em cada etapa (veja a imagem). Se pelo menos um ramo da árvore parar com uma condição de "aceitar", o NTM aceita a entrada. Desta forma, um NTM pode ser pensado como explorando simultaneamente todas as possibilidades computacionais em paralelo e selecionando um ramo de aceitação. Os NTMs não devem ser modelos fisicamente realizáveis, eles são simplesmente máquinas abstratas teoricamente interessantes que dão origem a uma série de classes de complexidade interessantes (que muitas vezes têm definições equivalentes fisicamente realizáveis).

A complexidade de tempo de um NTM é o número máximo de etapas que o NTM usa em qualquer ramificação de seu cálculo. Da mesma forma, a complexidade de espaço de um NTM é o número máximo de células que o NTM usa em qualquer ramificação de sua computação.

Os DTMs podem ser vistos como um caso especial de NTMs que não fazem uso do poder do não-determinismo. Portanto, todos os cálculos que podem ser realizados por um DTM também podem ser realizados por um NTM equivalente. Também é possível simular qualquer NTM usando um DTM. Portanto, os dois são equivalentes em termos de computabilidade. No entanto, a simulação de um NTM com um DTM geralmente requer mais tempo e / ou recursos de memória; como será visto, o quão significativa essa desaceleração é para certas classes de problemas computacionais é uma questão importante na teoria da complexidade computacional.

Limites de recursos

As classes de complexidade agrupam problemas computacionais por seus requisitos de recursos. Para fazer isso, os problemas computacionais são diferenciados por limites superiores na quantidade máxima de recursos que o algoritmo mais eficiente utiliza para resolvê-los. Mais particularmente, as classes de complexidade estão preocupadas com a taxa de crescimento nos requisitos de recursos para resolver um problema computacional à medida que o tamanho da entrada aumenta. Por exemplo, a quantidade de tempo que leva para resolver problemas na classe de complexidade P cresce relativamente devagar conforme o tamanho da entrada aumenta, enquanto cresce comparativamente rápido para problemas na classe de complexidade EXPTIME (ou mais precisamente, para problemas em EXPTIME que estão fora de P , desde ). Este processo é formalizada usando notação O grande .

Observe que o estudo das classes de complexidade tem como objetivo principal compreender a complexidade inerente necessária para resolver problemas computacionais. Os teóricos da complexidade, portanto, estão geralmente preocupados em encontrar a menor classe de complexidade em que um problema se enquadra e, portanto, preocupados em identificar em qual classe um problema computacional se enquadra usando o algoritmo mais eficiente . Pode haver um algoritmo, por exemplo, que resolve um problema específico em tempo exponencial, mas se o algoritmo mais eficiente para resolver esse problema é executado em tempo polinomial, então a complexidade de tempo inerente desse problema é melhor descrita como polinomial.

Limites de tempo

A complexidade de tempo de um algoritmo em relação ao modelo da máquina de Turing é o número de etapas que uma máquina de Turing leva para executar um algoritmo em um determinado tamanho de entrada. Formalmente, a complexidade de tempo para um algoritmo implementado com uma máquina de Turing M é definida como a função , onde é o número máximo de passos que M executa em qualquer entrada de comprimento n . Por exemplo, digamos que as entradas para M sejam números binários. Então, há, por exemplo, quatro entradas de tamanho dois: 00, 01, 10 e 11. Digamos que executar M em 00 leva dez passos, em 01 leva doze passos, em 10 leva oito passos e em 11 leva quinze passos . O tempo de execução é o máximo destes quatro tempos de execução: .

No entanto, as classes de complexidade estão menos preocupadas com valores de tempo de execução específicos e mais com a classe geral de funções em que a função de complexidade de tempo se enquadra. Por exemplo, a complexidade do tempo é um polinômio ? Uma função logarítmica ? Uma função exponencial ? Ou outro tipo de função? Como as funções de complexidade de tempo exato são frequentemente expressões complicadas, elas são simplificadas usando a notação O grande . Isso leva aos conjuntos mais básicos de classes de complexidade de tempo: DTIME e NTIME . Eles estão definidos da seguinte forma:

  • A classe de complexidade de tempo é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing determinística de tempo.
  • A classe de complexidade de tempo é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing não determinística de tempo.

Por exemplo, se um problema X pode ser resolvido por um algoritmo em execução no tempo, então ele está resolvido desde então . Note que sob a notação O grande é também o caso de que , e assim por diante. Isto significa que DTIME aulas geralmente não são mutuamente exclusivas, mas sim formam uma hierarquia: . Essa natureza hierárquica aparece com frequência entre as classes de complexidade.

Limites de espaço

A complexidade espacial de um algoritmo em relação ao modelo da máquina de Turing é o número de células na fita da máquina de Turing que são necessárias para executar um algoritmo em um determinado tamanho de entrada. Formalmente, a complexidade espacial de um algoritmo implementado com uma máquina de Turing M é definida como a função , onde é o número máximo de células que M usa em qualquer entrada de comprimento n .

As classes de complexidade espacial mais básicas são definidas da seguinte forma:

  • A classe de complexidade do espaço é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing determinística do espaço.
  • A classe de complexidade espacial é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing não determinística espacial.

Classes de complexidade básica

ALL é a classe de todos os problemas de decisão . Muitas classes de complexidade importantes são definidas limitando o tempo ou espaço usado por um algoritmo. Várias classes de complexidade importantes definidas dessa maneira são explicadas a seguir.

Classes de complexidade de tempo

Lembre-se de que a classe de complexidade do tempo é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing determinística do tempo e é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing não determinística do tempo. As classes de complexidade de tempo são frequentemente definidas formalmente em termos dessas duas classes.

P e NP

P é a classe de problemas que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial e NP é a classe de problemas que podem ser resolvidos por uma máquina de Turing não determinística em tempo polinomial. Ou mais formalmente,

Freqüentemente, P é considerado a classe de problemas que podem ser resolvidos "rapidamente" ou "eficientemente" por um computador determinístico, uma vez que a complexidade do tempo de resolução de um problema em P aumenta relativamente devagar com o tamanho da entrada.

Uma característica importante da classe NP é que ela pode ser definida de forma equivalente como a classe de problemas cujas soluções são verificáveis por uma máquina de Turing determinística em tempo polinomial. Ou seja, uma linguagem está em NP se existe uma máquina de Turing de tempo polinomial determinística , referida como o verificador, que toma como entrada uma string e uma string de certificado , e aceita se está na linguagem e rejeita se não estiver na linguagem . Intuitivamente, o certificado atua como uma prova de que a entrada está no idioma. Essa equivalência não apenas destaca uma conexão fundamental entre não determinismo e verificabilidade da solução, mas também fornece um método útil para provar que uma linguagem está em NP - simplesmente identifique um certificado adequado e mostre que ele pode ser verificado em tempo polinomial.

Embora possa parecer haver uma diferença óbvia entre a classe de problemas que podem ser resolvidos de forma eficiente e a classe de problemas que são meramente verificáveis ​​de forma eficiente, P e NP estão na verdade no centro de um dos mais famosos problemas não resolvidos na ciência da computação: o Problema P versus NP . Embora seja conhecido que P NP (intuitivamente, máquinas de Turing determinísticas são apenas uma subclasse de máquinas de Turing não determinísticas que não fazem uso de seu não determinismo; ou sob a definição do verificador, P é a classe de problemas cujos verificadores de tempo polinomial precisam apenas receber a cadeia vazia como seu certificado), não se sabe se NP é estritamente maior que P . Se P = NP , segue-se que o não determinismo não fornece nenhum poder computacional adicional sobre o determinismo no que diz respeito à habilidade de encontrar rapidamente uma solução para um problema; ou seja, ser capaz de explorar todos os ramos possíveis de computação fornece no máximo uma aceleração polinomial em relação à capacidade de explorar apenas um único ramo. Além disso, se seguiria que se a prova para uma instância de problema que pode rapidamente ser verificado para correção existe (ou seja, se o problema está em NP ), então existe também um algoritmo que pode rapidamente construir essa prova (isto é, o o problema está em P ). No entanto, a esmagadora maioria dos cientistas da computação acredita que P NP , e a maioria dos esquemas criptográficos empregados hoje, baseiam-se na suposição de que P NP .

EXPTIME e NEXPTIME

EXPTIME é a classe de problemas de decisão solucionáveis ​​por uma máquina de Turing determinística em tempo exponencial e NEXPTIME é a classe de problemas de decisão solucionáveis ​​por uma máquina de Turing não determinística em tempo exponencial. Ou mais formalmente,

EXPTIME é um superconjunto estrito de P e NEXPTIME é um superconjunto estrito de NP . É ainda o caso de EXPTIME NEXPTIME . Não se sabe se isso é adequado, mas se P = NP, então EXPTIME deve ser igual a NEXPTIME .

Classes de complexidade do espaço

Lembre-se de que a classe de complexidade espacial é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing determinística no espaço e é a coleção de todos os problemas que podem ser decididos por uma máquina de Turing não determinística no espaço. As classes de complexidade de espaço são frequentemente definidas formalmente em termos dessas duas classes.

L e NL

Embora seja possível definir classes de complexidade de tempo logarítmico , essas são classes extremamente estreitas, pois os tempos sublineares nem mesmo permitem que uma máquina de Turing leia a entrada inteira (porque ). No entanto, há um número significativo de problemas que podem ser resolvidos no espaço logarítmico. As definições dessas classes requerem uma máquina de Turing de duas fitas para que seja possível para a máquina armazenar toda a entrada (pode ser mostrado que em termos de computabilidade a máquina de Turing de duas fitas é equivalente à máquina de Turing de duas fitas ) No modelo da máquina de Turing de duas fitas, uma fita é a fita de entrada, que é somente leitura. A outra é a fita de trabalho, que permite tanto a leitura quanto a gravação, e é a fita na qual a máquina de Turing realiza os cálculos. A complexidade do espaço da máquina de Turing é medida como o número de células que são usadas na fita de trabalho.

L é então definido como a classe de problemas solucionáveis ​​no espaço logarítmico em uma máquina de Turing determinística e NL é a classe de problemas solucionáveis ​​no espaço logarítmico em uma máquina de Turing não determinística. Ou mais formalmente,

É sabido disso . No entanto, não se sabe se alguma dessas relações é adequada.

PSPACE e NPSPACE

As classes de complexidade PSPACE e NPSPACE são os análogos espaciais de P e NP . Ou seja, PSPACE é a classe de problemas solucionáveis ​​no espaço polinomial por uma máquina de Turing determinística e NPSPACE é a classe de problemas solucionáveis ​​no espaço polinomial por uma máquina de Turing não determinística. Mais formalmente,

Embora não se saiba se P = NP , o teorema de Savitch mostrou que PSPACE = NPSPACE . Também é conhecido que P PSPACE , que segue intuitivamente do fato de que, uma vez que escrever para uma célula na fita de uma máquina de Turing é definida como levando uma unidade de tempo, uma máquina de Turing operando em tempo polinomial só pode escrever para muitas células polinomialmente. Suspeita-se que P seja estritamente menor que PSPACE , mas isso não foi provado.

EXPSPACE e NEXPSPACE

As classes de complexidade EXPSPACE e NEXPSPACE são os análogos espaciais de EXPTIME e NEXPTIME . Ou seja, EXPSPACE é a classe de problemas solucionáveis ​​no espaço exponencial por uma máquina de Turing determinística e NEXPSPACE é a classe de problemas solucionáveis ​​no espaço exponencial por uma máquina de Turing não determinística. Ou mais formalmente,

O teorema de Savitch estabelece que EXPSPACE = NEXPSPACE . Esta classe é extremamente ampla: é conhecida como um superconjunto estrito de PSPACE , NP e P , e acredita-se que seja um superconjunto estrito de EXPTIME .

Propriedades das classes de complexidade

Fecho

As classes de complexidade têm uma variedade de propriedades de fechamento . Por exemplo, as classes de decisão podem ser fechadas sob negação , disjunção , conjunção ou mesmo sob todas as operações booleanas . Além disso, eles também podem ser fechados sob uma variedade de esquemas de quantificação. P , por exemplo, é fechado em todas as operações booleanas e em quantificação em domínios de tamanho polinomial (embora provavelmente não seja fechado em domínios de tamanho exponencial). As propriedades de fechamento podem ser úteis na separação de classes - um caminho possível para separar duas classes de complexidade é encontrar alguma propriedade de fechamento possuída por uma e não pela outra.

Cada classe X que não é fechado sob negação tem uma classe de complemento de co-X , o qual consiste nos complementos dos idiomas contidos em X . Da mesma forma, pode-se definir o fechamento booleano de uma classe, e assim por diante; isso é, no entanto, menos comumente feito.

As propriedades de fechamento são um dos principais motivos pelos quais muitas classes de complexidade são definidas da maneira que são. Considere, por exemplo, um problema que pode ser resolvido no tempo (ou seja, no tempo linear) e um que pode ser resolvido, na melhor das hipóteses, no tempo. Ambos os problemas estão em P , mas o tempo de execução do segundo cresce consideravelmente mais rápido do que o tempo de execução do primeiro conforme o tamanho da entrada aumenta. Alguém poderia perguntar se seria melhor definir a classe de problemas "eficientemente solucionáveis" usando algum limite polinomial menor, como , em vez de todos os polinômios, o que permite grandes discrepâncias. Acontece, entretanto, que os polinômios são a menor classe de funções que contém as funções lineares que são fechadas por adição, multiplicação e composição. Isso significa que os polinômios são a menor classe que permite a composição de "algoritmos eficientes"; isto é, um algoritmo de tempo polinomial que chama uma sub - rotina de tempo polinomial ainda produz um algoritmo de tempo polinomial. Se o limite fosse utilizado, entretanto, a composição de um número constante de algoritmos "eficientes" pode resultar em um novo algoritmo que não é "eficiente". (Observe que a definição de P também é útil porque, empiricamente, quase todos os problemas em P que são praticamente úteis de fato têm tempos de execução polinomiais de ordem inferior, e quase todos os problemas fora de P que são praticamente úteis não têm algoritmos conhecidos com tempos de execução exponenciais pequenos, ou seja, com tempos de execução próximos de 1.)

Dureza e completude

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 é pelo menos tão difícil quanto outro problema. Por exemplo, se um problema pode ser resolvido usando um algoritmo para , não é mais difícil do que , e dizemos que se reduz a . 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 é difícil para uma classe de problemas C se todos os problemas em C puderem ser reduzidos a . Assim, não há problema em C é mais difícil do que , uma vez que um algoritmo para nos permite resolver qualquer problema em C . Claro, a noção de problemas difíceis depende do tipo de redução que está sendo usado. 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 é em C e é difícil para C , então é dito ser completo para C . Isso significa que esse é o problema mais difícil em C (já que pode haver muitos problemas que são igualmente difíceis, pode-se dizer que é tão difícil quanto os 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 são os que mais provavelmente não estão em P. Porque o problema P  =  NP não é resolvido, podendo reduzir um NP conhecido - um problema completo, Π 2 , para outro problema, Π 1 , indicaria que não há solução em tempo polinomial conhecida para Π 1 . Isso ocorre porque uma solução em tempo polinomial para Π 1 resultaria em uma solução em tempo polinomial para Π 2 . 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 .

Relações entre classes de complexidade

Teorema de Savitch

O teorema de Savitch estabelece que PSPACE = NPSPACE e EXPSPACE = NEXPSPACE . Uma questão central da teoria da complexidade é se o não determinismo adiciona poder significativo a um modelo computacional. Isso é central para o problema aberto P versus NP no contexto do tempo. O teorema de Savitch mostra que, para o espaço, o não determinismo não adiciona significativamente mais potência, onde "significativo" significa a diferença entre os requisitos de recursos polinomiais e superpolinomiais (ou, para EXPSPACE , a diferença entre exponencial e superexponencial). Por exemplo, o teorema de Savitch prova que nenhum problema que requeira espaço exponencial para uma máquina de Turing determinística pode ser resolvido por uma máquina de Turing com espaço polinomial não determinística.

Teoremas de hierarquia

Por definição de DTIME , segue-se que está contido em if , desde if . No entanto, esta definição não dá nenhuma indicação se essa inclusão é estrita. Para requisitos de tempo e espaço, as condições sob as quais a inclusão é estrita são dadas 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. Os teoremas da hierarquia permitem 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.

O teorema da hierarquia do tempo afirma que

.

O teorema da hierarquia espacial afirma que

.

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 estabelece que P está estritamente contido em EXPTIME , e o teorema da hierarquia de espaço estabelece que L está estritamente contido em PSPACE .

Outros modelos de computação

Embora as máquinas de Turing determinísticas e não determinísticas sejam os modelos de computação mais comumente usados, muitas classes de complexidade são definidas em termos de outros modelos computacionais. Em particular,

Eles são explicados em mais detalhes a seguir.

Computação aleatória

Uma série de classes de complexidade importantes são definidas usando a máquina de Turing probabilística , uma variante da máquina de Turing que pode lançar moedas aleatórias. Essas classes ajudam a descrever melhor a complexidade dos algoritmos aleatórios .

Uma máquina de Turing probabilística é semelhante a uma máquina de Turing determinística, exceto que, em vez de seguir uma única função de transição (um conjunto de regras para como proceder em cada etapa do cálculo), ela seleciona probabilisticamente entre várias funções de transição em cada etapa. A definição padrão de uma máquina de Turing probabilística especifica duas funções de transição, de modo que a seleção da função de transição em cada etapa se assemelha a um cara ou coroa. A aleatoriedade introduzida em cada etapa do cálculo introduz o potencial de erro; isto é, cadeias de caracteres que a máquina de Turing deve aceitar podem em algumas ocasiões ser rejeitadas e cadeias de caracteres que a máquina de Turing deve rejeitar podem em algumas ocasiões ser aceitas. Como resultado, as classes de complexidade baseadas na máquina de Turing probabilística são definidas em grande parte em torno da quantidade de erro permitida. Formalmente, eles são definidos usando uma probabilidade de erro . Diz-se que uma máquina de Turing probabilística reconhece uma linguagem com probabilidade de erro se:

  1. uma string em implica que
  2. uma string não significa que

Classes de complexidade importantes

As relações entre as classes de complexidade probabilística fundamentais. BQP é uma classe de complexidade quântica probabilística e é descrito na seção de computação quântica.

As classes fundamentais de complexidade de tempo aleatório são ZPP , RP , co-RP , BPP e PP .

A classe mais estrita é ZPP (tempo polinomial probabilístico de zero erro), a classe de problemas solucionáveis ​​em tempo polinomial por uma máquina de Turing probabilística com probabilidade de erro 0. Intuitivamente, esta é a classe mais estrita de problemas probabilísticos porque não exige nenhum erro .

Uma classe ligeiramente mais flexível é RP (tempo polinomial aleatório), que não mantém nenhum erro para strings que não estejam na linguagem, mas permite erros limitados para strings na linguagem. Mais formalmente, uma linguagem está em RP se houver uma máquina de Turing de tempo polinomial probabilística M tal que, se uma string não estiver na linguagem, então M sempre rejeita e se uma string estiver na linguagem, então M aceita com uma probabilidade de pelo menos 1 / 2. A classe co-RP é definida de forma semelhante, exceto que os papéis são invertidos: o erro não é permitido para strings no idioma, mas é permitido para strings que não estejam no idioma. Juntas, as classes RP e co-RP abrangem todos os problemas que podem ser resolvidos por máquinas de Turing probabilísticas com erro unilateral .

Afrouxar ainda mais os requisitos de erro para permitir o erro bilateral produz a classe BPP (tempo polinomial probabilístico de erro limitado), a classe de problemas solucionáveis ​​em tempo polinomial por uma máquina de Turing probabilística com probabilidade de erro menor que 1/3 (para ambas as strings no idioma e não no idioma). BPP é a mais praticamente relevante das classes de complexidade probabilística - problemas em BPP têm algoritmos randomizados eficientes que podem ser executados rapidamente em computadores reais. BPP também está no centro do importante problema não resolvido na ciência da computação sobre se P = BPP , o que se verdadeiro significaria que a aleatoriedade não aumenta o poder computacional dos computadores, ou seja, qualquer máquina de Turing probabilística poderia ser simulada por uma máquina de Turing determinística com no máximo, desaceleração polinomial.

A classe mais ampla de problemas probabilísticos solucionáveis ​​com eficiência é PP (tempo polinomial probabilístico), o conjunto de linguagens solucionáveis ​​por uma máquina de Turing probabilística em tempo polinomial com uma probabilidade de erro menor que 1/2 para todas as strings.

ZPP , RP e co-RP são todos subconjuntos de BPP , que por sua vez é um subconjunto de PP . A razão para isso é intuitiva: as classes que permitem erro zero e apenas erro unilateral estão todas contidas na classe que permite erro bilateral, e PP simplesmente relaxa a probabilidade de erro do BPP . ZPP refere-se a RP e co-RP da seguinte maneira: . Ou seja, ZPP consiste exatamente naqueles problemas que estão em RP e co-RP . Intuitivamente, isso decorre do fato de que RP e co-RP permitem apenas erros unilaterais: co-RP não permite erros para strings na linguagem e RP não permite erros para strings que não estejam na linguagem. Portanto, se um problema está tanto em RP quanto em co-RP , então não deve haver erro para strings dentro e fora da linguagem (ou seja, nenhum erro qualquer), que é exatamente a definição de ZPP .

As classes importantes de complexidade de espaço aleatório incluem BPL , RL e RLP .

Sistemas de prova interativa

Várias classes de complexidade são definidas usando sistemas de prova interativos . As provas interativas generalizam a definição das provas da classe de complexidade NP e fornecem percepções sobre criptografia , algoritmos de aproximação e verificação formal .

Representação geral de um protocolo de prova interativo

Os sistemas de prova interativos são máquinas abstratas que modelam a computação como a troca de mensagens entre duas partes: um provador e um verificador . As partes interagem trocando mensagens e uma string de entrada é aceita pelo sistema se o verificador decidir aceitar a entrada com base nas mensagens que recebeu do provador. O provador tem poder computacional ilimitado, enquanto o verificador tem poder computacional limitado (a definição padrão de sistemas de prova interativa define o verificador como sendo polinomialmente limitado no tempo). O provador, no entanto, não é confiável (isso evita que todas as linguagens sejam trivialmente reconhecidas pelo sistema de prova, fazendo com que o provador computacionalmente ilimitado resolva se uma string está em uma linguagem e, em seguida, envie um "SIM" ou "NÃO" confiável para o verificador ), portanto, o verificador deve conduzir um "interrogatório" do provador "perguntando" sucessivas rodadas de perguntas, aceitando apenas se desenvolver um alto grau de confiança de que a string está na língua.

Classes de complexidade importantes

A classe NP é um sistema de prova simples no qual o verificador é restrito a ser uma máquina de Turing de tempo polinomial determinística e o procedimento é restrito a uma rodada (isto é, o provador envia apenas uma única prova completa - normalmente referida como o certificado —para o verificador). Dito de outra forma, na definição da classe NP (o conjunto de problemas de decisão para os quais as instâncias do problema, quando a resposta é "SIM", têm provas verificáveis ​​em tempo polinomial por uma máquina de Turing determinística) é um sistema de provas em que o a prova é construída por um provador não mencionado e a máquina de Turing determinística é o verificador. Por esse motivo, NP também pode ser chamado de dIP (prova interativa determinística), embora raramente seja referido como tal.

Acontece que NP captura todo o poder dos sistemas de prova interativos com verificadores determinísticos (tempo polinomial) porque pode ser mostrado que para qualquer sistema de prova com um verificador determinístico nunca é necessário precisar de mais do que uma única rodada de mensagens entre os provador e o verificador. Os sistemas de prova interativa que fornecem maior poder computacional sobre as classes de complexidade padrão, portanto, requerem verificadores probabilísticos , o que significa que as perguntas do verificador para o provador são computadas usando algoritmos probabilísticos . Conforme observado na seção acima sobre computação aleatória , algoritmos probabilísticos introduzem erro no sistema, de modo que as classes de complexidade baseadas em sistemas de prova probabilística são definidas em termos de uma probabilidade de erro ε .

A classe de complexidade mais geral decorrente dessa caracterização é a classe IP (tempo polinomial interativo), que é a classe de todos os problemas solucionáveis ​​por um sistema de prova interativo , onde V é o tempo polinomial probabilístico e o sistema de prova satisfaz duas propriedades: para uma linguagem

  1. (Completude) uma string w em L implica
  2. (Solidez) uma string w não em L implica

Uma característica importante do IP é que ele é igual a PSPACE . Em outras palavras, qualquer problema que possa ser resolvido por um sistema de prova interativa em tempo polinomial também pode ser resolvido por uma máquina de Turing determinística com recursos de espaço polinomial e vice-versa.

Uma modificação do protocolo para IP produz outra classe de complexidade importante: AM (protocolo Arthur-Merlin). Na definição dos sistemas de prova interativa usados ​​pela IP , o provador não foi capaz de ver as moedas utilizadas pelo verificador em seu cálculo probabilístico - ele só foi capaz de ver as mensagens que o verificador produziu com essas moedas. Por esse motivo, as moedas são chamadas de moedas aleatórias privadas . O sistema de prova interativo pode ser restringido de forma que as moedas usadas pelo verificador sejam moedas aleatórias públicas ; ou seja, o provador é capaz de ver as moedas. Formalmente, AM é definido como a classe de línguas com uma prova interativa em que o verificador envia uma string aleatória para o provador, o provador responde com uma mensagem e o verificador aceita ou rejeita aplicando uma função de tempo polinomial determinística ao mensagem do provador. AM pode ser generalizado para AM [ k ], onde k é o número de mensagens trocadas (então na forma generalizada o AM padrão definido acima é AM [2]). No entanto, para todos , AM [ k ] = AM [2]. Também é o caso .

Outras classes de complexidade definidas usando sistemas de prova interativa incluem MIP (tempo polinomial interativo multiprover) e QIP (tempo polinomial interativo quântico).

Circuitos booleanos

Exemplo circuito booleano calcular a função booleana , com exemplo de entrada , e . Os nós são portas AND , os nós são portas OR e os nós NÃO são portas .

Um modelo alternativo de computação à máquina de Turing é o circuito Booleano , um modelo simplificado dos circuitos digitais usados ​​em computadores modernos . Este modelo não apenas fornece uma conexão intuitiva entre computação na teoria e computação na prática, mas também é um modelo natural para computação não uniforme (computação na qual diferentes tamanhos de entrada no mesmo problema usam algoritmos diferentes).

Formalmente, um circuito booleano é um gráfico acíclico direcionado no qual as arestas representam fios (que carregam os valores de bit 0 e 1), os bits de entrada são representados por vértices de origem (vértices sem arestas de entrada) e todos os vértices não-fonte representam lógica portas (geralmente as portas AND , OR e NOT ). Uma porta lógica é designada porta de saída e representa o final do cálculo. O comportamento de entrada / saída de um circuito com variáveis ​​de entrada é representado pela função Booleana ; por exemplo, nos bits de entrada , o bit de saída do circuito é representado matematicamente como . Diz-se que o circuito calcula a função booleana .

Qualquer circuito em particular tem um número fixo de vértices de entrada, portanto, ele só pode agir em entradas desse tamanho. Linguagens (as representações formais de problemas de decisão ), no entanto, contêm cadeias de comprimentos diferentes, portanto, as linguagens não podem ser totalmente capturadas por um único circuito (isso contrasta com o modelo da máquina de Turing, em que uma linguagem é totalmente descrita por uma única máquina de Turing que pode atuar em qualquer tamanho de entrada). Uma linguagem é, portanto, representada por uma família de circuitos . Uma família de circuitos é uma lista infinita de circuitos , onde é um circuito com variáveis ​​de entrada. Diz-se que uma família de circuitos decide um idioma se, para cada string , está no idioma se e somente se , onde está o comprimento de . Em outras palavras, uma string de tamanho está na linguagem representada pela família de circuitos se o circuito (o circuito com o mesmo número de vértices de entrada que o número de caracteres em ) for avaliado como 1 quando for sua entrada.

Enquanto as classes de complexidade definidas usando máquinas de Turing são descritas em termos de complexidade de tempo , as classes de complexidade do circuito são definidas em termos de tamanho do circuito - o número de vértices no circuito. A complexidade de tamanho de uma família de circuitos é a função , onde é o tamanho do circuito de . As classes de funções familiares decorrem naturalmente disso; por exemplo, uma família de circuitos de tamanho polinomial é aquela em que a função é um polinômio .

Classes de complexidade importantes

A classe de complexidade P / poly é o conjunto de linguagens que podem ser decididas por famílias de circuitos de tamanho polinomial. Acontece que existe uma conexão natural entre a complexidade do circuito e a complexidade do tempo. Intuitivamente, uma linguagem com pequena complexidade de tempo (ou seja, requer relativamente poucas operações sequenciais em uma máquina de Turing), também possui uma pequena complexidade de circuito (ou seja, requer relativamente poucas operações booleanas). Formalmente, pode-se mostrar que se uma linguagem está em , onde está uma função , então ela tem complexidade de circuito . Resulta diretamente deste fato que . Em outras palavras, qualquer problema que pode ser resolvido em tempo polinomial por uma máquina de Turing determinística também pode ser resolvido por uma família de circuitos de tamanho polinomial. É ainda o caso em que a inclusão é adequada, ou seja (por exemplo, existem alguns problemas indecidíveis que estão em P / poli ).

P / poly tem várias propriedades que o tornam altamente útil no estudo das relações entre classes de complexidade. Em particular, é útil na investigação de problemas relacionados a P versus NP . Por exemplo, se houver qualquer linguagem em NP que não seja em P / poli , então . P / poly também é útil na investigação de propriedades da hierarquia polinomial . Por exemplo, se NPP / poli , então PH reduz para . Uma descrição completa das relações entre P / poli e outras classes de complexidade está disponível em " Importância de P / poli ". P / poly também é útil no estudo geral das propriedades das máquinas de Turing , já que a classe pode ser definida de forma equivalente como a classe de linguagens reconhecidas por uma máquina de Turing de tempo polinomial com uma função de conselho limitada por polinômio .

Duas subclasses de P / poli que têm propriedades interessantes por si mesmas são NC e AC . Essas classes são definidas não apenas em termos de tamanho do circuito, mas também em termos de profundidade . A profundidade de um circuito é o comprimento do caminho direcionado mais longo de um nó de entrada ao nó de saída. A classe NC é o conjunto de linguagens que podem ser resolvidas por famílias de circuitos que se restringem não apenas a ter tamanho polinomial, mas também a ter profundidade polilogarítmica. A classe AC é definida de forma semelhante a NC , porém as portas podem ter fan-in ilimitado (ou seja, as portas AND e OR podem ser aplicadas a mais de dois bits). NC é uma classe notável porque pode ser definida de forma equivalente como a classe de linguagens que possuem algoritmos paralelos eficientes .

Computação quântica

As classes BQP e QMA , que são de importância fundamental na ciência da informação quântica , são definidas usando máquinas de Turing quânticas .

Outros tipos de problemas

Embora a maioria das classes de complexidade sejam conjuntos de problemas de decisão , também há várias classes de complexidade definidas em termos de outros tipos de problemas. Em particular, existem classes de complexidade que consistem em problemas de contagem , problemas de função e problemas de promessa . Eles são explicados em mais detalhes a seguir.

Problemas de contagem

Um problema de contagem pergunta não apenas se existe uma solução (como acontece com um problema de decisão ), mas pergunta quantas soluções existem. Por exemplo, o problema de decisão CYCLE pergunta se um determinado grafo G tem um ciclo simples (a resposta é um simples sim / não); o problema de contagem correspondente (pronuncia-se "ciclo acentuado") pergunta quantos ciclos simples G tem. A saída para um problema de contagem é, portanto, um número, em contraste com a saída para um problema de decisão, que é um simples sim / não (ou aceitar / rejeitar, 0/1 ou outro esquema equivalente). Assim, enquanto os problemas de decisão são representados matematicamente como linguagens formais , os problemas de contagem são representados matematicamente como funções : um problema de contagem é formalizado como a função tal que, para uma entrada , é o número de soluções. Por exemplo, no CICLO problema, a entrada é um gráfico G (representada como uma cadeia de bits de ) e é o número de ciclos simples em L .

Problemas de contagem provenientes de um número de campos, incluindo a estimativa estatística , física estatística , projeto de rede e economia .

Classes de complexidade importantes

#P (pronuncia-se "P agudo") é uma classe importante de problemas de contagem que pode ser considerada a versão de contagem de NP . A conexão com NP surge do fato de que o número de soluções para um problema é igual ao número de ramos aceitáveis em uma árvore de computação não determinística da máquina de Turing . #P é, portanto, formalmente definido da seguinte forma:

#P é o conjunto de todas as funções tal que existe uma máquina de Turing não determinística de tempo polinomial M tal que, para todos , é igual ao número de ramos aceitáveis ​​na árvore de computação de M em w .

E assim como NP pode ser definido em termos de não-determinismo e em termos de um verificador (isto é, como um sistema de prova interativo ), também pode #P ser definido de forma equivalente em termos de um verificador. Lembre-se de que um problema de decisão está em NP se houver um certificado verificável em tempo polinomial para uma determinada instância de problema - isto é, NP pergunta se existe uma prova de associação (um certificado) para a entrada que pode ser verificada quanto à exatidão no polinômio Tempo. A classe #P pergunta quantos certificados existem. Neste contexto, #P é definido da seguinte forma:

#P é o conjunto de funções de tal modo que existe um polinomial e um tempo polinomial máquina de Turing V (o verificador), de tal modo que para cada , . Em outras palavras, é igual ao tamanho do conjunto que contém todos os certificados de tamanho polinomial.

Problemas de função

Problemas de contagem são um subconjunto de uma classe mais ampla de problemas denominados 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 . Para problemas de função, a saída não é simplesmente 'sim' ou 'não'. A classe de complexidade FP é o conjunto de problemas de funções que podem ser resolvidos por uma máquina de Turing determinística em tempo polinomial .

Problemas de promessa

Resumo das relações entre as classes de complexidade

A tabela a seguir mostra algumas das classes de problemas consideradas na teoria da complexidade. Se a classe X for um subconjunto estrito de Y , então X será mostrado abaixo de Y com uma linha escura conectando-os. Se X for um subconjunto, mas não se sabe se são conjuntos iguais, a linha é mais clara e pontilhada. Tecnicamente, a divisão em decidível e indecidível pertence mais ao estudo da teoria da computabilidade , mas é útil para colocar as classes de complexidade em perspectiva.

Problema de Decisão
SolidLine.png SolidLine.png
Tipo 0 (enumerável recursivamente)
Indecidível
SolidLine.png
Decidível
SolidLine.png
EXPSPACE
DottedLine.png
PRÓXIMA HORA
DottedLine.png
EXPTIME
DottedLine.png
PSPACE
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
Tipo 1 (sensível ao contexto)
SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
co-NP
BQP
NP
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png DottedLine.png
BPP
DottedLine.png
SolidLine.png SolidLine.png DottedLine.png DottedLine.png DottedLine.png
SolidLine.png SolidLine.png
P
SolidLine.png SolidLine.png DottedLine.png
SolidLine.png
NC
SolidLine.png SolidLine.png
Tipo 2 (sem contexto)
SolidLine.png
Tipo 3 (normal)

Veja também

Referências

Bibliografia

Leitura adicional

  • The Complexity Zoo : Uma enorme lista de classes de complexidade, uma referência para especialistas.
  • Neil Immerman . "Teoria da Complexidade Computacional" . Arquivado do original em 16/04/2016. Inclui um diagrama que mostra a hierarquia das classes de complexidade e como elas se encaixam.
  • Michael Garey e David S. Johnson : Computadores e Intratabilidade: Um Guia para a Teoria da NP-Completude. Nova York: WH Freeman & Co., 1979. A referência padrão sobre problemas NP-Completos - uma importante categoria de problemas cujas soluções parecem exigir um tempo impraticávelmente longo para serem computadas.