P, NP, PSPACE e BQP

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

https://ideiasesquecidas.com/

Entre no grupo de estudos de Computação Quântica:

https://www.facebook.com/groups/1013309389112487

Satya Nadella (CEO Microsoft), sobre computação quântica

O indiano Satya Nadella é o atual CEO da Microsoft, empresa fundada por Bill Gates. Nadella foi o responsável pelas grandes mudanças recentes da empresa, como direcionar esforços para cloud (ex. o Office 365 é extremamente poderoso).

No livro “Hit Refresh”, ele cita três tecnologias disruptivas: realidade mista, inteligência artificial e computação quântica. Não à toa, a Microsoft está investindo pesado nas três áreas.

Abaixo algumas frases, sobre computação quântica.

A computação quântica nos permitirá ir além do limite da Lei de Moore – a observação de que o número de transístores num chip de computador dobra a cada 2 anos – mudando a própria física da computação como conhecemos hoje.

Uma empresa de tecnologia que perde múltiplas tendências como esta ficará inevitavelmente para trás. Ao mesmo tempo, é perigoso perseguir tecnologias futuras não testadas e negligenciar o core do negócio atual. É o clássico dilema do inovador – arriscar o sucesso existente ao perseguir novas oportunidades.

Se construir um computador quântico fosse fácil, já teria sido feito.

Ao invés de apenas 0 ou 1 como num bit clássico, qubits podem estar em superposição, que permite várias computações simultâneas. Num algoritmo quântico propriamente construído, de acordo com um de nossos cientistas, ocorre um grande massacre em que todas ou muitas das respostas erradas são canceladas.

Problemas que computadores clássicos demorariam séculos para resolver, poderiam ser resolvidos por computadores quânticos em poucos minutos ou horas. Por exemplo, os níveis atuais de criptografia. Um computador atualmente demandaria 1 bilhão de anos para quebrar o RSA-2048, mas um computador quântico conseguiria quebrar em menos de 2 minutos. Felizmente, a computação quântica também revolucionará a computação clássica e a criptografia, levando a maior segurança ainda.

Computação quântica é o Santo Graal da tecnologia.

Links:

https://www.ciodive.com/news/microsofts-ceo-nadella-ai-mixed-reality-quantum-computing/507134/

https://arstechnica.com/gadgets/2017/09/microsoft-quantum-toolkit/

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/