Redução polinomial e NP-completude

Como já foi dito, há muitos problemas de computação com aplicações práticas importantes para os quais não conhecemos algoritmos eficientes. Isto posto, uma ideia é investigar a complexidade relativa dos problemas em . Um problema não é mais difícil que um problema se uma solução para implica numa solução para com perda de desempenho polinomial relativa a eficiência da solução de . Façamos isso mais preciso.