Simple Science

Ciência de ponta explicada de forma simples

O que significa "NP"?

Índice

NP significa "tempo polinomial não determinístico". É uma classe de problemas onde dá pra checar a solução rapidinho, mesmo que encontrar a solução demore um tempão.

O Que Isso Significa

Se você tem um problema em NP, dá pra verificar facilmente se uma resposta dada tá certa. Por exemplo, se alguém diz que resolveu um quebra-cabeça, você pode checar rápido se a solução deles tá correta. Mas encontrar essa solução do zero pode ser complicado e demorado.

Exemplos

Alguns exemplos comuns de problemas NP incluem:

  • Sudoku: Uma vez que você tem um quebra-cabeça completo, é fácil verificar se a solução tá certa.
  • Problema do Caixeiro Viajante: Dada uma lista de cidades, é difícil encontrar a rota mais curta que passe por cada cidade uma vez, mas é fácil checar se uma rota proposta é curta o suficiente.

Importância do NP

Entender problemas NP ajuda na ciência da computação e na matemática. Isso levanta questões sobre se todo problema que pode ser checado rápido também pode ser resolvido rápido. Isso leva a discussões maiores sobre os limites do que os computadores podem fazer e quão eficientes eles são em resolver problemas complexos.

Artigos mais recentes para NP