P=NP = ¿?
ALGUIEN QUE ME AYUDE PORFAAA
Respuestas
Respuesta: Hay otra clase de problemas, a la que llamamos NP, cuya definición está hecha de tal manera que incluye todos los problemas de la clase P, pero también otros muchos que se comportan de un modo intrigante. Uno de esos problemas es el llamado problema del viajante de comercio: dado un mapa de carreteras, consiste en encontrar el camino más corto para visitar n ciudades una sola vez y volver al punto de origen. Para estos nuevos problemas de la clase NP, los mejores algoritmos que se conocen tienen un coste similar al de los problemas intratables, pero nadie ha podido demostrar que no existan algoritmos polinomiales para ellos. Tampoco nadie ha demostrado que sean intratables. Están, por decirlo así, en una especie de limbo informático: no se sabe si son polinomiales, o si son intratables. La teoría desarrollada en estos años ha llegado sin embargo a alguna conclusión útil: ha definido una subclase de la clase NP, la subclase de los problemas NP-completos, en la cual se agrupan los problemas más costosos de la clase NP, de tal forma que, si para uno cualquiera de dichos problemas se encontrara un algoritmo polinomial, entonces todos ellos se resolverían en tiempo polinomial y además la clase NP colapsaría a P, es decir tendríamos la igualdad P=NP. Más aún, si se demostrara que uno solo de los problemas NP-completos es intratable, entonces todos ellos lo serían y tendríamos la desigualdad P≠NP.
Explicación paso a paso:
Explicación paso a paso:
sorry bro I don't know this question answer because this question is very tough for me because I don't know this language