O que é fácil para um computador fazer e o que é quase impossível? Essas questões estão no centro da questão da complexidade computacional. Apresentamos um mapa dessa paisagem.
Diferentes classes de complexidade classificam as tarefas de forma hierárquica. Uma classe pode conter todas as tarefas de outra, além de tarefas que requerem recursos de computação adicionais.Qual é a dificuldade fundamental da tarefa? Essa é a formulação da tarefa básica dos cientistas da computação que estão tentando classificar as tarefas pelas chamadas.
classes de dificuldade . Esses são grupos que contêm todas as tarefas de computação que exigem não mais do que uma quantidade fixa de recursos de computação - como tempo ou memória. Vamos dar um exemplo simples com um número grande como 123 456 789 001. Pode-se perguntar: é um número primo - um que divide apenas 1 e ele próprio? Os cientistas da computação podem responder com algoritmos rápidos - de modo que eles não comecem a desacelerar em números arbitrariamente grandes. No nosso caso, verifica-se que esse número não é primo. Então podemos fazer a pergunta: quais são seus principais fatores? Mas não existe um algoritmo rápido para respondê-lo - somente se você usar um computador quântico. Portanto, os cientistas da computação acreditam que essas duas tarefas pertencem a diferentes classes de complexidade.
Existem muitas classes diferentes de dificuldade, embora na maioria dos casos os pesquisadores não tenham conseguido provar que uma classe é claramente diferente das outras. A evidência de diferenças entre as classes é uma das tarefas mais difíceis e importantes nessa área.
A diferença entre as classes pode ser pouco distinguível ou óbvia, e é bastante difícil entender bem todas as classes. Portanto, compilamos este guia para as sete classes de dificuldade mais fundamentais. E sim, você não confundirá mais BPP e BQP.
P
Denota : tempo polinomial
Breve descrição : todas as tarefas que um computador clássico (não quântico) pode resolver facilmente.
Descrição exata : os algoritmos da classe P devem parar de funcionar e fornecer a resposta correta em não mais que o tempo n
c , onde n é o comprimento dos dados de entrada, c é uma constante.
Tarefas típicas :
- O número é primo?
- Qual é o caminho mais curto entre dois pontos?
O que os pesquisadores gostariam de saber : P coincide com NP? A coincidência revolucionaria a ciência da computação e tornaria a maioria dos sistemas criptográficos sem sentido (mas quase ninguém acredita nisso).
NP
Denota : tempo polinomial não determinístico
Breve descrição : todas as tarefas que um computador clássico pode facilmente verificar se há uma solução.
Descrição exata : o problema se enquadra na classe NP quando, se a resposta for sim, existe uma breve prova da exatidão da resposta. Se a entrada for uma sequência X e você precisar decidir se a resposta corresponde "sim", uma breve prova será outra sequência, Y, que pode ser usada para verificar a resposta correta "sim" em tempo polinomial. (Y às vezes é chamado de “testemunha curta” - todas as tarefas do NP têm testemunhas curtas, graças às quais podem ser verificadas).
Tarefas típicas :
- A tarefa de clicar . Imagine um gráfico com arestas e vértices - por exemplo, os vértices indicam usuários da rede social e a aresta indica que eles são "amigos". Uma clique é um subconjunto deste gráfico no qual todas as pessoas são amigas uma da outra. Você pode fazer as seguintes perguntas sobre o gráfico: há um clique de 20 pessoas nele? 50 pessoas? 100? Encontrar uma camarilha é uma tarefa completa do NP , ou seja, sua complexidade é a mais alta de todas as tarefas do NP. Porém, é fácil verificar uma resposta em potencial - um subconjunto de 50 nós que pode ou não ser um clique -.
- A tarefa do vendedor . Dado um conjunto de cidades com distâncias entre dois pares - existe uma maneira de percorrer todas as cidades, dirigindo menos de uma certa distância? Por exemplo, um vendedor pode viajar por todas as capitais dos EUA com menos de 11.000 milhas?
O que os pesquisadores gostariam de saber: P = NP? Especialistas em ciência da computação e não chegaram nem perto de resolver esse problema.
PH
Denota : hierarquia polinomial
Breve descrição : PH é uma generalização de NP. Ele contém todas as tarefas que podem ser obtidas iniciando com uma tarefa do NP e impondo níveis adicionais de dificuldade.
Descrição exata : O PH contém tarefas com vários "quantificadores" diferentes que complicam essas tarefas. Um exemplo de um problema com diferentes quantificadores: se recebermos X, existe Y tal que, para cada Z, exista W para o qual R seja satisfeito? Quanto mais quantificadores no problema, mais complicado ele é e maior a hierarquia polinomial.
Uma tarefa típica é determinar se realmente há um clique no tamanho 50 e se não há um clique no tamanho 51.
O que os pesquisadores gostariam de saber : ninguém foi capaz de provar que a HP é diferente de P. Esse problema é equivalente à igualdade de P e NP, porque se de repente ocorrer P = NP, todos os PHs serão reduzidos a P (P = PH).
PSPACE
Indica : restrição de espaço polinomial
Breve descrição : PSPACE contém todas as tarefas que podem ser resolvidas usando uma quantidade razoável de memória.
Descrição exata : Ao resolver tarefas do PSPACE, você não se preocupa mais com o tempo, apenas com a quantidade de memória necessária para o algoritmo funcionar. Cientistas da computação provaram que o PSPACE contém um PH que contém NP que contém P.
Tarefa típica : todas as tarefas de P, NP e PH estão contidas no PSPACE.
O que os pesquisadores gostariam de saber : PSPACE é diferente de P?
Bqp
Denota : tempo polinomial quântico com limitação de probabilidade de erro
Breve descrição : todas as tarefas que podem ser facilmente resolvidas em um computador quântico.
Descrição exata : todas as tarefas que podem ser resolvidas em um computador quântico no tempo polinomial.
Problema típico : encontre os fatores primos de um número inteiro.
O que os pesquisadores gostariam de saber : Até agora, ficou provado que o BQP está contido no PSPACE e que o BQP contém P. Os pesquisadores não sabem se o BQP está contido no NP, mas acreditam que essas duas classes não podem ser comparadas - existem tarefas que fazem parte do NP, mas não no BQP e vice-versa.
EXPTIME
Denota : tempo exponencial
Breve descrição : todas as tarefas que podem ser resolvidas em tempo exponencial em um computador clássico.
Descrição exata : EXP contém todas as classes anteriores - P, NP, PH, PSPACE e BQP. Os pesquisadores provaram que é diferente de P - eles descobriram tarefas que fazem parte do EXP e não do P.
Tarefa típica : generalização de jogos como xadrez e damas. Se um tabuleiro de xadrez puder ser de qualquer tamanho, a tarefa de determinar se um dos jogadores tem uma vantagem se torna tarefa da EXP.
O que os pesquisadores gostariam de saber : eles gostariam de provar que o PSPACE não contém EXP. Eles acreditam que existem tarefas que fazem parte do EXP, mas não fazem parte do PSPACE, porque às vezes leva muito tempo para resolver uma tarefa do EXP. Os pesquisadores sabem como separar EXP e P.
BPP
Denota : tempo polinomial com limitação de probabilidade de erro
Breve descrição : tarefas que podem ser resolvidas rapidamente usando algoritmos que usam aleatoriedade.
Descrição exata : BPP é o mesmo que P, com a diferença de que o algoritmo pode incluir etapas nas quais as decisões são tomadas aleatoriamente. Os algoritmos no BPP precisam fornecer as respostas corretas com uma probabilidade próxima a 1.
Tarefa típica : você tem duas fórmulas diferentes que fornecem polinômios com muitas variáveis. Essas fórmulas calculam o mesmo polinômio? Essa é a tarefa de verificar a identidade polinomial.
O que os pesquisadores gostariam de saber : BPP e P. são iguais? Se são iguais, qualquer algoritmo com aleatoriedade pode ser eliminado da aleatoriedade. Eles acreditam que é - que para todo problema para o qual existe um algoritmo aleatório eficaz, existe um algoritmo determinístico eficaz - mas eles ainda não foram capazes de provar isso.