Computação Quântica/Capítulo 3
Introdução a Ciência da Computação
Complexidade Computacional (3.2.2)
- Complexidade computacional é o estudo do tempo e do espaço necessários para solucionar problemas computacionais.
- Geralmente os problemas são chamados de fáceis, tratáveis ou viáveis quando existe solução de ordem polinomial, ou são chamados de difíceis, intratáveis ou inviáveis quando a solução existente não é polinomial, mas, sim, exponencial.
- Há uma ênfase na preferência por soluções polinomiais, óbvio já que são bem mais eficientes que as soluções exponenciais, mas não é por isso que deve-se deixar de fazer uma análise comparativa entre as soluções possíveis.
- A forte tese de Church-Turing afirma que se um problema não tem solução polinomial em uma máquina de Turing probabilística então não tem solução eficiente em outro dispositivo de computação.
Mais sobre Classes de Complexidade (3.2.4)
- O estudo de classes de complexidade na computação é essencial para o entendimento do poder de resolver problemas;
- Para compreender quão poderoso venha a ser um computador quântico devemos entender os problemas por este solúveis e verificar a relação das classes de complexidade nestes termos;
Classes de Complexidade
- São definidas por três variáveis: os recursos (tempo de computação, espaço na fita, quantidade de movimentação do cabeçote da máquina, etc), o tipo de problemas, e o modelo computacional em questão (Máquina de Turing determinística, MT não determinística, computador quântico, etc).
- Até agora o interesse maior foi em examinar as classes com recursos no tempo. Agora vamos examinar a classe PSPACE que se refere a problemas computáveis em uma máquina de turing, sem limite no tempo mas com uma quantidade polinomial de espaço.
- Não é provado que
- Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: . Percebamos que se: existem problemas eficientemente solúveis por um computador quântico, mas não por um computador clássico, pode-se concluir que: .
- A relação entre classes é conhecida: (No livro de Papadimitriou sobre Complexidade Computacional, seção 7.3 encontra-se boas explicações sobre grande parte desta relação)
Tratando problemas não computáveis
- Existem duas formas de lidar com problemas NP-Completos ou de outra classe não computável? Duas abordagens possíveis são: reduzir o problema a casos especiais mais plausíveis de computação, ou mudar a natureza do problema considerado.
- A segunda abordagem remete a um importante conceito: A redução de problemas em outros.
- Também em Papadimitriou capítulo 8, toda uma teoria sobre Redução é descrita. Segue uma idéia inicial;
- Redução sejam A e B problemas, B é redutível a A se existe uma transformação R (de computação fácil - no espaço) em que, para todo input x de B é possível a produção de um R(x) que resolva A.
- Desta forma, a computação de B se reduz a geração de R(x) e a computação de A.
- A é ao menos da ordem de B.
- Um exemplo: Seja uma MT probabilística, que decide a próxima ação jogando uma moeda. Tal máquina M decide linguagens . Se então M aceita x com uma probabilidade de no mínimo e se então M rejeita x com probabilidade de no mínimo .
- Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser essencialmente 1.
- BPP pode ser considerada a classe realmente computável por máquinas clássicas com uma equivalente BQP no estudo de máquinas quânticas.
Outros modelos Computacionais (3.3)
- As máquina de Turing não é o único modelo computacional vigente. Outros modelos conseguem aumentar o desempenho de uma MT sem necessariamente alterar a classe de complexidade dos problemas a serem resolvidos.
- Um primeiro exemplo é a computação paralela. Uma MT é capaz de simular uma máquina de processamento paralelo em tempo polinomial, tanto em relação a tempo quanto a espaço.
- Computadores de DNA se apresentam como uma proposta atraente para computação em paralelo. Combinando aleatoriamente diversas bases nitrogenadas e posteriormente selecionando as seqüências que satisfazem determinadas condições, econtramos soluções para problemas pouco tratáveis, como encontrar caminhos hamiltonianos. Computadores de DNA não aumentam a quantidade de problemas , mas pelo fato deste permitir um número extremamente grande de moléculas processando paralelamente, o uso de DNA pode ser útil para diversas aplicações.
- Computadores analógicos têm a aparente vantagem de possuir uma quantidade ilimitada de estados, possibilitando uma memória teoricamente infinita, entretanto em sistemas reais, o ruído faz com que os computadores analógicos tenham uma quantidade finita de estados independentes, caso contrário estarão sujeitos a uma alta taxa de erro. Os computadores digitais possuem uma taxa de erro bem menor, tornando-se na prática mais atrativos que os analógicos.