Acesso mais rápido do que o navegador!
41 relações: Algoritmo, Aproximação, Aritmética de Presburger, Caminho hamiltoniano, Clay Mathematics Institute, Cobertura de vértices (teoria dos grafos), Complexidade computacional, Conjunto independente, David Stifler Johnson, Heurística, Isomorfismo, John Hopcroft, Leonid Levin, Máquina de Turing, Máquina de Turing não determinística, NP (complexidade), NP-difícil, O jogo do 15, P (complexidade), P versus NP, P-completo, Probabilidade, Problema da mochila, Problema da soma dos subconjuntos, Problema de decisão, Problema de roteamento de veículos, Problema de satisfatibilidade booliana, Problema do caixeiro-viajante, Problema do clique, Problema do isomorfismo de subgrafos, Redução em tempo polinomial, Richard Karp, Se e somente se, Stephen Cook, Subconjunto, Tempo de execução, Teorema de Cook-Levin, Teoria dos grafos, Tetris, Torre de Hanói, Vértice.
Algoritmo
Uma animação do algoritmo de ordenação quicksort de uma matriz de valores ao acaso. As barras vermelhas marcam o elemento pivô. No início da animação, estando o elemento para o lado direito, é escolhido como o pivô Em matemática e ciência da computação, um algoritmo é uma sequência finita de ações executáveis que visam obter uma solução para um determinado tipo de problema.
Novo!!: NP-completo e Algoritmo · Veja mais »
Aproximação
Duas aproximações de um parabolóide. Uma aproximação (símbolo: ≈, às vezes é utilizado um til ˜) é uma representação inexata de alguma coisa, que apesar de tudo ainda é suficientemente próxima para ser usada.
Novo!!: NP-completo e Aproximação · Veja mais »
Aritmética de Presburger
A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma.
Novo!!: NP-completo e Aritmética de Presburger · 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-completo e Caminho hamiltoniano · Veja mais »
Clay Mathematics Institute
O Clay Mathematics Institute (CMI) é uma fundação privada sem fins lucrativos, baseada em Cambridge, Massachusetts.
Novo!!: NP-completo e Clay Mathematics Institute · Veja mais »
Cobertura de vértices (teoria dos grafos)
Na matemática, na disciplina de teoria dos grafos, uma cobertura de vertices de um grafo é um conjunto de vértices tal que cada aresta do grafo é incidente a pelo menos um vértice do conjunto.
Novo!!: NP-completo e Cobertura de vértices (teoria dos 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!!: NP-completo e Complexidade computacional · Veja mais »
Conjunto independente
Na teoria dos grafos, um conjunto independente de um grafo G é um conjunto S de vértices de G tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se a e b são vértices quaisquer de um conjunto independente, não há aresta entre a e b. Todo grafo tem ao menos um conjunto independente: o conjunto vazio.
Novo!!: NP-completo e Conjunto independente · Veja mais »
David Stifler Johnson
David Stifler Johnson (9 de dezembro de 1945 – 8 de março de 2016) foi um cientista da computação estadunidense especializado em algoritmos e otimização.
Novo!!: NP-completo e David Stifler Johnson · Veja mais »
Heurística
Heurística é um procedimento mental simples que ajuda a encontrar respostas adequadas, embora várias vezes imperfeitas, para perguntas difíceis.
Novo!!: NP-completo e Heurística · Veja mais »
Isomorfismo
Na álgebra abstrata, um isomorfismo é um homomorfismo bijetivo.
Novo!!: NP-completo e Isomorfismo · Veja mais »
John Hopcroft
John Edward Hopcroft (Seattle) é um professor de ciência da computação estadunidense.
Novo!!: NP-completo e John Hopcroft · Veja mais »
Leonid Levin
Leonid Anatolievich Levin, Леонид Анатольевич Левин; (Dnipropetrovsk, 2 de novembro de 1948) é um informático soviético-estadunidense.
Novo!!: NP-completo e Leonid Levin · Veja mais »
Máquina de Turing
Representação artística de uma máquina de Turing A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais (o artigo de referência foi publicado em 1936).
Novo!!: NP-completo e Máquina de Turing · 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!!: NP-completo e Máquina de Turing não determinística · 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!!: NP-completo e NP (complexidade) · 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-completo e NP-difícil · Veja mais »
O jogo do 15
O jogo do 15, também chamado de "O Quebra-cabeças das Quinze Pastilhas", é um famoso quebra-cabeças de 15 peças O Jogo do 15 e suas trilhões de possibilidades.
Novo!!: NP-completo e O jogo do 15 · 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-completo e P (complexidade) · Veja mais »
P versus NP
O problema "P versus NP" é o principal problema aberto da Ciência da Computação.
Novo!!: NP-completo e P versus NP · 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-completo e P-completo · Veja mais »
Probabilidade
A palavra probabilidade deriva do Latim probare (provar ou testar).
Novo!!: NP-completo e Probabilidade · Veja mais »
Problema da mochila
Problema da mochila: Como maximizar o valor com um peso máximo? O problema da mochila (em inglês, Knapsack problem) é um problema de optimização combinatória.
Novo!!: NP-completo e Problema da mochila · Veja mais »
Problema da soma dos subconjuntos
Em ciência da computação, o problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia.
Novo!!: NP-completo 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!!: NP-completo e Problema de decisão · Veja mais »
Problema de roteamento de veículos
Esquema gráfico de solução de um Problema de Roteamento de Veículos (PRV), com um só depósito. O problema de roteamento de veículos (PRV) é um dos mais estudados problemas na área da otimização combinatória.
Novo!!: NP-completo e Problema de roteamento de veículos · 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-completo 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!!: NP-completo e Problema do caixeiro-viajante · Veja mais »
Problema do clique
Em ciência da computação, o problema do clique refere-se a qualquer problema que possui como objetivo encontrar subgrafos completos ("cliques") em um grafo.
Novo!!: NP-completo e Problema do clique · Veja mais »
Problema do isomorfismo de subgrafos
Em teoria da complexidade, o problema do isomorfismo de subgrafos é um problema de decisão que se sabe ser NP-completo.
Novo!!: NP-completo e Problema do isomorfismo de subgrafos · 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!!: NP-completo e Redução em tempo polinomial · Veja mais »
Richard Karp
Richard Manning Karp (Boston) é um cientista da computação e teórico computacional da Universidade da California, Berkeley, reconhecido pela sua pesquisa sobre teoria dos algoritmos, pelo qual recebeu um Prêmio Turing em 1985, Medalha Benjamin Franklin em Computação e Ciência Cognitiva em 2004, e o Prêmio Kyoto em 2008.
Novo!!: NP-completo e Richard Karp · Veja mais »
Se e somente se
Se e somente se, ou se e só se (abreviado, sse), em matemática, lógica e filosofia, é uma forma de expressão para um teorema: Se A então B, e se B então A; ou A se e somente se B. O correspondente símbolo lógico é \Leftrightarrow.
Novo!!: NP-completo e Se e somente se · Veja mais »
Stephen Cook
Stephen Arthur Cook, (Buffalo) é um cientista da computação e matemático estadunidense-canadense, que teve maior contribuição no campo da teoria da complexidade e complexidade de prova.
Novo!!: NP-completo e Stephen Cook · Veja mais »
Subconjunto
Diagrama de Euler ilustrando o fato de que A é subconjunto de B ou, equivalentemente, que B é superconjunto de A Em teoria dos conjuntos, quando todo elemento de um conjunto A é também elemento de um conjunto B, dizemos que A é um subconjunto de B, denotado A \subseteq B (também dito "A é uma parte de B" ou "A está contido em B").
Novo!!: NP-completo e Subconjunto · Veja mais »
Tempo de execução
Em informática, tempo de execução ou runtime (termo em inglês), é o período em que um programa de computador permanece em execução.
Novo!!: NP-completo e Tempo de execução · 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-completo e Teorema de Cook-Levin · 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!!: NP-completo e Teoria dos grafos · Veja mais »
Tetris
Exemplo de jogo inspirado em Tetris Tetris é um famoso jogo eletrônico do gênero quebra-cabeça criado por Alexey Pajitnov, lançado em junho de 1984.
Novo!!: NP-completo e Tetris · Veja mais »
Torre de Hanói
Um Modelo das Torres de Hanói Torre de Hanói é um quebra-cabeça que consiste em uma base contendo três pinos, em um dos quais são dispostos alguns discos uns sobre os outros, em ordem crescente de diâmetro, de cima para baixo.
Novo!!: NP-completo e Torre de Hanói · Veja mais »
Vértice
Em geometria, um vértice é um ponto em que duas ou mais curvas, retas ou arestas se encontram.
Novo!!: NP-completo e Vértice · Veja mais »
