Complexidade computacional

Conceitos em Ciência da Computação

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Classes de complexidade

Classes de complexidade

Uma animação que mostra todo o espaço de complexidade de problemas

Uma imagem que mostra o conjunto de problemas P

Classe de complexidade -->	P (Tempo polinomial)
O que é	Resolvíveis rápido e de forma eficiente
Exemplo	Ordenar uma lista
Analogia	"Arquivar documentos em ordem alfabética"
Ponto-chave	São "fáceis" em termos computacionais

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Uma imagem que mostra os conjuntos de problemas P e NP

Classe de complexidade -->	NP (Tempo polinomial não determinístico)
O que é	Solução verificável; achar nova solução é difícil
Exemplo	Verificar se um Sudoku está correto
Analogia	"Achar um documento específico com info faltando"
Ponto-chave	Verificar é "fácil", encontrar novas soluções é difícil

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Uma imagem que mostra os conjuntos de problemas P, NP e NP-Complete

Classe de complexidade -->	NP-Complete
O que é	Mais difíceis em NP. Especial: resolve todos de NP
Exemplo	Problema do caixeiro-viajante
Analogia	"Quebra-cabeça complexo: fácil verificar, difícil resolver"
Ponto-chave	Não há solução eficiente conhecida; se houver, resolve todos de NP

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Uma imagem que mostra os conjuntos P, NP, NP-Complete e NP-Hard

Classe de complexidade -->	NP-Hard
O que é	Tão difícil quanto NP-Complete ou mais
Exemplo	Escalonamento ótimo com dependências complexas e não verificável
Analogia	"Agendar reunião ótima com muitas restrições e sem verificação rápida"
Ponto-chave	Pode ser inviável na prática

¹ https://www.baeldung.com/cs/p-np-np-complete-np-hard

Um diagrama que pergunta a velha questão de pesquisa: P=NP?

Conceitos em Ciência da Computação