Computação Quântica/Capítulo 3: mudanças entre as edições
Sem resumo de edição |
imported>NiginiOliveira ("Resumo" do capítulo 3 do livro: Quantum Computation and Quantum Information de Nielsen & Chuang) |
||
Linha 1: | Linha 1: | ||
== Introdução a Ciência da Computação == | |||
=== Mais sobre Classes de Complexidade (3.2.4) === | |||
* O estudo de classes de complexidade na computação é excencial para o entendimento do poder de resolver problemas; | |||
* Para compreender quão poderoso venha a ser um \emph{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 emph{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. | |||
** ${P \subset PSPACE}$ | |||
** ${NP \subset PSPACE}$ | |||
** Não é provado que ${P\! \subset PSPACE}$ | |||
** Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: ${CQ \subset PSPACE}$. 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: ${P \neq PSPACE}$. | |||
* A relação entre classes é conhecida: ${L \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP}$ (Em \cite{complexidade-papa}, seção 7.3 encontra-se boas explicações sobre grande parte desta relação) | |||
\end{itemize} | \end{itemize} | ||
\ | ==== Tratando problemas não computáveis ==== | ||
* Existem duas formas de lidar com problemas \emph{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. | |||
** Em \cite{complexidade-papa} capítulo 8, toda uma teoria sobre \emph{Redução} é descrita. Segue uma idéia inicial; | |||
** \emph{Redução} sejam A e B problemas, B é redutível a A se existe uma transformação R (de computação fácil - O(${\log{}{n}}$) no espaço) em que, para todo input \emph{x} de B é possível a produção de um \emph{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 \emph{jogando uma moeda}. Tal máquina M decide linguagens ${L \in BPP}$. Se ${x \in L}$ então M aceita x com uma probabilidade de no mínimo ${\frac{3}{4}}$ e se ${x \notin L}$ então M rejeita x com probabilidade de no mínimo ${\frac{3}{4}}$. | |||
\ | |||
* Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser excencialmente 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. | |||
Edição das 19h39min de 11 de julho de 2005
Introdução a Ciência da Computação
Mais sobre Classes de Complexidade (3.2.4)
- O estudo de classes de complexidade na computação é excencial para o entendimento do poder de resolver problemas;
- Para compreender quão poderoso venha a ser um \emph{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 emph{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.
- ${P \subset PSPACE}$
- ${NP \subset PSPACE}$
- Não é provado que ${P\! \subset PSPACE}$
- Sendo CQ a classe de problemas solúveis por um computador quântico em tempo polinomial, sabe-se que: ${CQ \subset PSPACE}$. 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: ${P \neq PSPACE}$.
- A relação entre classes é conhecida: ${L \subseteq P \subseteq NP \subseteq PSPACE \subseteq EXP}$ (Em \cite{complexidade-papa}, seção 7.3 encontra-se boas explicações sobre grande parte desta relação)
\end{itemize}
Tratando problemas não computáveis
- Existem duas formas de lidar com problemas \emph{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.
- Em \cite{complexidade-papa} capítulo 8, toda uma teoria sobre \emph{Redução} é descrita. Segue uma idéia inicial;
- \emph{Redução} sejam A e B problemas, B é redutível a A se existe uma transformação R (de computação fácil - O(${\log{}{n}}$) no espaço) em que, para todo input \emph{x} de B é possível a produção de um \emph{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 \emph{jogando uma moeda}. Tal máquina M decide linguagens ${L \in BPP}$. Se ${x \in L}$ então M aceita x com uma probabilidade de no mínimo ${\frac{3}{4}}$ e se ${x \notin L}$ então M rejeita x com probabilidade de no mínimo ${\frac{3}{4}}$.
- Uma importante observação sobre o exemplo acima é que se o algoritmo for repetido algumas vezes a probabilidade de sucesso pode ser excencialmente 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.