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.

6 relações: BPP, Complexidade computacional, Hierarquia polinomial, Michael Sipser, Ou exclusivo, P (complexidade).

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!!: Teorema de Sipser–Lautemann e BPP · 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!!: Teorema de Sipser–Lautemann e Complexidade computacional · 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!!: Teorema de Sipser–Lautemann e Hierarquia polinomial · Veja mais »

Michael Sipser

Michael Fredric Sipser é um professor de Matemática Aplicada no grupo de teoria da computação do Massachusetts Institute of Technology.

Novo!!: Teorema de Sipser–Lautemann e Michael Sipser · Veja mais »

Ou exclusivo

Ou exclusivo ou disjunção exclusiva é uma operação lógica entre dois operandos que resulta em um valor lógico verdadeiro se e somente se os dois operandos forem diferentes, ou seja, se um for verdadeiro e o outro for falso.

Novo!!: Teorema de Sipser–Lautemann e Ou exclusivo · 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!!: Teorema de Sipser–Lautemann e P (complexidade) · Veja mais »

Unionpédia é um mapa conceitual ou rede semântica organizado sob a forma de enciclopédia - dicionário. Dá uma breve definição de cada conceito e toda a sua relacionados.

É um mapa mental on-line gigante que serve de base para os diagramas de conceito. É livre para usar e cada artigo ou documento pode ser baixado. É uma ferramenta, de recursos ou de referência para estudo, pesquisa, educação, ou formação, eles podem usar professores, educadores, alunos e estudantes; ou para o mundo acadêmico: para a escola, primário, secundário, médio, faculdade, grau técnico, universidade, graduação, mestrado ou doutorado; para papéis, relatórios, documentos, projetos, idéias, documentação, resumos, pesquisas ou teses. Aqui aparece a definição, explicação, descrição, ou o significado de cada significativa no qual você precisa de informações e uma lista de seus conceitos associados como um glossário. Disponível em português, inglês, espanhol, japonês, chinês, francês, alemão, italiano, polonês, holandês, russo, árabe, hindi, sueco, ucraniano, húngaro, catalão, checo, hebraico, dinamarquês, finlandês, indonésio, norueguês, romeno, turco, vietnamita, coreano, tailandês, grego, búlgaro, croata, eslovaco, lituano, filipino, letão, estoniano e esloveno. Mais idiomas em breve.

Todas as informações foi feita a partir de Wikipédia, é disponibilizado nos termos da licença Creative Commons - Atribuição - Compartilha Igual 3.0 Não Adaptada (CC BY-SA 3.0).

A Unionpédia não é endossada ou afiliada à Wikimedia Foundation.

Google Play, Android e o logotipo do Google Play são marcas registradas da Google Inc.

Política de Privacidade