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!
E sem anúncios!

P/polinomial

Na Teoria da complexidade computacional, P/poly é a classe de complexidade das linguagens reconhecidas em tempo polinomial por uma máquina de Turing with a polynomial-bounded advice function.

12 relações: Classe de complexidade, Complexidade computacional, Criptografia, Exptime, Hierarquia polinomial, Leonard Adleman, Máquina de Turing, NEXPTIME, P (complexidade), Protocolo de Arthur-Merlin, PSPACE, Redução em tempo polinomial.

Classe de complexidade

Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.

Novo!!: P/polinomial e Classe de complexidade · Veja mais »

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.

Novo!!: P/polinomial e Complexidade computacional · Veja mais »

Criptografia

chave é utilizada para cifrar e decifrar. A máquina Enigma, utilizada na cifragem e decifragem de mensagens secretas. Criptografia (kryptós, "escondido", e gráphein, "escrita") é o estudo dos princípios e técnicas pelas quais a informação pode ser transformada da sua forma original para outra ilegível, de forma que possa ser conhecida apenas por seu destinatário (detentor da "chave secreta"), o que a torna difícil de ser lida por alguém não autorizado.

Novo!!: P/polinomial e Criptografia · 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!!: P/polinomial e Exptime · Veja mais »

Hierarquia polinomial

No ramo da Complexidade computacional a hierarquia polinomial é a hierarquia das Classes de complexidade que generaliza as classes P, NP e Co-NP para Máquinas oráculo.

Novo!!: P/polinomial e Hierarquia polinomial · Veja mais »

Leonard Adleman

Leonard Max Adleman (São Francisco) é um informático e biólogo molecular estadunidense.

Novo!!: P/polinomial e Leonard Adleman · 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!!: P/polinomial e Máquina de Turing · 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!!: P/polinomial e NEXPTIME · Veja mais »

P (complexidade)

Na teoria da complexidade computacional, P é o acrônimo em inglês para Tempo polinomial determinístico (Deterministic Polynomial time) que denota o conjunto de problemas que podem ser resolvidos em tempo polinomial por uma máquina de Turing determinística.

Novo!!: P/polinomial e P (complexidade) · Veja mais »

Protocolo de Arthur-Merlin

Na área da Complexidade computacional, um protocolo Arthur–Merlin é um sistema de prova interativa no qual os lançamentos de moeda do verificador são obrigados a serem públicos.

Novo!!: P/polinomial e Protocolo de Arthur-Merlin · 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!!: P/polinomial e PSPACE · Veja mais »

Redução em tempo polinomial

Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial.

Novo!!: P/polinomial e Redução em tempo polinomial · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »