Discusión:NP-hard

Estoy intentando enterarme de la diferencia entre np-hard y np-completo y leyendo por aquí me parece que he llegado a una 'contradicción'. En este artículo se comenta que la suma de subconjuntos es un ejemplo de np-hard, sin embargo según el propio artículo del problema y el artículo de np-completo, es un ejemplo de np-completo. Si np-completo es un subconjunto de np-hard (que no lo acabo de saber a ciencia cierta), realmente no el ejemplo no es erróneo, pero no lo encuentro ilustrativo, si no más bien lioso, al menos se podría que aclarar este punto. A lo mejor estoy metiendo la pata, porque sigo sin aclararme, si es el caso, lo siento mucho :) Edu

NP-hard son problemas tan o más difíciles que uno de NP. Incluyen entonces, además de NP-completo, clases de problemas mucho más complejos, como el de parada, mencionado en el artículo.
NP-completo son los problemas representativos de NP. Aquellos tales que resolviendo uno, resuelves todos los de NP, pero no los más complejos que NP. Saludos. --Ascánder 04:23 13 may 2006 (CEST)

Mira, un problema es NP-duro (NP-hard) si es tan o más dificil que cualquier otro problema en NP; en términos más técnicos, si todo problema en NP puede reducirse a éste en tiempo polinomial. Para que un problema sea NP-completo debe cumplir dos condiciones: 1. que sea NP-duro y 2. que esté en NP. Espero haber aclarado tu duda.

El problema de parada es "NP-hard"

También he quedado muy confundido con la descripción de los problemas NP-hard, pero lo que más me sorprendió es la clasificación del "problema de parada" en NP-hard cuando la misma wikipedia admite que se trata de un problema indecidible y por tanto no es transformable el problema de satisfacibilidad booleana (el cual es NP) en el "problema de parada" de la máquina de Turing. Seria como hacer insoluble un problema que tiene solución (absurdo).

Quisiera también comentar que el término NP tiene dos traducciones una es "polinomio no determinista" y la otra "no polinómico", lo cual ha dado también lugar a confusiones. He visto artículos en revistas, incluso, en donde se comenta que el problema de N = NP (?) por el que se ofrece el premio del millón de dólares, se trata de demostrar si es posible o no trasformar todo algoritmo no polinómico en un algoritmo polinómico, lo cual, creo, se ha demostrado que no y imagino que no debe ser una demostración muy complicada (¡nadie ha ofrecido un premio por eso, ni siquiera he visto en ningún libro especializado que se trate de un problema irresuelto!).

Noto también cierto tono hostil en la forma en como respondiste el al comentario anterior. ¿Que significa eso de "mira"?. Espero recibir una respuesta más cordial.... de lo que se trata es de mejorar la wikipedia.

alexvillalb159@hotmail.com

Saludos. Como se ha mencionado antes, NP-hard puede explicarse como NP-completo o peor. Entre los peores están también los indecidibles, como el problema de parada.

Hasta pronto. --Ascánder (discusión) 23:09 10 abr 2008 (UTC)

Pero el problema de parada no es un problema dificil o peor sino algoritmicamente IMPOSIBLE, a menos que disientas de la teoria oficial --Usuario:AlexanderV

14 - 4 - 2008: Insisto en que hay un error en cuanto a lo escrito de que el problema de la parada sea transformable en el de la insatisfacibilidad booleana y no me imagino de donde se pueda haber sacado eso. Tampoco se trata de que se disienta: simplemente no se sabe de que se esta hablando :(

Estoy muy decepcionado no solo por lo dicho sino por esa actitud de no habrirse al dialogo. De no discutir, como si esta no fuese una wikipedia abierta y desarrollada por todos --Usuario:AlexanderV

Hola, probablemente tus objeciones tienen que ver con la definición de "más difícil que NP", pero ella es muy amplia: Cualquier problema que no pueda ser resuelto con un algoritmo en NP.

Los que no pueden ser resueltos del todo caen allí, como el problema de parada que no es NP (y el artículo por supuesto no dice que lo sea). --Ascánder (discusión) 15:02 16 abr 2008 (UTC)

El articulo no dice que el problema parada sea NP pero dice que se puede transformar en un problema NP (específicamente el de insatisfabilidad booleana), lo que es decir lo mismo con otras palabras.

La forma en como se elabora esta transformación es en verdad trivial.

Vi algo parecido en una pagina Web. Pero lo que se decía en ella no era la transformación del problema de parada en el de insatisfabilidad booleana, sino que basándose en el problema de parada o mejor dicho en el teorema de que no es posible diseñar un algoritmo que determine si una maquina de Turing se parara o no. Basándose en eso, entonces se podía demostrar que para un algoritmo dado no era posible determinar si este se pararía o no para una entrada X...

Es decir cualquier algoritmo se podría transformar entonces en nada más y nada menos que el indecidible problema de parada. Pero eso si, distorsionando lo que decía esa página Web (lo cual era razonable)....

¿no consideras que es confuso el articulo, en esto que dice o que puede estar equivocado (un error no pequeño)?.... espero que no ignores la pregunta como usualmente haces con casi todo lo que escribo. --Usuario:AlexanderV

Textualmente dice: el problema de satisfacibilidad booleana puede reducirse al problema de parada transformándolo en la descripción de una máquina de Turing ... Eso es cierto de cualquier algoritmo. Más adelante dice que el recíproco (el lado que te preocupa) no se cumple: Para ver que el problema de parada no está en NP es suficiente notar que todos los problemas de NP tienen un algoritmo asociado pero el problema de parada es indecidible. Saludos. --Ascánder (discusión) 02:30 17 abr 2008 (UTC)

Bien Ascander propongo dejar esta discusión o mal entendido hasta aqui, por ahora.... aunque aun creo que el articulo es confuso en ese aspecto que te plantee.

"Eso es cierto de cualquier algoritmo" <--- ¡te hice concluir eso! yo esperaba que tuvieses más cuidado o que me expresaras tu desacuerdo (¿entonces porque precisamente el de insatisfabilidad boolena?)... yo mismo no estoy muy satisfecho con la sugerencia y no la escribí convencido, aunque fuese razonable...

Estaré investigando más sobre teoría de complejidad computacional.

Tal vez, luego de un tiempo pueda sugerir otra forma de enunciar o replantear tu afirmación....

mi correo es: alexvillalb159@hotmail.com

me gustaría escribirte.... sino tienes inconveniente en ello...

Me parece que no hay error en lo escrito en el artículo, lo que por supuesto no quiere decir que no se pueda expresar mejor y Wikipedia te invita a colaborar en el artículo si tienes ideas para mejorar su redacción o completarlo. Puedes escribir a mi correo aquí. Saludos. --Ascánder (discusión) 17:09 17 abr 2008 (UTC)

El problema de parada NO es "NP-hard"

Quisiera corregir la siguiente afirmación en discusión:

NP-hard son problemas tan o más difíciles que uno de NP.

Lo correcto es decir:

NP-hard son problemas tan o más difíciles que TODOS los NP juntos. 

Sin embargo, también tiene que existir una relación Polinomial que los vincule, y esto excluye a los problemas indecidibles como el de parada. Por tanto debe revisarse el artículo.

Nótese que debe existir relación polinomial para vincular un problema de decisión con otro, o de lo contrario se podría tener dos problemas NP y ninguno completo porque no sería posible una trasformación determinística dentro de la cota polinomial. JuanManuelDato (discusión) 16:05 24 ago 2015 (UTC) He estado revisando del artículo en inglés su argumentario:

 ...it to the description of a Turing machine that tries all truth value assignments and when it finds one that satisfies the formula it halts and otherwise it goes into an infinite loop.

La razón por la cual el algoritmo de parada se considera NP-duro es porque, en su formulación, de existir tal configuración permitiría decidir cuándo una fórmula de la lógica se resuelve y, como según el teorema de Cook, satisfacer una fórmula de la lógica es suficiente como para satisfacer cualquier NP, entonces el problema de la parada sería NP-duro. Esto podría valer de explicación. Aunque, debemos partir de que afirmaremos de que hay selenitas jugando al tenis en la Luna: porque una configuración que está demostrada que no existe no puede ser vinculada polinomialmente con otra configuración. El uso del lenguaje es demasiado formal - aunque desde cierto punto de vista matemático-filosófico entiendo que se quiera postular así.

No hay que olvidar de que, en informática, el concepto NP-duro sólo sirve para hacer demostraciones - no para programar [salvo que nos dé por usar un algoritmo truncado en una base de datos]. Por eso la valoración de que el algoritmo de parada pueda ser NP-duro puede ser considerado una afirmación independiente de las definiciones que usamos en computabilidad. JuanManuelDato (discusión) 09:18 25 ago 2015 (UTC)