Obra: Computação Quântica/Capítulo 3
Matéria: Filosofia
introdução ciência da computação volte para página principal do livro clicando aqui circuitos máquina de turing mt modelo de circuitos são modelos computacionais equivalentes uma mt similar um algoritmo modelo de circuitos semelhante implementação real dos computadores circuitos são acíclicos são formados por fios portas os fios carregam informação as portas realizam tarefas computacionais simples portas lógicas são funções onde representa os bits de entrada os bits de saída funções do tipo com bits de entrada um único bit de saída são conhecidas como funções booleanas seus circuitos correspondentes são circuitos booleanos máquina de turing modelo de circuitos estão ligados através do conceito de família uniforme de circuitos uma família de circuitos uma coleção de circuitos representada por cn onde um inteiro positivo um circuito cn possui bits de entrada um número finito de bits de trabalho saída uma família de circuitos dita uma família uniforme de circuitos se existe um algoritmo em uma mt que gere descrição de cn caso não exista uma mt que gere descrição de cn esta família dita não uniforme circuitos desempenham diversas computações classe de funções computáveis por uma família uniforme de circuitos mesma classe de funções computáveis por mt como quantificar recursos computacionais muitas vezes pequenas mudanças em um algoritmo alteram quantidade ou intensidade de recursos que ele necessita para sua execução exemplo de pergunta de interesse quantos passos de tempo espaço energia são necessários para computação de um algorítmo notação assintótica utilizada fim de representar comportamento essencial de uma função serve de medida de comparação entre os diversos tipos de algoritmos leva em consideração número de passos precisos para sua computação durante intervalos de tempo longos somente termo de maior grandeza realmente importa numa análise de recursos gastos por um algorítimo em log termo que vai interessar para grande será apenas mais ainda tendo constants como de importância secundária temos que expressão cresce linearmente ou seja como big limita superiormente uma função se existirem um um tais que big omega limita inferiromente uma função se existirem um um tais que big teta limita superior inferiormente uma função se for ao mesmo tempo ou seja se existirem tais que para complexidade computacional complexidade computacional estudo dos recursos eg tempo 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 para mesmo são chamados de difíceis intratáveis ou inviáveis quando solução existente não polinomial mas sim exponencial há uma ênfase na preferência por soluções polinomiais isso se dá por serem em geral 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 tese forte de church turing afirma que se um problema não tem solução polin
re as soluções possíveis tese forte 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 problemas de decisão complexidade np problemas de decisão muitos problemas computacionais são mais facilmente formulados com problemas de decisão que tem como resposta sim ou não por exemplo número dado um número primo ou não este um problema de decisão primária uma linguagem sobre alfabeto um subconjunto do conjunto de todos os símbolos de por exemplo se então pertence os problemas de decisão podem ser codificados de uma maneira simples usando problemas com linguagens por exemplo problema de decisão do primo pode ser codificado usando alfabeto binário conjunto pode ser interpretado como números inteiros não negativos por exemplo pode ser interpretado como número em inteiro linguagem definida de forma conter todas as combinações binárias tais que número gerado por ela seja primo para resolver problema de decisão de números primos preciso ter uma maquina de turing que dado um número em sua fita de entrada tivesse como saídas respostas do tipo sim se for primo não quando não for um número primo complexidade np as classes de complexidades são definidas para ser uma coleção de linguagens há problemas que não podem ser resolvidos em tempo polinomial infelizmente provar que algum problema dado não pode ser resolvido em tempo polinomial parece ser muito difícil um exemplo de problema de decisão que se acredita que não estar na classe de complexidade problema fatoração supondo que seja diferente de np possível provar que há uma classe não vazia para problemas intermediários npi np intermediário os quais não são solucionados com recursos polinomiais nem com np completo obviamente não há nenhum problema conhecido que esteja em npi mas há diversos problemas que são considerados como sendo prováveis candidatos npi dois dos candidatos os mais fortes são os problemas de fatoração os de grafos isomórficos na teoria de complexidade computacional co np uma classe de complexidade que complemento da classe np ou seja classe dos problemas em que verificação das provas são não instanciáveis problema sat um outro problema de decisão da teoria da complexidade nele defini se uma expressão booleana escrita usando somente and or not variáveis parêntesis na matemática uma fórmula da lógica proposicional dita satisfatível se os valores verdades puderem ser atribuídos as suas variáveis classe das fórmulas satisfatíveis pertence classe np completo mais sobre classes de complexidade estudo de classes de complexidade na computação essencial para entendimento do poder de resolver problemas para compreender quão poderoso venha ser um computador quântico devemos entender os problemas por este solúveis verificar 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 quantidad
mplexidade 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 tipo de problemas modelo computacional em questão máquina de turing determinística mt não determinística computador quântico etc até agora interesse maior foi em examinar as classes com recursos no tempo agora vamos examinar classe pspace que se refere 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 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 relação entre classes conhecida no livro de papadimitriou sobre complexidade computacional seção 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 problema casos especiais mais plausíveis de computação ou mudar natureza do problema considerado segunda abordagem remete um importante conceito redução de problemas em outros também em papadimitriou capítulo toda uma teoria sobre redução descrita segue uma idéia inicial redução sejam problemas redutível se existe uma transformação de computação fácil no espaço em que para todo input de possível produção de um que resolva desta forma computação de se reduz geração de computação de ao menos da ordem de um exemplo seja uma mt probabilística que decide próxima ação jogando uma moeda tal máquina decide linguagens se então aceita com uma probabilidade de no mínimo se então rejeita com probabilidade de no mínimo uma importante observação sobre exemplo acima que se algoritmo for repetido algumas vezes probabilidade de sucesso pode ser essencialmente bpp pode ser considerada classe realmente computável por máquinas clássicas com uma equivalente bqp no estudo de máquinas quânticas outros modelos computacionais as máquina de turing não único modelo computacional vigente outros modelos conseguem aumentar desempenho de uma mt sem necessariamente alterar classe de complexidade dos problemas serem resolvidos um primeiro exemplo computação paralela uma mt capaz de simular uma máquina de processamento paralelo em tempo polinomial tanto em relação tempo quanto espaço computadores de dna se apresentam como uma proposta atraente para computação em paralelo combinando aleatoriamente diversas bases nitrogenadas 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 quantidade de problemas mas pelo fato deste permitir um número extremamente grande de moléculas processando paralelamente uso de dna pode ser útil para diversas aplicações computadores analógicos
processando paralelamente uso de dna pode ser útil para diversas aplicações computadores analógicos têm aparente vantagem de possuir uma quantidade ilimitada de estados possibilitando uma memória teoricamente infinita entretanto em sistemas reais ruído faz com que os computadores analógicos tenham uma quantidade finita de estados independentes caso contrário estarão sujeitos 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 computação distribuída uma outra alternativa para diminuição do tempo de processamento em relação execução centralizada de uma mt entretanto maior dilema para esse modelo computacional comunicação entre as unidades de processamento não trivial para muitos problemas separa los em porções menores para que possam ser resolvidos separadamente volte para página principal do livro clicando aqui