P, NP, PSPACE e BQP

Um breve resumo dessa sopa de letrinhas da complexidade computacional.

P - Problemas que podem ser RESOLVIDO 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…

Ver o post original 228 mais palavras

Deixe um comentário

Faça o login usando um destes métodos para comentar:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s