Llamamos algoritmos “tractables” a aquellos resolubles en tiempo polinomal en función al tamaño de su entrada. Para algunos problemas existen estos tipos de algoritmos, mientras que para otros no, queremos poder clasificar a los problemas de acuerdo a la complejidad de su resolución.
Definimos un problema abstracto Q como una relación binaria entre un conjunto de instancias y soluciones. Un algoritmo será el que realice ese “mapeo” entre instancias y soluciones.
Son aquellos que buscan la mejor solución ya sea para maximizar o minimizar un resultado.
Son aquellos cuya solución puede tomar como valor SI/NO.
Dado un problema de optimización Q, podemos reformularlo como un problema de decisión (y viceversa). De esta forma encontraremos la respuesta en tiempo polinómico o pseudopolinómico ya que también depende de la complejidad de resolver tal problema de decisión, a su vez si tenemos una forma eficiente de resolver uno también tendríamos una forma eficiente de resolver el otro.
Un algoritmo A resuelve de forma eficiente un problema S si para toda instancia I de S encuentra la solución en tiempo polinomial y por lo tanto existe una constante k tal que A se encuentra acotado superiormente por O(n^k).
Se lo conoce como P al conjunto de problemas de decisión para los que existe un algoritmo que lo resuelve en forma eficiente.
Un algoritmo B certifica/verifica eficientemente un problema de decisión S si para toda instancia I de S, dado un certificado t que contiene evidencia de la solución s(I) es “si” puede verificar esta afirmación en tiempo polinomial.
Se lo conoce como NP al conjunto de problemas de decisión para los que existe un algoritmo que lo certifique de forma eficiente.
¿P c NP? Si el problema Q pertenece a P, podemos definir B(I, t) como:
