Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Faça o download
Acesso mais rápido do que o navegador!
 

Complexidade computacional

Índice Complexidade computacional

A teoria da complexidade computacional é um ramo da teoria da computação em ciência da computação teórica e matemática que se concentra em classificar problemas computacionais de acordo com sua dificuldade inerente, e relacionar essas classes entre si.

93 relações: AC, Algoritmo, Algoritmo de Shor, Algoritmo probabilístico, Análise de algoritmos, Análise numérica, Aritmética de Presburger, Autómato celular, Autômato linearmente limitado, Axiomas de Blum, Boris Trakhtenbrot, BPP, BQP, Cambridge University Press, Campo de número de peneira geral, Ciência da computação teórica, Clay Mathematics Institute, Cobertura de vértices (teoria dos grafos), Combinatória, Complexidade de comunicação, Computação paralela, Distribuição de probabilidade, DSPACE, Dtime, Equação diferencial, EXPSPACE, Exptime, Fatoração de inteiros, Função parcial, Grande-O, Investigação operacional, IP (complexidade), Jogo da vida, John Wiley & Sons, László Babai, Leonid Levin, Linguagem formal, Lista de adjacência, Lista de termos relacionados aos algoritmos e estruturas de dados, Logaritmo discreto, Logística, Manuel Blum, Matemática, Matemática pura, Matriz de adjacência, Máquina de Turing, Máquina de Turing alternada, Máquina de Turing multifita, Máquina de Turing não determinística, Máquina de Turing probabilística, ..., Máquina de Turing quântica, Modelo de árvore de decisão, Modelo de computação, Número inteiro, Número primo, NC, NEXPTIME, NP-completo, NP-difícil, NSPACE, NTIME, Porta lógica, Problema computacional, Problema da mochila, Problema de decisão, Problema de função, Problema de satisfatibilidade booliana, Problema do caixeiro-viajante, Problema do caminho hamiltoniano, Problemas do Prémio Millennium, Problemas em aberto da ciência da computação, Programação inteira, PSPACE, QMA, Quicksort, Raymond Smullyan, Regulação, Richard Karp, RP, RSA, Sistema de numeração binário, Sistema dinâmico, Springer Science+Business Media, Stephen Cook, Teorema da aceleração de Blum, Teorema de Savitch, Teoria da computação, Teoria da computabilidade, Teoria dos grafos, Tese de Church-Turing, Tese de Cobham, Teste de primalidade, ZPP. Expandir índice (43 mais) »

AC

;AC.

Novo!!: Complexidade computacional e AC · Veja mais »

Algoritmo

Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô. Algoritmo é uma sequência finita de instruções bem definidas e não ambíguas, cada uma das quais devendo ser executadas mecânica ou eletronicamente em um intervalo de tempo finito e com uma quantidade de esforço finita.

Novo!!: Complexidade computacional e Algoritmo · Veja mais »

Algoritmo de Shor

Na teoria da complexidade computacional e em Computação quântica, o algoritmo de Shor, batizado em homenagem ao matemático Peter Shor, é um algoritmo quântico para fatorar um número N não primo de L bits.

Novo!!: Complexidade computacional e Algoritmo de Shor · Veja mais »

Algoritmo probabilístico

Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.

Novo!!: Complexidade computacional e Algoritmo probabilístico · Veja mais »

Análise de algoritmos

Em ciência da computação, a análise de algoritmos tem como função determinar os recursos necessários para executar um dado algoritmo.

Novo!!: Complexidade computacional e Análise de algoritmos · Veja mais »

Análise numérica

''Clay tablet'' Babilônio YBC 7289(c. 1800–1600 BCE) http://www.math.ubc.ca/~cass/Euclid/ybc/ybc.html com anotações. (Imagem por Bill Casselman) A análise numérica é o estudo de algoritmos de aproximação para a solução de problemas matemáticos.

Novo!!: Complexidade computacional e Análise numérica · Veja mais »

Aritmética de Presburger

Aritmética de Presburger é a teoria de primeira-ordem dos números naturais com soma.

Novo!!: Complexidade computacional e Aritmética de Presburger · Veja mais »

Autómato celular

Os autómatos celulares elementares são os modelos de evolução temporal mais simples com capacidade para exibir comportamento complicado.

Novo!!: Complexidade computacional e Autómato celular · Veja mais »

Autômato linearmente limitado

Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto.

Novo!!: Complexidade computacional e Autômato linearmente limitado · Veja mais »

Axiomas de Blum

Na teoria da complexidade computacional, os axiomas de Blum ou axiomas de complexidade de Blum são axiomas que especificam propriedades desejáveis de medidas de complexidade no conjunto de funções computáveis.

Novo!!: Complexidade computacional e Axiomas de Blum · Veja mais »

Boris Trakhtenbrot

Boris (Boaz) Avraamovich Trakhtenbrot (Борис Авраамович Трахтенброт; Brichevo, –) ou Boaz (Boris) Trakhtenbrot (בועז טרכטנברוט) foi um matemático russo-israelense.

Novo!!: Complexidade computacional e Boris Trakhtenbrot · Veja mais »

BPP

Na teoria da complexidade computacional, BPP (inglês: Bounded-error Probabilistic Polinomial time, probabilístico de tempo polinomial comprometido à erros) é a classe de problemas de decisão solúveis por uma Máquina de Turing em tempo polinomial, com uma probabilidade de erro de no máximo 1/3 para todas as instâncias.

Novo!!: Complexidade computacional e BPP · Veja mais »

BQP

A relação suspeita entre '''BQP''' para outros espaços de problemasMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Em Teoria da Complexidade Computacional, BQP (do inglês bounded error quantum polynomial time) é a classe de problemas de decisão solúveis por um computador quântico em tempo polinomial, com uma probabilidade de erro de até 1/3 para todas as instâncias.

Novo!!: Complexidade computacional e BQP · Veja mais »

Cambridge University Press

Cambridge University Press é uma editora britânica, fundada em 1534 com o aval do rei Henrique VIII para a Universidade de Cambridge, sendo a editora mais antiga do mundo em operação contínua e a segunda maior editora universitária do mundo.

Novo!!: Complexidade computacional e Cambridge University Press · Veja mais »

Campo de número de peneira geral

Na teoria dos números, um ramo da matemática, o campo de número de peneira geral, (GNFS) é o mais eficiente algoritmo clássico, conhecido por fatorar inteiros maiores do que 100 dígitos.

Novo!!: Complexidade computacional e Campo de número de peneira geral · Veja mais »

Ciência da computação teórica

Ciência da computação teórica (TCS) é uma divisão ou subconjunto de ciências da computação e matemática que incide sobre os aspectos mais abstratos ou matemáticos da computação e inclui a teoria da computação.

Novo!!: Complexidade computacional e Ciência da computação teórica · Veja mais »

Clay Mathematics Institute

O Clay Mathematics Institute (CMI) é uma fundação privada sem fins lucrativos, baseada em Cambridge, Massachusetts.

Novo!!: Complexidade computacional e Clay Mathematics Institute · Veja mais »

Cobertura de vértices (teoria dos grafos)

Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto.

Novo!!: Complexidade computacional e Cobertura de vértices (teoria dos grafos) · Veja mais »

Combinatória

A combinatória é um ramo da matemática que estuda coleções finitas de elementos que satisfazem critérios específicos determinados, e se preocupa, em particular, com a "contagem" de elementos nessas coleções (combinatória enumerativa) e com a decisão de certo objeto "ótimo" existe (combinatória extremal) e com estruturas "algébricas" que esses objetos possam ter (combinatória algébrica).

Novo!!: Complexidade computacional e Combinatória · Veja mais »

Complexidade de comunicação

A noção de complexidade de comunicação foi introduzida por Yao em 1979, que investigou o seguinte problema envolvendo duas partes (Alice e Bob).

Novo!!: Complexidade computacional e Complexidade de comunicação · Veja mais »

Computação paralela

Computação paralela é uma forma de computação em que vários cálculos são realizados ao mesmo tempo, operando sob o princípio de que grandes problemas geralmente podem ser divididos em problemas menores, que então são resolvidos concorrentemente (em paralelo).

Novo!!: Complexidade computacional e Computação paralela · Veja mais »

Distribuição de probabilidade

Em teoria da probabilidade e em estatística, uma distribuição de probabilidade descreve o comportamento aleatório de um fenômeno dependente do acaso.

Novo!!: Complexidade computacional e Distribuição de probabilidade · Veja mais »

DSPACE

Em complexidade computacional, DSPACE ou simplesmente SPACE é um recurso computacional descrevendo a disponibilidade de memória para uma máquina de Turing.

Novo!!: Complexidade computacional e DSPACE · Veja mais »

Dtime

Na teoria da complexidade computacional, DTIME (ou TIME) é o recurso computacional de tempo de computação para uma máquina de Turing determinística.

Novo!!: Complexidade computacional e Dtime · Veja mais »

Equação diferencial

Soluções de uma equação diferencial (a negro) e as respectivas condições iniciais (a vermelho). Em matemática, uma equação diferencial é uma equação cuja incógnita é uma função que aparece na equação sob a forma das respectivas derivadas.

Novo!!: Complexidade computacional e Equação diferencial · Veja mais »

EXPSPACE

Em teoria da complexidade computacionais, EXPSPACE é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em espaço O(2p(n)) onde p(n) é uma função polinomial de n. (Alguns autores restringem p(n) para uma função linear, mas a maioria chama a classe resultante de ESPACE.) Se, por outro lado, nós usamos uma máquina não determinísitica, teremos a classe NEXPSPACE, que é igual a EXPSPACE pelo teorema de savitch.

Novo!!: Complexidade computacional e EXPSPACE · Veja mais »

Exptime

Na teoria da complexidade computacional, a classe de complexidade Exptime (às vezes chamado EXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing determinística em O(2p(n)) tempo, onde p (n) é uma função polinomial de n. Em termos de DTIME, Sabemos que e também, pelo time hierarchy theoremeo space hierarchy theorem, que assim pelo menos uma das três primeiras inclusões e pelo menos uma das três últimas inclusões deve ser adequada, mas não se sabe quais são.

Novo!!: Complexidade computacional e Exptime · Veja mais »

Fatoração de inteiros

Em teoria dos números, o problema da fatoração/ fatoração de inteiros consiste em encontrar um divisor não trivial de um número composto; Por exemplo dado o número 91, o objetivo é encontrar um número tal como 7 que o divida.

Novo!!: Complexidade computacional e Fatoração de inteiros · Veja mais »

Função parcial

Em matemática, uma função parcial é quase uma função, falhando na definição, porque para nem todos x do domínio existe algum f(x).

Novo!!: Complexidade computacional e Função parcial · Veja mais »

Grande-O

''g''(''x'') sempre que ''x'' ≥ ''x''0. Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.

Novo!!: Complexidade computacional e Grande-O · Veja mais »

Investigação operacional

A investigação operacional (IO), ou pesquisa operacional (PO), é um ramo interdisciplinar da matemática aplicada que faz uso de modelos matemáticos, estatísticos e de algoritmos na ajuda à tomada de decisão.

Novo!!: Complexidade computacional e Investigação operacional · Veja mais »

IP (complexidade)

Em Teoria da complexidade computacional, a classe IP (abreviação de Interactive Polynomial Time (Tempo Polinomial Interativo)) é a classe de problemas solúveis em tempo polinomial por um sistema de prova interativa.

Novo!!: Complexidade computacional e IP (complexidade) · Veja mais »

Jogo da vida

thumb Gosper'' criando ''planadores''. O jogo da vida é um autómato celular desenvolvido pelo matemático britânico John Horton Conway em 1970.

Novo!!: Complexidade computacional e Jogo da vida · Veja mais »

John Wiley & Sons

A John Wiley & Sons, Inc.

Novo!!: Complexidade computacional e John Wiley & Sons · Veja mais »

László Babai

László (Laci) Babai (Budapeste) é um matemático e cientista da computação húngaro.

Novo!!: Complexidade computacional e László Babai · Veja mais »

Leonid Levin

Leonid Anatolievich Levin, Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense.

Novo!!: Complexidade computacional e Leonid Levin · Veja mais »

Linguagem formal

Entende-se por linguagem formal estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.

Novo!!: Complexidade computacional e Linguagem formal · Veja mais »

Lista de adjacência

Em teoria dos grafos, uma lista de adjacência, estrutura de adjacência ou dicionário é a representação de todas arestas ou arcos de um grafo em uma lista.

Novo!!: Complexidade computacional e Lista de adjacência · Veja mais »

Lista de termos relacionados aos algoritmos e estruturas de dados

* Abstração.

Novo!!: Complexidade computacional e Lista de termos relacionados aos algoritmos e estruturas de dados · Veja mais »

Logaritmo discreto

Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais.

Novo!!: Complexidade computacional e Logaritmo discreto · Veja mais »

Logística

A logística é uma especialidade da administração responsável por prover recursos e informações para a execução de todas as atividades de uma organização.

Novo!!: Complexidade computacional e Logística · Veja mais »

Manuel Blum

Manuel Blum (Caracas, 26 de abril de 1938) é um informático venezuelano.

Novo!!: Complexidade computacional e Manuel Blum · Veja mais »

Matemática

grego, representado por Rafael em A Escola de Atenas. A matemática (dos termos gregos μάθημα, transliterado máthēma, 'ciência', conhecimento' ou 'aprendizagem'; e μαθηματικός, transliterado mathēmatikós, 'inclinado a aprender') é a ciência do raciocínio lógico e abstrato, que estuda quantidades, medidas, espaços, estruturas, variações e estatísticas.

Novo!!: Complexidade computacional e Matemática · Veja mais »

Matemática pura

A matemática pura é a matemática que não têm ou não necessita se preocupar com sua possível aplicação em uma determinada área do conhecimento, sendo considerada uma matemática "estética".

Novo!!: Complexidade computacional e Matemática pura · Veja mais »

Matriz de adjacência

Uma matriz de adjacência é uma das formas de se representar um grafo.

Novo!!: Complexidade computacional e Matriz de adjacência · Veja mais »

Máquina de Turing

Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).

Novo!!: Complexidade computacional e Máquina de Turing · Veja mais »

Máquina de Turing alternada

Em complexidade de computação teórica, uma máquina de Turing alternada (MTA) é uma máquina de Turing não-determinística (MTN) com a regra que aceita computações que generalizam regras usadas na definição da complexidade das classes NP e co-NP.

Novo!!: Complexidade computacional e Máquina de Turing alternada · Veja mais »

Máquina de Turing multifita

Uma máquina de Turing multifita é uma máquina de Turing comum com várias fitas.

Novo!!: Complexidade computacional e Máquina de Turing multifita · Veja mais »

Máquina de Turing não determinística

Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.

Novo!!: Complexidade computacional e Máquina de Turing não determinística · Veja mais »

Máquina de Turing probabilística

Em Teoria da Computabilidade, uma máquina de Turing probabilística é uma Máquina de Turing não determinística que escolhe aleatoriamente dentre as transições a cada ponto, de acordo com alguma distribuição de probabilidade.

Novo!!: Complexidade computacional e Máquina de Turing probabilística · Veja mais »

Máquina de Turing quântica

Uma máquina de Turing quântica, ou também computador quântico universal é uma máquina abstrata usada para modelar o efeito de um computador quântico.

Novo!!: Complexidade computacional e Máquina de Turing quântica · Veja mais »

Modelo de árvore de decisão

Em complexidade computacional e complexidade de comunicação o modelo de árvore de decisão é o modelo de computação ou comunicação no qual um algoritmo ou processo de comunicação é considerado basicamente uma árvore de decisão, ou seja, uma sequência de operações ramificadas baseadas em comparações de quantidades, sendo as comparações atribuidas uma unidade de custo computacional.

Novo!!: Complexidade computacional e Modelo de árvore de decisão · Veja mais »

Modelo de computação

Em teoria da computabilidade, um modelo de computação é a definição de um conjunto de operações que podem ser usadas numa computação e seus respectivos custos.

Novo!!: Complexidade computacional e Modelo de computação · Veja mais »

Número inteiro

Os números inteiros são constituídos dos números naturais e seus simétricos negativos, incluindo o zero.

Novo!!: Complexidade computacional e Número inteiro · Veja mais »

Número primo

Número primo é qualquer número p cujo conjunto dos divisores não inversíveis não é vazio, e todos os seus elementos são produtos de p por números inteiros inversíveis.

Novo!!: Complexidade computacional e Número primo · Veja mais »

NC

* Carolina do Norte, um Estado dos Estados Unidos.

Novo!!: Complexidade computacional e NC · Veja mais »

NEXPTIME

Em teoria da complexidade, NEXPSPACE (também chamada de NEXP) é o conjunto de todos os problemas de decisão solúveis por uma máquina de Turing não determinística em espaço O(2p(n)) para uma dada p(n) e espaço ilimitado.

Novo!!: Complexidade computacional e NEXPTIME · Veja mais »

NP-completo

Na teoria da complexidade computacional, a classe de complexidade é o subconjunto dos problemas NP de tal modo que todo problema em NP se pode reduzir, com uma redução de tempo polinomial, a um dos problemas NP-completo.

Novo!!: Complexidade computacional e NP-completo · Veja mais »

NP-difícil

NP-difícil (ou NP-hard, ou NP-complexo) na teoria da complexidade computacional, é uma classe de problemas que são, informalmente, "Pelo menos tão difíceis quanto os problemas mais difíceis em NP".

Novo!!: Complexidade computacional e NP-difícil · Veja mais »

NSPACE

Em teoria da complexidade computational, a classe de complexidade NSPACE(f(n)) é um conjunto de problemas de decisão que podem ser resolvido por uma máquina de Turing não-determinística usando espaço O(f(n)), e tempo ilimitado.

Novo!!: Complexidade computacional e NSPACE · Veja mais »

NTIME

Na teoria da complexidade computacional, a classe de complexidade NTIME(f(n)) é o conjunto dos problemas de decisão que podem ser solucionado por uma máquina de Turing não-determinística usando um tempo O(f(n)) e espaço ilimitado.

Novo!!: Complexidade computacional e NTIME · Veja mais »

Porta lógica

Porta NAND: esquema do circuito integrado e ''hardware'' Portas ou circuitos lógicos são dispositivos que operam um ou mais sinais lógicos de entrada para produzir uma e somente uma saída, dependente da função implementada no circuito.

Novo!!: Complexidade computacional e Porta lógica · Veja mais »

Problema computacional

Na ciência da teoria da computação, um problema computacional é um objeto matemático que representa um coleção de questões que computadores talvez queiram resolver.

Novo!!: Complexidade computacional e Problema computacional · Veja mais »

Problema da mochila

Problema da mochila: Como maximizar o valor com um peso máximo? O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória.

Novo!!: Complexidade computacional e Problema da mochila · Veja mais »

Problema de decisão

Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.

Novo!!: Complexidade computacional e Problema de decisão · Veja mais »

Problema de função

Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO.

Novo!!: Complexidade computacional e Problema de função · Veja mais »

Problema de satisfatibilidade booliana

Na teoria da complexidade computacional, o problema de satisfazibilidade booleana (SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.

Novo!!: Complexidade computacional e Problema de satisfatibilidade booliana · Veja mais »

Problema do caixeiro-viajante

O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem.

Novo!!: Complexidade computacional e Problema do caixeiro-viajante · Veja mais »

Problema do caminho hamiltoniano

No campo matemático da teoria dos grafos o Problema do caminho hamiltoniano e o Problema do ciclo hamiltoniano são problemas de determinar se um Caminho hamiltoniano ou um Ciclo hamiltoniano existe em um dado grafo (direcionado ou não direcionado).

Novo!!: Complexidade computacional e Problema do caminho hamiltoniano · Veja mais »

Problemas do Prémio Millennium

Os Problemas do Prémio Millennium (em inglês: Millennium Prize Problems) são sete problemas matemáticos.

Novo!!: Complexidade computacional e Problemas do Prémio Millennium · Veja mais »

Problemas em aberto da ciência da computação

Este artigo é uma lista de problemas em aberto na Ciência da computação.

Novo!!: Complexidade computacional e Problemas em aberto da ciência da computação · Veja mais »

Programação inteira

Um Problema de Programação Inteira é um modelo de programação linear no qual algumas ou todas as variáveis do problema pertencem ao conjunto dos números inteiros.

Novo!!: Complexidade computacional e Programação inteira · Veja mais »

PSPACE

Na teoria da complexidade computacional, PSPACE é o conjunto de todos os problemas de decisão que podem ser resolvidos por uma máquina de Turing usando uma quantidade polinomial de espaço.

Novo!!: Complexidade computacional e PSPACE · Veja mais »

QMA

QMA, na teoria da complexidade, que vem de Quantum Merlin Arthur, é uma classe de complexidade análoga à classe NP ou à classe de complexidade probabilística MA.

Novo!!: Complexidade computacional e QMA · Veja mais »

Quicksort

O algoritmo quicksort é um método de ordenação muito rápido e eficiente, inventado por C.A.R. Hoare em 1960, quando visitou a Universidade de Moscovo como estudante.

Novo!!: Complexidade computacional e Quicksort · Veja mais »

Raymond Smullyan

Raymond Merrill Smullyan (Far Rockaway, 25 de maio de 1919 – 6 de fevereiro de 2017) foi um matemático estadunidense, pianista, lógico, filósofo taoísta e mágico.

Novo!!: Complexidade computacional e Raymond Smullyan · Veja mais »

Regulação

O conceito de regulação (do latim, regula - vara reta, barra, régua; relacionado ao v.lat. regere - reger, ordenar, controlar, dirigir, guiar - ver reta) permeia, de forma geral, diversas áreas do conhecimento humano, como as tratadas pelas disciplinas técnico-científicas da administração, da automação, da cibernética, do direito, da economia, da educação, das engenharias, da teoria de controle, da teoria de sistemas e dos sistemas dinâmicos, entre outras.

Novo!!: Complexidade computacional e Regulação · Veja mais »

Richard Karp

Richard Manning Karp (Boston) é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.

Novo!!: Complexidade computacional e Richard Karp · Veja mais »

RP

* Relações públicas — conjunto de atividades informativas relacionadas com o intercâmbio de informações entre um indivíduo ou organização e o seu público.

Novo!!: Complexidade computacional e RP · Veja mais »

RSA

Adi Shamir, um dos criadores do RSA RSA (Rivest-Shamir-Adleman) é um dos primeiros sistemas de criptografia de chave pública e é amplamente utilizado para transmissão segura de dados.

Novo!!: Complexidade computacional e RSA · Veja mais »

Sistema de numeração binário

O sistema binário ou de base 2 é um sistema de numeração posicional em que todas as quantidades se representam com base em dois números, ou seja, zero e um (0 e 1).

Novo!!: Complexidade computacional e Sistema de numeração binário · Veja mais »

Sistema dinâmico

atrator de Lorenz é um exemplo de sistema dinâmico não-linear. O estudo deste sistema incentivou a criação da teoria do Caos. Na física matemática e na matemática, sistema dinâmico é um conceito no qual uma função descreve a relação no tempo de um ponto em um espaço geométrico.

Novo!!: Complexidade computacional e Sistema dinâmico · Veja mais »

Springer Science+Business Media

Springer Science+Business Media ou Springer-Verlag, ou ainda, simplesmente Springer é uma editora mundial baseada na Alemanha, a qual publica livros-texto, livros de referência acadêmica, e periódicos de artigos com revisão por pares (peer-review), com foco em ciência, tecnologia, matemática, e medicina.

Novo!!: Complexidade computacional e Springer Science+Business Media · Veja mais »

Stephen Cook

Stephen Arthur Cook, (Buffalo) é um cientista da computação e matemático estadunidense-canadense, que teve maior contribuição no campo da teoria da complexidade e complexidade de prova.

Novo!!: Complexidade computacional e Stephen Cook · Veja mais »

Teorema da aceleração de Blum

Na teoria da complexidade computacional, o teorema da aceleração de Blum ou teorema do aumento da velocidade de Blum (do inglês, Blum's speedup theorem), inicialmente definido por Manuel Blum em 1967, é um teorema fundamental sobre a complexidade de funções computáveis.

Novo!!: Complexidade computacional e Teorema da aceleração de Blum · Veja mais »

Teorema de Savitch

Na teoria da complexidade computacional, o teorema de Savitch, provado por Walter Savitch em 1970, afirma que para toda função ƒ(n) ≥ log(n), em outras palavras, se uma máquina de Turing não-determinística pode resolver um problema usando um espaço f(n) (polinomial), uma máquina de Turing determinística ordinária pode resolver o mesmo problema dentro dessa região delimitada.

Novo!!: Complexidade computacional e Teorema de Savitch · Veja mais »

Teoria da computação

A teoria da computação é um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um dado modelo de computação.

Novo!!: Complexidade computacional e Teoria da computação · Veja mais »

Teoria da computabilidade

A teoria da computabilidade, também chamada de teoria da recursão, é um ramo da lógica matemática que foi originado na década de 30 com o estudo das funções computáveis e dos graus de Turing.

Novo!!: Complexidade computacional e Teoria da computabilidade · Veja mais »

Teoria dos grafos

Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

Novo!!: Complexidade computacional e Teoria dos grafos · Veja mais »

Tese de Church-Turing

Na teoria da computabilidade, a Tese de Church-Turing ou Tese de Church, assim nomeada em referência a Alonzo Church e Alan Turing, é uma hipótese sobre a natureza de artefatos mecânicos de cálculo, como computadores, e sobre que tipo de algoritmos eles podem executar.

Novo!!: Complexidade computacional e Tese de Church-Turing · Veja mais »

Tese de Cobham

A Tese de Cobham, também conhecida como a tese de Cobham–Edmonds (assim denominada em referência a Alan Cobham e Jack Edmonds), assegura que problemas computacionais podem ser resolvidos de maneira viável em algum dispositivo de computação apenas se forem computáveis em tempo polinomial, ou seja, se pertencerem à classe de complexidade P.

Novo!!: Complexidade computacional e Tese de Cobham · Veja mais »

Teste de primalidade

Um teste de primalidade é um algoritmo para determinar se um dado número inteiro é primo.

Novo!!: Complexidade computacional e Teste de primalidade · Veja mais »

ZPP

Na Teoria da complexidade computacional, ZPP (inglês: Zero-error Probabilistic Polinomial time, Probalístico de tempo polinominal sem erros) é a classe complexa de problemas em que uma Máquina de Turing existe com estas propriedades.

Novo!!: Complexidade computacional e ZPP · Veja mais »

Redireciona aqui:

Computação factível, Teoria da complexidade, Teoria da complexidade computacional, Teoria de complexidade computacional.

CessanteEntrada
Ei! Agora estamos em Facebook! »