No. Debido a que la transformación del tiempo polinomial (la reducción) podría no preservar la estructura, por ejemplo, la planaridad, mientras calcula y genera el nuevo gráfico. La integridad de NP no se preocupa mucho por las instancias, excepto su equivalencia.
Supongamos que hay un problema P completo de NP, que puede resolver en la clase de gráfico X en tiempo polinómico. Ahora desea utilizar este algoritmo para resolver cualquier problema Q, que está en NP, en la clase de gráfico X en tiempo polinómico. Por supuesto, dado que P es NP-completo, existe una reducción de tiempo polinomial de Q a P. Entonces obtiene un gráfico, que pertenece a la clase de gráfico X, y usa la reducción. Pero la reducción podría sacarlo de la clase de gráfico X, donde no se sabe que P sea polinomial solucionable en el tiempo. Ahí es donde falla el enfoque obvio.
Como consecuencia de una respuesta negativa a su pregunta, las clases de gráficas restringidas se vuelven interesantes. Por ejemplo, la mayoría de los problemas de NP completo son fáciles para la tress, pero hay algunos que siguen siendo NP completos incluso en los árboles (como encontrar el número acromático). Lo mismo ocurre con los gráficos bipartitos, los gráficos perfectos, los gráficos planos, etc. Esto nos dice que los problemas se comportan de manera diferente en las diferentes clases de gráficos, y que debemos profundizar si queremos conocer mejor la relación.
- ¿Se puede almacenar la conciencia humana en una computadora de verdad? Si es así, ¿cuánto tiempo podría tomar desde ahora para lograrlo?
- ¿Es Giga Flops una forma confiable de comparar la velocidad de los procesadores de la computadora (no le interesa la potencia u otros parámetros)?
- ¿Qué hacen los desarrolladores web?
- ¿Tendrán alguna vez las computadoras su propia conciencia?
- ¿Qué pueden aprender los legisladores de la informática?
