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!
 

P-Sharp completude

Índice P-Sharp completude

#P-completo, pronunciado "P-sharp completo" ou "P-número completo" é uma classe de complexidade na teoria da complexidade computacional.

21 relações: Acoplamento (teoria dos grafos), Algoritmo probabilístico, Cardinalidade, Classe de complexidade, Coloração de grafos, Complexidade computacional, Conjunto parcialmente ordenado, DNF, Grafos acíclicos dirigidos, Grande-O, Leslie Valiant, Lista de termos técnicos relacionados à teoria dos grafos, Máquina de Turing não determinística, Ordenação topológica, P (complexidade), P versus NP, Redução (complexidade), Redução em tempo polinomial, Sharp-SAT, Teoria dos grafos, Vértice (teoria dos grafos).

Acoplamento (teoria dos grafos)

Na teoria dos grafos um acoplamento, emparelhamento ou conjunto de arestas independentes em um grafo G é um conjunto de '''arestas''' sem vértices em comum.

Novo!!: P-Sharp completude e Acoplamento (teoria dos grafos) · Veja mais »

Algoritmo probabilístico

Um algoritmo probabilístico é um algoritmo que utiliza a probabilidade como parte de sua lógica.

Novo!!: P-Sharp completude e Algoritmo probabilístico · Veja mais »

Cardinalidade

Na matemática, a cardinalidade de um conjunto é uma medida do "número de elementos do conjunto".

Novo!!: P-Sharp completude e Cardinalidade · Veja mais »

Classe de complexidade

Na Teoria da Complexidade Computacional, uma Classe de Complexidade é um conjunto de problemas.

Novo!!: P-Sharp completude e Classe de complexidade · Veja mais »

Coloração de grafos

Em teoria dos grafos, coloração de grafos é um caso especial de rotulagem de grafos; é uma atribuição de rótulos tradicionalmente chamados "cores" a elementos de um grafo sujeita a certas restrições.

Novo!!: P-Sharp completude e Coloração de grafos · 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 completude e Complexidade computacional · Veja mais »

Conjunto parcialmente ordenado

Na matemática, especialmente na Teoria da ordem, um conjunto parcialmente ordenado (poset, em inglês partially ordered set) é um conjunto equipado com uma relação binária de ordem parcial.

Novo!!: P-Sharp completude e Conjunto parcialmente ordenado · Veja mais »

DNF

Sem descrição

Novo!!: P-Sharp completude e DNF · Veja mais »

Grafos acíclicos dirigidos

Em matemática, um grafo acíclico dirigido, (em inglês: directed acyclic graph, ou simplesmente um dag ou DAG), é um grafo dirigido sem ciclo; isto é, para qualquer vértice v, não há nenhuma ligação dirigida começando e acabando em v. Estes grafos aparecem em modelos onde não faz sentido que um vértice tenha uma ligação com si próprio.

Novo!!: P-Sharp completude e Grafos acíclicos dirigidos · Veja mais »

Grande-O

''g''(''x'') sempre que ''x'' ≥ ''x''0. Na matemática, a notação O-grande descreve o comportamento limitante de uma função quando o argumento tende a um valor específico ou para o infinito, normalmente, em termos de funções mais simples.

Novo!!: P-Sharp completude e Grande-O · Veja mais »

Leslie Valiant

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

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

Lista de termos técnicos relacionados à teoria dos grafos

Este glossário contém alguns termos técnicos relacionados com teoria dos grafos.

Novo!!: P-Sharp completude e Lista de termos técnicos relacionados à teoria dos grafos · 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 completude e Máquina de Turing não determinística · Veja mais »

Ordenação topológica

Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída.

Novo!!: P-Sharp completude e Ordenação topológica · 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 completude e P (complexidade) · Veja mais »

P versus NP

O problema "P versus NP" é o principal problema aberto da Ciência da Computação.

Novo!!: P-Sharp completude e P versus NP · Veja mais »

Redução (complexidade)

Em teoria da computação e complexidade, uma redução é uma transformação de um problema em outro.

Novo!!: P-Sharp completude e Redução (complexidade) · Veja mais »

Redução em tempo polinomial

Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial.

Novo!!: P-Sharp completude e Redução em tempo polinomial · 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-Sharp completude e Sharp-SAT · Veja mais »

Teoria dos grafos

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

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

Vértice (teoria dos grafos)

Em teoria dos grafos, um vértice (plural vértices) ou nó é a unidade fundamental da qual os grafos são formados: um grafo não dirigido consiste de um conjunto de vértices e um conjunto de arestas (pares de vértices não ordenados), enquanto um digrafo é constituído por um conjunto de vértices e um conjunto de arcos (pares ordenados de vértices).

Novo!!: P-Sharp completude e Vértice (teoria dos grafos) · Veja mais »

CessanteEntrada
Ei! Agora estamos em Facebook! »