Problemas Relacionados Computacionalmente

Examinamos varios problemas de áreas como flujos de red, teoría de juegos, inteligencia artificial, teoría de grafos, programación entera y programación no lineal y mostramos que están relacionados en el sentido de que cualquiera de estos problemas es soluble en tiempo polinómico si todos los demás también lo son. En la actualidad, no se conoce ningún algoritmo de tiempo polinómico para estos problemas. Estos problemas amplían la clase de equivalencia de problemas conocida como P-Completo. El problema de decidir si la clase de lenguajes aceptados por máquinas de Turing no deterministas de tiempo polinómico es la misma que la aceptada por máquinas de Turing deterministas de tiempo polinómico está relacionado con problemas P-Completos en el sentido de que estas dos clases de lenguajes son las mismas si cada problema P-Completo tiene una solución determinista polinómica. A la luz de esto, parece muy probable que esta clase de equivalencia defina una clase de problemas que no se pueden resolver en tiempo polinómico determinista.