Acesso mais rápido do que o navegador!
60 relações: Automorfismo de grafos, BPP, Caminho hamiltoniano, Certificado de primalidade, Circuitos e conjuntos de números naturais, Circuitos sobre conjuntos de números naturais, Classe de complexidade, Co-NP, Complemento (complexidade), Completo (complexidade), Complexidade caso médio, Complexidade computacional, Complexidade de caso médio, Complexidade de prova, Computers and Intractability, Conjectura de jogos únicos, Corte Máximo, Empacotamento de conjuntos, EXPSPACE, Exptime, Fatoração de inteiros, Grafo implícito, Hierarquia polinomial, Isomorfismo de grafos, Linguagem esparsa, Lista de algoritmos, Máquina de Turing alternante, Medida de recurso delimitado, NEXPTIME, NP, NP-completo, NP-difícil, NP-fácil, NTIME, P (complexidade), P-completo, PH (complexidade), PLS (complexidade), PostBQP, Problema de isomorfismo de grafos, Problema de satisfatibilidade booliana, Prova de conhecimento, Prova de conhecimento zero, PSPACE, PSPACE-completude, QMA, Redução (complexidade), RP (complexidade computacional), Sistema de prova interativa, SNP (complexidade), ..., Teorema de Cook-Levin, Teorema de Fagin, Teorema de hierarquia de tempo, Teorema de Immerman–Szelepcsényi, Teorema de Valiant-Vazirani, Teorema PCP, Teoria da computação, TFNP, UP (complexidade), 2-EXPTIME. Expandir índice (10 mais) »
Automorfismo de grafos
No campo da matemática da teoria dos grafos, um automorfismo de um grafo é uma forma de simetria em que o grafo é mapeado em si, preservando a conectividade vértice-aresta.
Novo!!: NP (complexidade) e Automorfismo de grafos · 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!!: NP (complexidade) e BPP · Veja mais »
Caminho hamiltoniano
Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não repetindo nenhum, ou seja, passar por todos uma e uma só vez por cada.
Novo!!: NP (complexidade) e Caminho hamiltoniano · Veja mais »
Certificado de primalidade
Na Ciência da Computação e na Matemática, o certificado de primalidade ou a prova de primalidade é uma prova sucinta e formal de que um número é primo.
Novo!!: NP (complexidade) e Certificado de primalidade · 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!!: NP (complexidade) 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!!: NP (complexidade) e Circuitos sobre conjuntos de números naturais · Veja mais »
Classe de complexidade
Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.
Novo!!: NP (complexidade) e Classe de complexidade · Veja mais »
Co-NP
Na Teoria da complexidade, co-NP é uma Classe de complexidade.
Novo!!: NP (complexidade) e Co-NP · Veja mais »
Complemento (complexidade)
Na teoria da complexidade computacional, o complemento de um problema de decisão é o problema de decisão resultante do reverso das respostas sim e não.Igualmente, se definimos problemas de decisão como um conjunto de cadeias finitas, então o complemento deste conjunto sobre um domínio fixo é seu problema-complemento.
Novo!!: NP (complexidade) e Complemento (complexidade) · Veja mais »
Completo (complexidade)
Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade.
Novo!!: NP (complexidade) e Completo (complexidade) · Veja mais »
Complexidade caso médio
Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis.
Novo!!: NP (complexidade) e Complexidade caso médio · 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!!: NP (complexidade) e Complexidade computacional · Veja mais »
Complexidade de caso médio
Em teoria de complexidade computacional, a complexidade de caso médio de um algoritmo é a quantidade de algum recurso computacional (tipicamente tempo) utilizado pelo algoritmo, numa média sobre todas as entradas possíveis.
Novo!!: NP (complexidade) e Complexidade de caso médio · 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!!: NP (complexidade) e Complexidade de prova · Veja mais »
Computers and Intractability
Computers and Intractability: A Guide to the Theory of NP-Completeness (Computadores e Intratabilidade: Um guia para a Teoria da NP-completude, tradução livre, não há edição em português) é um livro de Michael Garey e David S. Johnson de grande influência em ciência da computação, mais especificamente em teoria da complexidade computacional.
Novo!!: NP (complexidade) e Computers and Intractability · Veja mais »
Conjectura de jogos únicos
Na teoria da complexidade computacional, a Conjectura de Jogos Únicos é uma conjectura feita por Subhash Khot em 2002.
Novo!!: NP (complexidade) e Conjectura de jogos únicos · Veja mais »
Corte Máximo
Para um grafo, um corte máximo é um corte cujo tamanho é de pelo menos o tamanho de qualquer outro corte.
Novo!!: NP (complexidade) e Corte Máximo · Veja mais »
Empacotamento de conjuntos
Empacotamento de conjuntos é um clássico NP-completo problema em complexidade computacional teoria e análise combinatória, e foi um dos Karp 21 problemas NP-completos.
Novo!!: NP (complexidade) e Empacotamento de conjuntos · 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!!: NP (complexidade) 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!!: NP (complexidade) e Exptime · Veja mais »
Fatoração de inteiros
Na teoria dos números, a fatoração de inteiros é a decomposição de um número composto em um produto de números inteiros menores.
Novo!!: NP (complexidade) e Fatoração de inteiros · Veja mais »
Grafo implícito
No estudo de algoritmos de grafos, uma representação por grafo implícito (ou mais simplesmente grafo Implícito) é um grafo em que os vertices ou arestas não são representados como objetos explícitos na memória de um computador, mas sim, determinados algoritmicamente a partir de alguma entrada.
Novo!!: NP (complexidade) e Grafo implícito · 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!!: NP (complexidade) e Hierarquia polinomial · Veja mais »
Isomorfismo de grafos
Em teoria dos grafos, um isomorfismo dos grafos G e H é uma bijeção entre os conjuntos de vértices de G e H de tal forma que quaisquer dois vértices u e v de G são adjacentes em G se e somente se ƒ(u) e ƒ(v) são adjacentes em H. Este tipo de bijeção é comumente chamado de "bijeção com preservação de arestas", de acordo com a noção geral de isomorfismo sendo uma bijeção de preservação-de-estrutura.
Novo!!: NP (complexidade) e Isomorfismo de grafos · Veja mais »
Linguagem esparsa
Em teoria da complexidade computacional, uma linguagem esparsa é uma linguagem formal (um conjunto de strings) cujo número de strings de comprimento n na língua é limitada por uma função de polinômio n. São utilizadas principalmente no estudo da relação entre a classe de complexidade NP com outras classes.
Novo!!: NP (complexidade) e Linguagem esparsa · Veja mais »
Lista de algoritmos
Abaixo segue a lista de algoritmos.
Novo!!: NP (complexidade) e Lista de algoritmos · Veja mais »
Máquina de Turing alternante
Em teoria da complexidade, uma máquina de Turing alternante (MTA) é uma máquina de Turing não determinística (MTN) com uma regra para aceitar computações que generalizam as regras usadas nas definições de Classe de complexidade NP (complexidade) e Co-NP.
Novo!!: NP (complexidade) e Máquina de Turing alternante · Veja mais »
Medida de recurso delimitado
A medida de recurso delimitado de Lutz é uma generalização da Medida de Lebesgue para classes de complexidade.
Novo!!: NP (complexidade) e Medida de recurso delimitado · 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!!: NP (complexidade) e NEXPTIME · Veja mais »
NP
* Notícias Populares - antigo jornal paulistano.
Novo!!: NP (complexidade) e NP · 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!!: NP (complexidade) 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!!: NP (complexidade) e NP-difícil · Veja mais »
NP-fácil
Em complexidade computacional, a classe de complexidade NP-fácil é a classe de problemas que são solúveis em tempo polinomial por uma máquina de Turing determinística com um oráculo para algum problema de decisão em NP.
Novo!!: NP (complexidade) e NP-fácil · 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!!: NP (complexidade) e NTIME · 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!!: NP (complexidade) e P (complexidade) · Veja mais »
P-completo
Na teoria da complexidade computacional, a noção de problema de decisão P-completo é útil na análise de questões como.
Novo!!: NP (complexidade) e P-completo · 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!!: NP (complexidade) e PH (complexidade) · Veja mais »
PLS (complexidade)
Na teoria da complexidade computacional, a Pesquisa Local Polinomial (PLS) é uma classe de complexidade que modela a dificuldade de encontrar uma solução ótima localmente para um problema de otimização.
Novo!!: NP (complexidade) e PLS (complexidade) · Veja mais »
PostBQP
Em teoria da complexidade computacional, PostBQP é uma classe de complexidade que consiste de todos os problemas computacionais solúveis em tempo polinomial em uma Máquina de Turing quântica com pós-seleção e erro limitado (no sentido de que o algoritmo é correto ao menos em 2/3 das vezes para todas as entradas).
Novo!!: NP (complexidade) e PostBQP · 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!!: NP (complexidade) e Problema de isomorfismo de grafos · Veja mais »
Problema de satisfatibilidade booliana
Na teoria da complexidade computacional, o problema de satisfatibilidade booliana (do inglês boolean satisfiability problem, muitas vezes abreviado como SATISFIABILITY ou SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.
Novo!!: NP (complexidade) e Problema de satisfatibilidade booliana · Veja mais »
Prova de conhecimento
Na criptografia, uma prova de conhecimento é uma prova interativa na qual o provador consegue "convencer" um verificador de que o provador sabe algo.
Novo!!: NP (complexidade) e Prova de conhecimento · Veja mais »
Prova de conhecimento zero
Em criptografia, uma prova de conhecimento zero ou protocolo de conhecimento zero é um método pelo qual uma parte (o provador) pode provar à outra parte (o verificador) que uma determinada afirmação é verdadeira, sem transmitir qualquer informação além do fato de que a afirmação é realmente verdadeira.
Novo!!: NP (complexidade) e Prova de conhecimento zero · 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!!: NP (complexidade) e PSPACE · Veja mais »
PSPACE-completude
Em teoria da complexidade computacional, um problema de decisão é PSPACE-completo se pertence à classe de complexidade PSPACE e todos os problemas em PSPACE podem ser reduzidos a ele em tempo polinomial.
Novo!!: NP (complexidade) e PSPACE-completude · 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!!: NP (complexidade) e QMA · Veja mais »
Redução (complexidade)
Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.
Novo!!: NP (complexidade) e Redução (complexidade) · Veja mais »
RP (complexidade computacional)
Tempo Polinomial Aleatorizado (em inglês, Randomized polynomial time: RP) é uma classe de complexidade da complexidade computacional, problemas para nos quais a Máquina de Turing probabilística possui as seguintes propriedades.
Novo!!: NP (complexidade) e RP (complexidade computacional) · Veja mais »
Sistema de prova interativa
Na teoria da complexidade, um sistema de prova interativa é uma máquina abstrata que formula computação como a troca de mensagens entre duas partes.
Novo!!: NP (complexidade) e Sistema de prova interativa · Veja mais »
SNP (complexidade)
Na teoria da complexidade computacional, SNP (de Strict NP) é uma classe de complexidade que contém um subconjunto limitado de NP baseado em sua caracterização lógica em termos de propriedades da Teoria dos grafos.
Novo!!: NP (complexidade) e SNP (complexidade) · Veja mais »
Teorema de Cook-Levin
Na teoria da complexidade computacional, o teorema de Cook-Levin, também conhecido como teorema de Cook, afirma que o problema de satisfatibilidade booleana é NP-completo.
Novo!!: NP (complexidade) e Teorema de Cook-Levin · Veja mais »
Teorema de Fagin
Teorema de Fagin é um resultado da teoria da complexidade descritiva, que afirma que o conjunto de todas as propriedades que podem ser expressas na lógica de segunda ordem existencial, é precisamente a classe de complexidade NP.
Novo!!: NP (complexidade) e Teorema de Fagin · Veja mais »
Teorema de hierarquia de tempo
Na teoria da complexidade computacional, os teoremas de hierarquia de tempo são importantes declarações sobre a limitação de tempo de computação de máquinas de Turing.
Novo!!: NP (complexidade) e Teorema de hierarquia de tempo · Veja mais »
Teorema de Immerman–Szelepcsényi
Na teoria de complexidade computacional, o teorema de Immerman–Szelepcsényi foi provado de forma independente por Neil Immerman e Róbert Szelepcsényi no ano de 1987.
Novo!!: NP (complexidade) e Teorema de Immerman–Szelepcsényi · Veja mais »
Teorema de Valiant-Vazirani
O Teorema de Valiant–Vazirani é um teorema na teoria da complexidade computacional.
Novo!!: NP (complexidade) e Teorema de Valiant-Vazirani · Veja mais »
Teorema PCP
Na teoria da complexidade computacional, o Teorema PCP afirma que todo problema de decisão na classe de complexidade NP tem provas checáveis probabilisticamente (prova que pode ser checada por um algoritmo aleatorizado) de complexidade de busca constante e complexidade logarítmica de aleatoriedade (usa um número logarítmico de bits aleatórios).
Novo!!: NP (complexidade) e Teorema PCP · 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!!: NP (complexidade) e Teoria da computação · Veja mais »
TFNP
Na teoria da complexidade computacional, a complexidade de classe TFNP é uma subclasse da classe FNP onde existência da solução é garantida.
Novo!!: NP (complexidade) e TFNP · Veja mais »
UP (complexidade)
Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada.
Novo!!: NP (complexidade) e UP (complexidade) · Veja mais »
2-EXPTIME
Na teoria da Complexidade Computacional, a classe de complexidade 2-EXPTIME (também chamada 2-EXP) é o conjunto de todos os problemas de decisão solucionáveis por uma Máquina de Turing Determinística em tempo O(22p(n)), onde p(n) é uma função polinomial de n. Em termos de DTIME, Nós sabemos que: 2-EXPTIME também pode ser reformulado como a classe do espaço AEXPSPACE, os problemas que podem ser solucionados por uma Máquina de Turing Alternada em espaço exponencial.
Novo!!: NP (complexidade) e 2-EXPTIME · Veja mais »
