Um breve resumo dessa sopa de letrinhas da complexidade computacional.
P – Problemas que podem ser RESOLVIDOS em tempo polinomial.
NP – Problemas que podem ser VERIFICADOS em tempo polinomial.
NP complete – Os problemas mais difíceis da classe NP.
PSPACE – Problemas que necessitam de uma quantidade polinomial de memória.
BQP – Problemas de podem ser resolvidos eficientemente num computador quântico.
Uma explicação mais elaborada.
P – São os problemas “fáceis” de serem resolvidos.
NP – São os problemas “fáceis” de serem verificados. Ou seja, dada uma resposta, é fácil verificar se ela atende ou não o problema. Porém, não é necessariamente fácil chegar à solução.
Portanto, podem existir problemas que são fáceis de verificar, porém difíceis de resolver.
Exemplo simples. Rearrumar a palavra a seguir:
lrsdhreeaaamb
É bem mais difícil encontrar a solução do que verificar que “desembaralhar” é a resposta.
Os problemas mais difíceis de todos os NP são chamados NP-Completos. Diversos problemas da vida real, como o da Satisfiabilidade, são NP-Completos.
Existe também o NP-Hard, que são problemas pelo menos tão difíceis quanto os NP-completo. Problemas de otimização são assim. NP-Completo é achar uma solução, o NP-Hard, achar a melhor solução. O famoso problema do Caixeiro-Viajante é um exemplo de problema de otimização.
Um grande problema não resolvido do mundo é se P = NP. Até hoje, não foi possível provar que são iguais ou não diferentes. É, inclusive, um dos desafios do milênio do Instituto Clay, valendo 1 milhão de dólares!
O BQP são problemas resolvíveis por um computador quântico. Suspeita-se que seja possível resolver problemas mais difíceis que a classe P, porém sem resolver o NP-completo.
Portanto, a figura que representa os graus de complexidade é apenas uma ideia. Se P for igual a NP, nem precisaríamos de computador quântico! Bastaria usar esse algoritmo, que resolve problemas difíceis de forma fácil.
O problema P vs NP é complicado de provar, não à toa, até hoje não foi resolvido.
Porém, até hoje os problemas difíceis continuam difíceis, o que é um forte indício de que P é diferente de NP, e que problemas difíceis continuarão difíceis – e que computadores quânticos serão muito úteis.
https://pt.wikipedia.org/wiki/BQP
https://en.wikipedia.org/wiki/P_versus_NP_problem
Ideias técnicas com uma pitada de filosofia
Entre no grupo de estudos de Computação Quântica:
ideiasesquecidas.com 
Republicou isso em Computação e Informação Quântica.
CurtirCurtir