Me acabo de enterar que cuando tenemos un algoritmo polinomial para NP-completo los problemas, es posible utilizar el algoritmo para resolver todos los problemas NP.
Entonces, la pregunta es: ¿cómo podemos entonces distinguir la no-NP-completo NP problemas de tipo NP-completo los problemas? Parece que todos estos problemas tienen un polinomio algoritmo para convertir a otros problemas...
Como @Jason DeVito se mencionó, esto es imposible si $P=NP$. Si $P\neq NP$, entonces una forma de distinguir sería producir dos problemas NP, a Y B, tal que no es el polinomio de la reducción del tiempo de B a A. Entonces B no es NP-completo. Una forma trivial de hacer esto es dejar que B sea un problema trivial, como la determinación de la membresía en el emptyset. Esto está claramente en NP, pero no puede poli-tiempo de calcular cualquier tipo NP-completo el problema. El punto aquí es que la clase NP se cierra a la baja.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
