O que é NP-completo?

NP-completo é uma classe de problemas de decisão em ciência da computação. Um problema é considerado NP-completo se: 1. Ele pertence à classe NP (nondeterministic polynomial time), ou seja, se uma solução pode ser verificada em tempo polinomial. 2. Todos os problemas em NP podem ser reduzidos a ele em tempo polinomial. Isso significa que, se conseguirmos resolver um problema NP-completo em tempo polinomial, poderemos resolver todos os problemas em NP de forma eficiente. Exemplos clássicos de problemas NP-completos incluem o problema do caixeiro viajante e o problema da satisfatibilidade booleana (SAT).