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-Sharp

Na teoria da complexidade computacional, a classe de complexidade #P (Chamada de  "P-sharp" ou "P-hash") é o conjunto dos problemas de contagem associado aos problemas de decisão pertencentes ao conjunto NP.

19 relações: Caminho hamiltoniano, Complexidade computacional, Elsevier, Forma normal conjuntiva, Hierarquia polinomial, Leslie Valiant, Máquina de Turing não determinística, Máquina oráculo, NP (complexidade), P (complexidade), Permanente, PH, PP (complexidade), Problema da soma dos subconjuntos, Problema de decisão, Problema de função, Problema de satisfatibilidade booliana, Problema do caixeiro-viajante, Teoria dos grafos.

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!!: P-Sharp e Caminho hamiltoniano · 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-Sharp e Complexidade computacional · Veja mais »

Elsevier

Logotipo da Elsevier Elsevier é a maior editora de literatura médica e científica do mundo, fazendo parte do grupo Reed Elsevier.

Novo!!: P-Sharp e Elsevier · Veja mais »

Forma normal conjuntiva

Na lógica booleana, uma fórmula está na forma normal conjuntiva (FNC) se é uma conjunção de cláusulas, onde uma cláusula é uma disjunção de literais.

Novo!!: P-Sharp e Forma normal conjuntiva · 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-Sharp e Hierarquia polinomial · Veja mais »

Leslie Valiant

Leslie Gabriel Valiant (28 de março de 1949) é um informático britânico.

Novo!!: P-Sharp e Leslie Valiant · Veja mais »

Máquina de Turing não determinística

Máquina de Turing não-determinística em ciência da computação é uma máquina de Turing cujo mecanismo de controle atua como um autômato finito não-determinístico.

Novo!!: P-Sharp e Máquina de Turing não determinística · 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!!: P-Sharp e Máquina oráculo · Veja mais »

NP (complexidade)

Na teoria da complexidade computacional, NP é o acrônimo em inglês para Tempo polinomial não determinístico (Non-Deterministic Polynomial time) que denota o conjunto de problemas que são decidíveis em tempo polinomial por uma máquina de Turing não-determinística.

Novo!!: P-Sharp e NP (complexidade) · 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-Sharp e P (complexidade) · Veja mais »

Permanente

*Eternidade.

Novo!!: P-Sharp e Permanente · Veja mais »

PH

Em físico-química, o pH é uma escala para medida do, que indica a acidez ou basicidade de uma solução aquosa.

Novo!!: P-Sharp e PH · 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 instancias.

Novo!!: P-Sharp e PP (complexidade) · Veja mais »

Problema da soma dos subconjuntos

Em ciências da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia.

Novo!!: P-Sharp e Problema da soma dos subconjuntos · Veja mais »

Problema de decisão

Na teoria da computabilidade e na teoria da complexidade computacional um problema de decisão é uma questão sobre um sistema formal com uma resposta do tipo sim-ou-não.

Novo!!: P-Sharp e Problema de decisão · Veja mais »

Problema de função

Em teoria da complexidade computacional, um problema de função é um problema computacional onde uma única saída (de uma função total) é esperada pra cada entrada, mas a sáida é mais complexa do que um problema de decisão, isto é, não é apenas SIM ou NÃO.

Novo!!: P-Sharp e Problema de função · Veja mais »

Problema de satisfatibilidade booliana

Na teoria da complexidade computacional, o problema de satisfazibilidade booleana (SAT) foi o primeiro problema identificado como pertencente à classe de complexidade NP-completo.

Novo!!: P-Sharp e Problema de satisfatibilidade booliana · Veja mais »

Problema do caixeiro-viajante

O Problema do Caixeiro Viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem.

Novo!!: P-Sharp e Problema do caixeiro-viajante · Veja mais »

Teoria dos grafos

Grafo com 4 vértices e 6 arestas. É um grafo completo, conexo e planar. A teoria dos grafos é um ramo da matemática que estuda as relações entre os objetos de um determinado conjunto.

Novo!!: P-Sharp e Teoria dos grafos · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »