Acesso mais rápido do que o navegador!
24 relações: Albert Ronald Meyer, BPP, Circuitos e conjuntos de números naturais, Circuitos sobre conjuntos de números naturais, Complexidade de prova, Fórmula booliana completamente quantificada, Fórmula booliana totalmente quantificada, Hierarquia aritmética, Hierarquia exponencial, Larry Stockmeyer, Lógica default, Máquina oráculo, P versus NP, P/polinomial, PH (complexidade), Polinomial, PP (complexidade), Problema de isomorfismo de grafos, Problema do isomorfismo de subgrafos, Quantificador Delimitado, Redução (complexidade), Richard Karp, Teorema de Sipser–Lautemann, Teoria da complexidade estrutural.
Albert Ronald Meyer
Albert Ronald da Silva Meyer é um informático estadunidense.
Novo!!: Hierarquia polinomial e Albert Ronald Meyer · 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!!: Hierarquia polinomial e BPP · Veja mais »
Circuitos e conjuntos de números naturais
Circuitos sobre números naturais são um modelo matemático utilizado no estudo da teoria da complexidade computacional.
Novo!!: Hierarquia polinomial e Circuitos e conjuntos de números naturais · Veja mais »
Circuitos sobre conjuntos de números naturais
Circuitos sobre conjuntos de números naturais são um modelo matemático utilizado no estudo da teoria da complexidade computacional.
Novo!!: Hierarquia polinomial e Circuitos sobre conjuntos de números naturais · Veja mais »
Complexidade de prova
Em ciência da computação, complexidade de prova é a medida da eficiência dos métodos de prova de teoremas automatizados que é baseado no tamanho das provas que produzem.
Novo!!: Hierarquia polinomial e Complexidade de prova · Veja mais »
Fórmula booliana completamente quantificada
Em teoria da complexidade computacional, uma linguagem TQBF é uma linguagem formal consistindo de fórmulas booleanas completamente quantificadas.
Novo!!: Hierarquia polinomial e Fórmula booliana completamente quantificada · Veja mais »
Fórmula booliana totalmente quantificada
Na teoria da complexidade computacional, a linguagem TBQF é uma linguagem formal que consiste na quantificação verdadeira das fórmulas booleanas.
Novo!!: Hierarquia polinomial e Fórmula booliana totalmente quantificada · Veja mais »
Hierarquia aritmética
Em Lógica matemática, a hierarquia aritmética, ou hierarquia de Kleene-Mostowski classifica certos conjuntos baseada na complexidade das formulas que o definem.
Novo!!: Hierarquia polinomial e Hierarquia aritmética · Veja mais »
Hierarquia exponencial
Em teoria da complexidade computacional, a hierarquia exponencial é a hierarquia da complexidade das classes, que pertencem à classe de tempo exponencial, análogo a hierarquia polinomial.
Novo!!: Hierarquia polinomial e Hierarquia exponencial · Veja mais »
Larry Stockmeyer
Larry Joseph Stockmeyer (–) foi um cientista da computação americano.
Novo!!: Hierarquia polinomial e Larry Stockmeyer · Veja mais »
Lógica default
A lógica default é uma lógica não-monotônica proposta por Raymon Reiter para formalizar o raciocínio com suposições defaults.
Novo!!: Hierarquia polinomial e Lógica default · Veja mais »
Máquina oráculo
Em teoria da computação, uma máquina oráculo é uma máquina abstrata usada para estudar problemas de decisão.
Novo!!: Hierarquia polinomial e Máquina oráculo · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: Hierarquia polinomial e P versus NP · Veja mais »
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 com um polynomial-bounded advice function.
Novo!!: Hierarquia polinomial e P/polinomial · Veja mais »
PH (complexidade)
Na teoria da complexidade computacional, a classe de complexidade de PH é a união de todas as classes de complexidade na hierarquia polinomial: O PH foi primeiramente definido por Larry Stockmeyer.
Novo!!: Hierarquia polinomial e PH (complexidade) · Veja mais »
Polinomial
* Equação polinomial — equações com uma variável e na forma.
Novo!!: Hierarquia polinomial e Polinomial · Veja mais »
PP (complexidade)
Em Complexidade computacional, PP é a classe de problemas de decisão decidíveis por uma Máquina de Turing probabilística em tempo polinomial, com uma probabilidade de erro de menos do que 1/2 para todas as instâncias.
Novo!!: Hierarquia polinomial e PP (complexidade) · Veja mais »
Problema de isomorfismo de grafos
O problema de isomorfismo de grafos é um problema computacional para determinar se dois grafos finitos são isomórficos.
Novo!!: Hierarquia polinomial e Problema de isomorfismo de grafos · Veja mais »
Problema do isomorfismo de subgrafos
Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.
Novo!!: Hierarquia polinomial e Problema do isomorfismo de subgrafos · Veja mais »
Quantificador Delimitado
No estudo de teorias formais em lógica matemática, os quantificadores delimitados são muitas vezes adicionados para uma linguagem em adição aos quantificadores padrão "∀" e "∃".
Novo!!: Hierarquia polinomial e Quantificador Delimitado · Veja mais »
Redução (complexidade)
Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.
Novo!!: Hierarquia polinomial e Redução (complexidade) · 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!!: Hierarquia polinomial e Richard Karp · Veja mais »
Teorema de Sipser–Lautemann
Em teoria da complexidade computacional, o teorema Sipser-Lautemann ou teorema Sipser-Gács-Lautemann estabelece que Bounded-error probabilistic polinomial time (BPP), está contida na hierarquia de tempo polinomial, e, mais especificamente, em Σ2 ∩ Π2.
Novo!!: Hierarquia polinomial e Teorema de Sipser–Lautemann · Veja mais »
Teoria da complexidade estrutural
Em Complexidade computacional da ciência da computação, a teoria da complexidade estrutural ou simplesmente complexidade estrutural é o estudo de classes de complexidade, ao invés da complexidade computacional de problemas individuais e algoritmos.
Novo!!: Hierarquia polinomial e Teoria da complexidade estrutural · Veja mais »
