Acesso mais rápido do que o navegador!
9 relações: Circuito booliano, Linguagem esparsa, NC (complexidade), NP-completo, Problema de satisfatibilidade booliana, Satisfatibilidade de Horn, Sharp-SAT, Teorema da dicotomia de Schaefer, Teorema da Dicotomia de Schaefer.
Circuito booliano
Na teoria da complexidade computacional e complexidade de circuito, um circuito booliano é um modelo matemático para circuitos lógicos digitais.
Novo!!: P-completo e Circuito booliano · 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!!: P-completo e Linguagem esparsa · Veja mais »
NC (complexidade)
Na teoria da complexidade, a classe NC (para "Classe de Nick") é o conjunto de Problema de decisão decidíveis em tempo polilogarítmico em um computador paralelo com um número polinomial de processadores.
Novo!!: P-completo e NC (complexidade) · 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!!: P-completo e NP-completo · 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!!: P-completo e Problema de satisfatibilidade booliana · Veja mais »
Satisfatibilidade de Horn
Na lógica formal, Satisfatibilidade de Horn, ou HORNSAT, é o problema de decidir se um dado conjunto de cláusulas de Horn é satisfatível ou não.
Novo!!: P-completo e Satisfatibilidade de Horn · Veja mais »
Sharp-SAT
Na teoria da complexidade computacional, #SAT, ou Sharp-SAT é um problema de função relacionado com o problema da satisfabilidade booleana.
Novo!!: P-completo e Sharp-SAT · Veja mais »
Teorema da dicotomia de Schaefer
Em teoria da complexidade computacional, um ramo da ciência da computação, o Teorema da dicotomia de Schaefer declara condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano gera problemas de tempo polinomial ou problemas NP-completos quando as relações de S são usadas para restringir algumas das variáveis proposicionais.
Novo!!: P-completo e Teorema da dicotomia de Schaefer · Veja mais »
Teorema da Dicotomia de Schaefer
Em teoria da complexidade computacional, um ramo da Ciência da Computação, o teorema da dicotomia de Schaefer estabelece as condições necessárias e suficientes sob as quais um conjunto finito S de relações sobre o domínio Booleano produza problemas de tempo polinomial ou NP-completo quando as relações de S são usadas para restringir algumas das variáveis proposicionais.
Novo!!: P-completo e Teorema da Dicotomia de Schaefer · Veja mais »
