Logotipo
Unionpédia
Comunicação
Disponível no Google Play
Novo! Faça o download do Unionpédia em seu dispositivo Android™!
Instalar
Acesso mais rápido do que o navegador!
 

P versus NP

Índice P versus NP

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

30 relações: Algoritmo, Aritmética de Presburger, Ciência da computação, Complexidade computacional, Computador, Criptografia, Data Encryption Standard, Engenharia, Enumeração, Fatorial, Força bruta e ignorância, Função polinomial, Hierarquia polinomial, International Standard Book Number, Internet, Logaritmo discreto, Matemática, Máquina de Turing, NP-completo, Otimização combinatória, Problema da mochila, Problema da parada, Problema de satisfatibilidade booliana, Problema do caixeiro-viajante, Problemas do Prémio Millennium, Richard Karp, Senha, Stephen Cook, Teoria da computação, Teoria dos grafos.

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!!: P versus NP e Algoritmo · Veja mais »

Aritmética de Presburger

A Aritmética de Presburger é uma teoria de primeira-ordem dos números naturais com soma.

Novo!!: P versus NP e Aritmética de Presburger · Veja mais »

Ciência da computação

A Ciência da Computação lida com fundamentos teóricos da informação, computação, e técnicas práticas para suas implementações e aplicações.

Novo!!: P versus NP e Ciência da computação · 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 versus NP e Complexidade computacional · Veja mais »

Computador

Um computador pessoal. Columbia, um supercomputador da NASA. Um assistente pessoal digital. Na tecnologia, o computador é um dispositivo eletroeletrônico formado por um conjunto de componentes eletrônicos capaz de executar variados tipos de tratamento de informações (processamento de dados) e de algoritmos.

Novo!!: P versus NP e Computador · Veja mais »

Criptografia

Enigma, uma máquina utilizada na cifragem e decifragem de mensagens criptografadas. chave é utilizada para cifrar e decifrar. Criptografia (kryptós, "escondido", e gráphein, "escrita") é uma área da criptologia que estuda e pratica princípios e técnicas para comunicação segura na presença de terceiros, chamados "adversários".

Novo!!: P versus NP e Criptografia · Veja mais »

Data Encryption Standard

O Data Encryption Standard (DES) é algoritmo criptográfico simétrico selecionado como FIPS oficial (Federal Information Processing Standard) pelo governo dos EUA em 1976 e que foi utilizado em larga escala internacionalmente.

Novo!!: P versus NP e Data Encryption Standard · Veja mais »

Engenharia

capital federal, projetados pelo engenheiro Joaquim Cardozo com bases delgadas que apenas tocam o chão, são as principais conquistas da engenharia estrutural brasileira. A Falkirk Wheel, um exemplo da aplicação de várias técnicas e ciências da engenharia. Engenharia é a aplicação do conhecimento científico, econômico, social e prático, com o intuito de planejar, desenhar, construir, manter e melhorar estruturas, máquinas, aparelhos, sistemas, materiais e processos.

Novo!!: P versus NP e Engenharia · Veja mais »

Enumeração

Em matemática e ciência da computação teórica, a enumeração é a repetiçao de diversas palavras seguidas de virgula.

Novo!!: P versus NP e Enumeração · Veja mais »

Fatorial

Na matemática, o de um número natural n, representado por n!, é o produto de todos os inteiros positivos menores ou iguais a n. A notação n! foi introduzida por Christian Kramp em 1808.

Novo!!: P versus NP e Fatorial · Veja mais »

Força bruta e ignorância

Força bruta e ignorância, em matemática, é o método que consiste em provar algum teorema (ou apresentar algum contra-exemplo) pelo método exaustivo de calcular cada caso possível.

Novo!!: P versus NP e Força bruta e ignorância · Veja mais »

Função polinomial

Gráfico de uma função polinomial Em matemática, função polinomial é uma função P que pode ser expressa da forma: em que n é um número inteiro não negativo e os números a_0, a_1,...

Novo!!: P versus NP e Função polinomial · 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 versus NP e Hierarquia polinomial · Veja mais »

International Standard Book Number

O International Standard Book Number, mais conhecido pela sigla ISBN, é o Número Padrão Internacional de Livro.

Novo!!: P versus NP e International Standard Book Number · Veja mais »

Internet

A Internet é um sistema global de redes de computadores interligadas que utilizam um conjunto próprio de protocolos (Internet Protocol Suite ou TCP/IP) com o propósito de servir progressivamente usuários no mundo inteiro.

Novo!!: P versus NP e Internet · Veja mais »

Logaritmo discreto

Na matemática, especialmente em álgebra abstrata e suas aplicações, logaritmos discretos são grupos análogos a logaritmos naturais.

Novo!!: P versus NP e Logaritmo discreto · Veja mais »

Matemática

problemas matemáticos Matemática (dos termos gregos: μάθημα, transliterado máthēma, 'ciência', conhecimento' ou 'aprendizagem; e μαθηματικός, transliterado mathēmatikós, 'inclinado a aprender') é a ciência do raciocínio lógico e abstrato, que estuda quantidades (teoria dos números), espaço e medidas (geometria), estruturas, variações e estatística.

Novo!!: P versus NP e Matemática · 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!!: P versus NP e Máquina de Turing · 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 versus NP e NP-completo · Veja mais »

Otimização combinatória

A Otimização Combinatória é um ramo da ciência da computação e da matemática aplicada que estuda problemas de otimização em conjuntos finitos.

Novo!!: P versus NP e Otimização combinatória · 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!!: P versus NP e Problema da mochila · Veja mais »

Problema da parada

Na teoria da computabilidade o experimento mental do problema da parada é um problema de decisão que pode ser declarado informalmente da seguinte forma: Alan Turing provou em 1936 que um algoritmo genérico para resolver o problema da parada para todos pares programa-entrada possíveis não pode existir.

Novo!!: P versus NP e Problema da parada · 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 versus NP 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 versus NP e Problema do caixeiro-viajante · Veja mais »

Problemas do Prémio Millennium

Os Prêmios dos Problemas do Milênio (em inglês: Millennium Prize Problems) são sete problemas matemáticos estabelecidos pelo Instituto Clay de Matemática.

Novo!!: P versus NP e Problemas do Prémio Millennium · 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!!: P versus NP e Richard Karp · Veja mais »

Senha

Senha, palavra-passe, palavra-chave ou password é uma palavra ou código secreto previamente convencionado entre as partes como forma de reconhecimento.

Novo!!: P versus NP e Senha · 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!!: P versus NP e Stephen Cook · 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!!: P versus NP e Teoria da computação · 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 versus NP e Teoria dos grafos · Veja mais »

Redireciona aqui:

A questão P versus NP, Classes P e NP, P vs. NP, P=NP.

CessanteEntrada
Ei! Agora estamos em Facebook! »