Sobre clases de complejidad

[u_maligno]

Buenas, no sé si este hilo debería ir aquí o en métodos informáticos, pero como mi duda es bastante general y teórica (no sobre algún lenguaje de programación o método informático en concreto) lo pongo por aqui..

El asunto es que por más que leo sobre el tema (en la Wikipedia principalmente) no me aclaro con algunas cosas. Entiendo que los problemas de clase P son aquellos que se pueden solucionar en un tiempo polinómico, y los de clase NP no se sabe, pero sí se sabe que las soluciones al problema se pueden comprobar en tiempo polinómico.

Entiendo también (bueno, más o menos) que hay una clase de problemas dentro de NP (los NP- completos) a la que el resto de problemas NP se pueden "reducir" (transformar?), también en un tiempo razonable, con lo que, si un problema de este tipo se pudiera solucionar en tiempo polinómico, significaría que todos los problemas de NP se podrían solucionar también, y eso significaría que NP = P.

Hasta aquí todo bien, ya sé que tendría que hacer para ganar 1 millón de dólares y no debería irme por las ramas con otras cosas (no nos engañemos, es la parte más interesante de este tema ). Pero qué hay de los problemas que ni siquiera se pueden comprobar en tiempo polinómico? (o no se sabe si puede hacerse), no existe ningún dilema sobre este tema? Quiero decir, no veo ninguna clase que englobe a NP, pero se me ocurren problemas cuya comprobación podría ser tan costosa como su solución, y que en ninguno de los dos casos pudiera realizarse en tiempo polinómico (con lo que ni siquiera estarían en NP?).

Y algo un poco más concreto, aunque para mi relacionado con la anterior (probablemente por no haber ententido bien alguna parte ), tiene que ver con el problema de la mochila. Aquí yo no veo forma de comprobar nada en tiempo polinómico, pero se supone que el problema es NP (NP-completo de hecho). De qué forma se puede verificar en tiempo polinómico que x combinación de cajas es la que maximiza las ganancias? no habría que verificar exactamente el mismo número de combinaciones que para encontrar la solución?

En fin, que igual me he leído demasiado "por encima" algunas cosas y realmente no he entendido nada (o la idea básica al menos), porque siempre que leo sobre este tema me quedo con la sensación de que hay demasiadas cosas que se me escapan, y así es imposible ganarse 1 millón de dólares.

Salu2

[pod]

NP no se sabe, pero sí se sabe que las soluciones al problema se pueden comprobar en tiempo polinómico.

Más que saberse, ésta es la definición de "NP". Un problema es NP si, y sólo sí, dada una posible solución podemos comprobar si es correcta o no en tiempo polinómico. Eso quiere decir que los problemas P también son NP, $P \subset NP$. Lo que no sabemos es si los problemas NP también son todos P, esto es lo que te daría un millón de napos.

Entiendo también (bueno, más o menos) que hay una clase de problemas dentro de NP (los NP- completos) a la que el resto de problemas NP se pueden "reducir" (transformar?), también en un tiempo razonable, con lo que, si un problema de este tipo se pudiera solucionar en tiempo polinómico, significaría que todos los problemas de NP se podrían solucionar también, y eso significaría que NP = P.

Esto es correcto.

Pero qué hay de los problemas que ni siquiera se pueden comprobar en tiempo polinómico? (o no se sabe si puede hacerse), no existe ningún dilema sobre este tema? Quiero decir, no veo ninguna clase que englobe a NP, pero se me ocurren problemas cuya comprobación podría ser tan costosa como su solución, y que en ninguno de los dos casos pudiera realizarse en tiempo polinómico (con lo que ni siquiera estarían en NP?).

Estos problemas se llamarían "NP-hard" (NP-difícil en español, supongo; donde aquí "difícil" se refiere a la complejidad de la solución). Un problema NP-hard son todos aquellos problemas que son, por lo menos, tan difíciles como el más difícil de los problemas NP. Fíjate que los problemas NP-completos son todos equivalentes entre si, y a su vez todo problema NP se puede reducir a un NP-completo. Por lo tanto, no hay problema en NP que sea más difícil que un problema NP-completo (si A se puede reducir a B, eso quiere decir que la complejidad de B es mayor o igual a la de A; la reducción de un problema puede aumentar su complejidad, no reuducirla). Eso quiere decir que los problemas NP-completos son, a su vez, NP-hard.

Si P = NP, entonces los conjuntos P, NP y NP-completo serian exactamente el mismo. Y todos ellos serian un subconjunto de los NP-hard. En este caso, todos los problemas del mundo serian NP-hard.

Si P $\neq$NP, entonces P seria un subconjunto de NP. Habría una intersección no nula entre NP y NP-hard, esa intersección (que sería disjunta a P) serian los problemas NP-complete. Quedarian problemas NP que no son ni P ni completos (y por lo tanto, tampoco NP-hard).

Fíjate que un problema que se pueda demostrar que es NP-hard y no NP (es decir, puedo demostrar que no hay algoritmo de comprobación polinómico), entonces jamás podrá haber algoritmo de resolución que sí sea polinómico porque la solución nunca puede ser más eficiente que la comprobación (*). El interés de los problemas NP es que "a lo mejor" se pueden resolver en tiempo polinómico. Además, muchos problema de importancia son NP (por ejemplo, si se descubriera que N=NP, la criptografía actual pasaría un mal rato).

(*) Ver que la solución siempre tiene que ser igual o más compleja que la comprobación es fácil. Dada una solución candidata, si tengo una algoritmo que soluciona el problema, siempre puedo ejecutar el algoritmo de solución para ver si el resultado coincide con el candidato. Así, pues, un algoritmo de solución se puede usar como comprobación (pero no a la inversa; un algoritmo de comprobación puede ser más "barato" que uno de solución).

Y algo un poco más concreto, aunque para mi relacionado con la anterior (probablemente por no haber ententido bien alguna parte ), tiene que ver con el problema de la mochila. Aquí yo no veo forma de comprobar nada en tiempo polinómico, pero se supone que el problema es NP (NP-completo de hecho). De qué forma se puede verificar en tiempo polinómico que x combinación de cajas es la que maximiza las ganancias? no habría que verificar exactamente el mismo número de combinaciones que para encontrar la solución?

El problema de la mochila tiene, por lo menos, dos variables.

La variante de decisión seria decir si es posible alcanzar determinado valor dentro del peso máximo. Este sí es NP-completo.

La variante de optimización (encontrar el valor máximo dentro del límite de peso) es al que tu te refieres, y ciertamente no es NP, sólo es NP-hard.

[u_maligno]

Gracias Pod, algo había leído sobre los NP-hard pero no tenía muy claro qué significaba (y bueno, aún me cuesta la verdad ) El resto lo he entendido (creo) pero aquí me pierdo:

Si P NP, entonces P seria un subconjunto de NP. Habría una intersección no nula entre NP y NP-hard, esa intersección (que sería disjunta a P) serian los problemas NP-complete. Quedarian problemas NP que no son ni P ni completos (y por lo tanto, tampoco NP-hard).

Entiendo que si P = NP tanto P, como NP (y NP-completo) serían lo mismo y un subconjunto de NP-Hard. Pero si no lo es lo único que entiendo es que P sería un subconjunto de NP, que ningún problema NP ni NP- completo podría resolverse en tiempo polinómico (pero sí comprobarse) y que todas estas clases seguirían siendo un subconjunto de NP-hard (que incluiría también los problemas cuya comprobación no fuera polinómica). Quiero decir, no veo cómo algunos problemas NP quedarían fuera de NP-Hard, si se demostrara que P no es igual a NP.

El problema de la mochila tiene, por lo menos, dos variables.

La variante de decisión seria decir si es posible alcanzar determinado valor dentro del peso máximo. Este sí es NP-completo.

La variante de optimización (encontrar el valor máximo dentro del límite de peso) es al que tu te refieres, y ciertamente no es NP, sólo es NP-hard.

Ok, ya decía yo. El de la suma de subconjuntos lo entendía (ahí sí que se ve claro que la comprobación es más rápida que la solución) pero este me traía de cabeza

Saludos.

[pod]

que ningún problema NP ni NP- completo podría resolverse en tiempo polinómico (pero sí comprobarse)

Los problemas P también son NP, así que sí que hay problemas NP resolubles en tiempo polinómico. La afirmación que acabo de hacer es cierta siempre, sean P y NP iguales o no.

NP - P seria el conjunto de problemas que no tiene solución polinómica, pero sí comprobación (sería un conjunto vacío si P=NP).

y que todas estas clases seguirían siendo un subconjunto de NP-hard (que incluiría también los problemas cuya comprobación no fuera polinómica). Quiero decir, no veo cómo algunos problemas NP quedarían fuera de NP-Hard, si se demostrara que P no es igual a NP.

Por definición, un problema NP-hard es tan difícil o más como el más difícil de los problemas NP. Así que cualquier problema que sea menos difícil que "el más difícil de los problemas NP" no pertenece a NP-hard. Fíjate que, de nuevo por definición, el "más difícil de todos los problemas NP" es un problema NP-completo (y todos los NP-completos son igual de difíciles). Así que los problemas NP-completos pertenecen a NP-hard, y de hecho la intersección NP-hard $\cap$ NP = NP-completo.

Luego, si P y NP son diferentes, existen problemas que son NP pero no son ni completos ni P. En este caso, NP quedaría dividido en tres regiones, los que son P, los que son NP-completo (y, a la vez, también son NP-hard) y los que no son ni una ni otra.

En la wikipedia he encontrado este diagrama de Venn que lo ejemplifica bastante: https://commons.wikimedia.org/wiki/F...te_np-hard.svg

[u_maligno]

Gracias Pod. Pero hay una parte que me sigue despistando. Por una parte dices que los problemas NP-completos son los problemas NP más difíciles por definición. Y por otra decías que si A se puede reducir a B, eso quiere decir que la complejidad de A es mayor o igual a la de B.

No sé si fue una errata o si por dificultad y complejidad te refieres a cosas diferentes, pero resulta que yo la mayor parte del tiempo lo he entendido así, o sea, que los problemas NP (A) eran más o igual de dificiles que los NP-completos (B). De ahí que me cueste entender que el conjunto NP-Hard sólo englobe a los NP-completos si P no es igual a NP (si es igual ya lo entiendo mejor, porque directamente dejarían de tener sentido todas esas expresiones diferentes )

Saludos.

[pod]

Gracias Pod. Pero hay una parte que me sigue despistando. Por una parte dices que los problemas NP-completos son los problemas NP más difíciles por definición. Y por otra decías que si A se puede reducir a B, eso quiere decir que la complejidad de A es mayor o igual a la de B.

No sé si fue una errata o si por dificultad y complejidad te refieres a cosas diferentes, pero resulta que yo la mayor parte del tiempo lo he entendido así, o sea, que los problemas NP (A) eran más o igual de dificiles que los NP-completos (B). De ahí que me cueste entender que el conjunto NP-Hard sólo englobe a los NP-completos si P no es igual a NP (si es igual ya lo entiendo mejor, porque directamente dejarían de tener sentido todas esas expresiones diferentes )

Saludos.

Tienes razón, el paréntesis donde hablaba de la reducción está al revés. Yo puedo reducir un problema simple a uno complejo, no al revés. El problema al cual reduces debe tener al menos la misma complejidad que el original. Para poder reducir un problema en otro, el segundo debe tener por lo menos la misma complejidad para capturar todos los detalles del primero.

Un ejemplo tonto. Imagínate que yo tengo un algoritmo A que me permite ordenar listas de números cuando todos ellos son enteros. Y otro algoritmo B que puedo utilizar para cualquier lista de números, sean enteros o no. Claramente el algoritmo B resuelve un problema más complejo que A (aunque seria difícil expresar la diferencia con la notación o). Fíjate que yo puedo usar el algoritmo B para resolver el mismo problema que A, pero no a la inversa.

Luego, cualquier problema en NP se puede reducir a un problema NP-completo. Eso quiere decir que un problema NP-completo es tan difícil o más que cualquier otro problema de NP.


PD: Uso el término difícil como sinónimo informal de complejo, para no repetir tantas veces la misma palabra.

[u_maligno]

Ok, gracias pod. Aclarado. Creo que al final sólo era el término "reducir" lo que me despistaba, ya que normalmente quiere decir lo contrario (reducir algo complejo a algo más simple). Aunque en este caso supongo que eso no tendría sentido, a no ser que P = NP claro

Saludos.

[u_maligno]

Buenas, siento reflotar el hilo pero pensando más sobre el tema me han surgido algunas dudas más, en concreto, cómo se mide exactamente el tiempo de un problema/algoritmo?

Estaba pensando en el problema de los números primos por ejemplo, que es uno de los que podría poner en riesgo la criptografía actual (si no entendí mal).

Aquí por más que pienso no veo tiempos factoriales o exponenciales, ni si quiera polinómicos de grado mayor a 1. Hasta con un algoritmo muy poco optimizado no habría que hacer más de una nueva operación (en este caso una división más) por cada nuevo número.

Es así cómo se mide el tiempo de un problema (contando el número de operaciones nuevas por cada nueva iteración) o me estoy haciendo la picha un lío?

Es que no veo en qué afectaría que P fuera igual a NP a este problema en concreto, de hecho no sé dónde leí que habían demostrado (en 2002 o así) que el problema de los primos estaba en P. Algo que también me despista porque me hace pensar que el asunto no es tan obvio como lo veo yo (si no no habrían tardado tanto en demostrarlo )

Y otra cosa relacionada con esto, aunque también con cualquier problema de decisión en general, si la respuesta a la pregunta ¿es x primo? es sí, cómo se verifica en un tiempo menor que el que se necesitó para encontrar la respuesta?

En este caso entiendo que si la respuesta es no (y el número es compuesto) la comprobación sí es más rápida que la solución (siempre y cuando se incluya el número por el que es divisible en la respuesta, claro), ya que sólo habría que hacer una división, por "a saber" cuántas para encontrar la solución (con muchísima suerte sólo 1 también, si resulta que es un múltiplo de 3 y el algoritmo empieza dividiendo por los impares más pequeños)..

Pero qué pasa si la respuesta es sí? aquí no veo forma de comprobar nada de forma más rápida, y con otros problemas como el de la suma de subconjuntos o el problema de la mochila igual pero al revés, si la respuesta es sí se podría comprobar más rápido, haciendo la suma en el primer caso y viendo que es menor a x valor en el segundo, pero si la respuesta es no en ambos casos habría que hacer el mismo número de operaciones para verificar la respuesta, no?

Y volviendo a lo primero, resulta que hace poco conseguí (después de no poco sufrimiento y muchos intentos fallidos ) hacer un programa que calcula el máximo GAP posible (no real) que se puede formar con los múltiplos de x números primos. Es decir, que calcula todas las combinaciones posibles en las posiciones respectivas de los múltiplos y calcula cuál es la que da como resultado un GAP (múltiplos consecutivos) mayor.

Pues bien, resulta que para un número de primos mayor a 10 el programa ya empieza a tardar días o incluso semanas, ya que el número de operaciones a realizar crece de forma factorial (en función del producto de los primos a considerar).. Yo diría que esto es tiempo factorial pero viendo que igual tiro por lo bajini con lo de los primos, etc.. aún podría ser más bestia de lo que pienso (si es que hay algo más bestia que tiempo factorial ), cómo podría calcular, o más bien expresar de forma concreta (con una fórmula chula de esas), el tiempo de este algoritmo?

Y ya de paso, supongo que se podría retocar para hacer que fuera un problema de decisión, preguntando si hay algún gap mayor a x valor (que sé yo, mayor al primo más grande por ejemplo) y que en este caso sería un problema NP (se podría comprobar que x combinación da un GAP mayor a x en tiempo polinómico). Pero, sería NP-completo? Lo de ser bastante difícil de resolver creo que lo cumple a la perfección pero lo de que el resto de problemas NP se pudieran reducir a este ya no lo veo tan claro..

Por cierto, resulta que para los 8 primeros primos (hasta el 19) el máximo GAP que da el programa es justo el doble del primo anterior al más grande. Por suerte pude añadir justo un primo más (antes de que empezara a tardar una eternidad) y ver que para el 23 esto ya no se cumple, y que la sucesión que sigue no está relacionada con los primos (no de forma tan directa al menos) sino con una cosa llamada "Jacobsthal function", que como mi inglés no es muy bueno no sé muy bien qué es (no encontré nada en español) pero parece que tiene que ver con los GAPS de los primos también, y de hecho puede que sea la misma cosa y se calcule igual..

Saludos, y sorry por el tocho, que igual hablo de demasiadas cosas a la vez ..

[pod]

que igual hablo de demasiadas cosas a la vez ..

Pues sí, es casi imposible responder a un mensaje donde sacas tantos temas diferentes. Seria mejor centrarte en una cosa a la vez.

Buenas, siento reflotar el hilo pero pensando más sobre el tema me han surgido algunas dudas más, en concreto, cómo se mide exactamente el tiempo de un problema/algoritmo?

Esencialmente, contando el número de operaciones básica que se deben hacer. Pero hay que tener cuidado a la hora de hacerlo; por ejemplo tu dices:

Aquí por más que pienso no veo tiempos factoriales o exponenciales, ni si quiera polinómicos de grado mayor a 1. Hasta con un algoritmo muy poco optimizado no habría que hacer más de una nueva operación (en este caso una división más) por cada nuevo número.

Aquí estás contando la división como una sola operación. Pero realizar una división también tiene su complejidad algorítmica, no te cuesta lo mismo dividir un número de 2 cifras que uno de 700. Así que añadir una divisón no es sumar uno al numero de operaciones. Tienes que sumar todas las operaciones que hay dentro de la división.

Es que no veo en qué afectaría que P fuera igual a NP a este problema en concreto, de hecho no sé dónde leí que habían demostrado (en 2002 o así) que el problema de los primos estaba en P. Algo que también me despista porque me hace pensar que el asunto no es tan obvio como lo veo yo (si no no habrían tardado tanto en demostrarlo )

Aquí tendrías que ser un poco más explícito. Hay muchísima literatura de números primos, así que no sé a que te refieres con "el problema de los primos". Probablemente existan miles de problemas con números primos.

Y otra cosa relacionada con esto, aunque también con cualquier problema de decisión en general, si la respuesta a la pregunta ¿es x primo? es sí, cómo se verifica en un tiempo menor que el que se necesitó para encontrar la respuesta?

En este caso entiendo que si la respuesta es no (y el número es compuesto) la comprobación sí es más rápida que la solución (siempre y cuando se incluya el número por el que es divisible en la respuesta, claro), ya que sólo habría que hacer una división, por "a saber" cuántas para encontrar la solución (con muchísima suerte sólo 1 también, si resulta que es un múltiplo de 3 y el algoritmo empieza dividiendo por los impares más pequeños)..

Pero qué pasa si la respuesta es sí? aquí no veo forma de comprobar nada de forma más rápida, y con otros problemas como el de la suma de subconjuntos o el problema de la mochila igual pero al revés, si la respuesta es sí se podría comprobar más rápido, haciendo la suma en el primer caso y viendo que es menor a x valor en el segundo, pero si la respuesta es no en ambos casos habría que hacer el mismo número de operaciones para verificar la respuesta, no?

El problema de decidir si un número arbitrario es primo, o no lo es, es polinómico en el número de dígitos de la cifra. Lee sobre el test de primalidad AKS.

El problema difícil (el que afectaría a la criptografía) es la factorización de enteros. Es decir, encontrar los factores primos de un número. Es obvio que este problema es NP, dada una solución candidata solo hay que multiplicar para ver si da el resultado esperado o no; la multiplicación es un algoritmo polinómino en el número de cifras. Hasta donde servidor sabe, no se ha conseguido demostrar si este problema es P o no. Tampoco se ha demostrado que sea (o no) NP-completo, pero generalmente se cree que no lo es.

Y volviendo a lo primero, resulta que hace poco conseguí (después de no poco sufrimiento y muchos intentos fallidos ) hacer un programa que calcula el máximo GAP posible (no real) que se puede formar con los múltiplos de x números primos. Es decir, que calcula todas las combinaciones posibles en las posiciones respectivas de los múltiplos y calcula cuál es la que da como resultado un GAP (múltiplos consecutivos) mayor.

Pues bien, resulta que para un número de primos mayor a 10 el programa ya empieza a tardar días o incluso semanas, ya que el número de operaciones a realizar crece de forma factorial (en función del producto de los primos a considerar).. Yo diría que esto es tiempo factorial pero viendo que igual tiro por lo bajini con lo de los primos, etc.. aún podría ser más bestia de lo que pienso (si es que hay algo más bestia que tiempo factorial ), cómo podría calcular, o más bien expresar de forma concreta (con una fórmula chula de esas), el tiempo de este algoritmo?

Y ya de paso, supongo que se podría retocar para hacer que fuera un problema de decisión, preguntando si hay algún gap mayor a x valor (que sé yo, mayor al primo más grande por ejemplo) y que en este caso sería un problema NP (se podría comprobar que x combinación da un GAP mayor a x en tiempo polinómico). Pero, sería NP-completo? Lo de ser bastante difícil de resolver creo que lo cumple a la perfección pero lo de que el resto de problemas NP se pudieran reducir a este ya no lo veo tan claro..

Por cierto, resulta que para los 8 primeros primos (hasta el 19) el máximo GAP que da el programa es justo el doble del primo anterior al más grande. Por suerte pude añadir justo un primo más (antes de que empezara a tardar una eternidad) y ver que para el 23 esto ya no se cumple, y que la sucesión que sigue no está relacionada con los primos (no de forma tan directa al menos) sino con una cosa llamada "Jacobsthal function", que como mi inglés no es muy bueno no sé muy bien qué es (no encontré nada en español) pero parece que tiene que ver con los GAPS de los primos también, y de hecho puede que sea la misma cosa y se calcule igual..

Yo diría que este es un problema peor que exponencial, pero no factorial, si sólo permites que cada primo vaya con exponente 1. Si tienes N primos, para cada múltiplo posible tienes que decidir si el primo está como factor o no (alternativamente, si su exponente es 1 o 0). Añadir un nuevo primo multiplica por 2 el número de combinaciones, así que el número de combinaciones seria $2^N$. Después, tienes que ordenar los $2^N$. Ordenar n números es un problema $o(n \log n)$, así que si tienes $n = 2^N$ nos iríamos a $o(2^N \log 2^N) = o(N 2^N)$. Finalmente, tienes que recorrer la lista de 2^N números para encontrar el mayor gap, lo cual es proporcional al número de elementos en la lista, así que hay un nuevo factor $2^N$. Todo esto teniendo en cuenta que todas las multiplicaciones cuestan lo mismo, que sabemos que no es así. Por lo tanto, la complejidad de este problema es, por lo menos, si no me he equivocado en el razonamiento, $o(N 2^{2N})$.

Puedes hacer el experimento. Mide el tiempo que tarda el sistema para valores de N crecientes (mejor haciendo una media entre varias repeticiones) y representa el resultado en una gráfica.

[u_maligno]

Ok, gracias Pod. Con el problema de los primos me refería simplemente a saber si un número es primo o no. Pero mi razonamiento (salvo por lo de las divisiones que tienes razón y no lo había tenido en cuenta) de que no se necesitaría más de una "operación" (división) valdría también para el problema de encontrar los factores primos de cualquier número, si no hay algo muy gordo (o tonto) que estoy pasando por alto.

La única diferencia que veo yo entre un problema y el otro es que para saber si un número es primo o no, no es necesario hacer todas las divisiones en el caso de que el número sea compuesto, sólo si es primo. En cambio para encontrar los factores primos de un número habría que hacer todas las divisiones (por números menores su raíz cuadrada) con todos los números. Entiendo que este problema es más difícil pero seguiría siendo, como mucho, una división más por cada nuevo número (algo que me sigue pareciendo bastante poco, o demasiado obvio que es polinómico, en comparación a otros problemas en los que el número de operaciones crece de forma exponencial o factorial).

De todos modos, si no tengo mal entendido, el problema que afectaría a la criptografía sería el de encontrar los dos únicos factores primos de un número (se multiplican dos primos al azar supongo), con lo que en este caso tampoco habría que hacer todas las divisiones y sería como comprobar si ese número es primo o compuesto (o mejor ya que sería siempre compuesto).

Pero vaya, que me da la sensación que estoy pasando algo por alto o no entiendo muy bien algunas cosas (cómo funciona lo de la criptografía más en detalle, cómo medir de forma más precisa el número de operaciones "básicas", etc..) porque obviamente tiene que haber alguna razón por la que se le da tanta importancia a este tema (sólo que a mi, seguramente por ignorancia se me escapa)

Con respecto al problema de los GAPS, no sé si entendí lo de los exponentes (lo leeré más detenidamente en otro momento a ver si lo pillo, aunque aclaro que mi nivel de mates es muy muy básico ). Yo lo que hice es comprobar todas las posibilidades "a lo bruto", asignándole a cada primo todas las posiciones posibles antes de que apareciera su primer múltiplo (y luego registrar todo en una cadena, suficientemente grande para incluir un número razonable de múltiplos, y luego simplente contar hasta que encontrara una posición vacía). O sea, que para registar todas las posiciones posibles tuve que hacer un bucle desde 1 hasta el producto de todos los primos a considerar (de ahí que me pareciera mínimo tiempo factorial, aunque seguramente se puedan hacer algoritmos más eficientes que el mío )

Sobre lo del experimento lo probaré en cuánto tenga un rato, al final parece la mejor forma para medir todo esto de los tiempos jeje (aunque en este caso no podré tomar muchas mediciones, así que me quedaría una gráfica un poco corta )

Saludos.

[Livilro]

Saludos, era para preguntarte pod .

"Eso quiere decir que los problemas P también son NP, . Lo que no sabemos es si los problemas NP también son todos P"

¿ Un problema NP puede estar formado por diversos P no ?

¿Existen problemas NP hard y complete que sean tales consideraciones sin que se puedan extraer problemas P de ellos ?

[pod]

Saludos, era para preguntarte pod .

"Eso quiere decir que los problemas P también son NP, . Lo que no sabemos es si los problemas NP también son todos P"

¿ Un problema NP puede estar formado por diversos P no ?

¿Existen problemas NP hard y complete que sean tales consideraciones sin que se puedan extraer problemas P de ellos ?

No sé si hay una definición precisa de qué significa que un problema esté "formado por diversos problemas". Sin una definición formal, es difícil hacer teoremas matemáticos.

En cualquier caso, ten en cuenta que un número polinómico de problemas P sigue siendo P (porque la multiplicación de polinomios sigue siendo un polinomio). Así que un problema NP no puede estar formado por un número polinómico de problemas P (salvo que P=NP, claro).

[Livilro]

"Un problema NP-hard son todos aquellos problemas que son, por lo menos, tan difíciles como el más difícil de los problemas NP. Fíjate que los problemas NP-completos son todos equivalentes entre si, y a su vez todo problema NP se puede reducir a un NP-completo. Por lo tanto, no hay problema en NP que sea más difícil que un problema NP-completo (si A se puede reducir a B, eso quiere decir que la complejidad de B es mayor o igual a la de A; la reducción de un problema puede aumentar su complejidad, no reuducirla).

¿ Esto implica que p=np "si y solo si" la complejidad y condiciones de ambos fuesen equivalentes ?

( equivalentes no implicando ser iguales )

(si A se puede reducir a B, eso quiere decir que la complejidad de B es mayor o igual ..

"Dos conjuntos A y B son iguales, expresado A = B, solamente cuando constan de los mismos elementos."

'Solamente cuando consta de los mismos elementos', ¿ es tan estricto o equivalentes tambien es valido ? Supongo que cuando dices ""mayor" o igual" complejidad es donde recae la diferencia.



Entiendo que incluso NP se puede reducir a P siempre y cuando ambos tengan asociado un parámetro llamado complejidad ( sea esto lo que sea ), que aumente o disminuya hasta sus máximos correspondientes.

En este caso para reducir de NP a P, será la complejidad de P ( sea esto lo que sea ) la que aumente hasta el máximo, siendo necesario que ese mismo parámetro complejidad pero de NP disminuya hasta el mínimo.


En ese punto NP podría ser igual que P?

[pod]

¿ Esto implica que p=np "si y solo si" la complejidad y condiciones de ambos fuesen equivalentes ?

No sé que quieres decir con "complejidad y condiciones". P y NP son conjuntos de problemas; el concepto de complejidad no se aplica a P. Se aplica, en cualquier caso, a cada problema $p \in P$, por ejemplo.

"Dos conjuntos A y B son iguales, expresado A = B, solamente cuando constan de los mismos elementos."

En la frase que citas, A y B no son conjuntos. Son problemas.

Entiendo que incluso NP se puede reducir a P siempre y cuando ambos tengan asociado un parámetro llamado complejidad ( sea esto lo que sea ), que aumente o disminuya hasta sus máximos correspondientes.

La complejidad no es un parámetro. Cada problema pertenece a una clase de complejidad.

Que un problema A se pueda reducir a otro problema B significa que es posible aplicar una solución de B para resolver A. Por ejemplo, si yo tengo que hacer una suma de tres cifras, y tengo un programa de ordenador que sabe hacer sumas de siete cifras, entonces puedo añadir cuatro ceros delante de las cifras y usar ese programa de ordenador. Es decir, el problema "sumas de tres cifras" se puede reducir trivialmente al problema de "sumas de siete cifras".

El recíproco no es cierto. Si yo tengo un programa que sabe hacer sumas de 3 cifras, no puedo usarlo para resolver directamente sumas de 7 cifras. Las sumas de siete cifras no se pueden reducir a sumas de tres cifras.

De esto, parece evidente que si un problema A se puede reducir a otro problema B, entonces B es igual o más complicado que A. Dicho de otra manera, la reducción de un problema en otro no puede hacerlo más fácil.

En este caso para reducir de NP a P, será la complejidad de P ( sea esto lo que sea ) la que aumente hasta el máximo, siendo necesario que ese mismo parámetro complejidad pero de NP disminuya hasta el mínimo.


En ese punto NP podría ser igual que P?

Creo que esto no tiene absolutamente ningún sentido.

[Livilro]

Yo puedo reducir un problema simple a uno complejo, no al revés. El problema al cual reduces debe tener al menos la misma complejidad que el original. Para poder reducir un problema en otro, el segundo debe tener por lo menos la misma complejidad para capturar todos los detalles del primero.

Un ejemplo tonto. Imagínate que yo tengo un algoritmo A que me permite ordenar listas de números cuando todos ellos son enteros. Y otro algoritmo B que puedo utilizar para cualquier lista de números, sean enteros o no. Claramente el algoritmo B resuelve un problema más complejo que A (aunque seria difícil expresar la diferencia con la notación o). Fíjate que yo puedo usar el algoritmo B para resolver el mismo problema que A, pero no a la inversa.

Saludos Pod eso entiendo por complejidad, no hay mucha duda,
ese párrafo esta muy claro.




P puedo tratarlo como conjunto de diferentes problemas {p1,p2,..}
¿es incorrecto ?, ¿ es lo que refieres con p ∈ P no ?

Por ello asumí A y B como conjuntos,
y perdón...obvié nombrar que la complejidad es en p ∈ P.

Traté tambien a NP como conjunto para enfrentarlos.




Algo tan ambigüo como P y NP, (problemas...será por variedad..) y además nombrando una complejidad intrinseca de los mismos sea lo que sea esa complejidad intrinseca,
entiendo con ello que un problema es reductible "si y solo si" la complejidad (dije condiciones pensando en conjuntos todo el tiempo) se mantuviese igual o aumentase para el problema reducido, nunca que dusminuyese.


clara como el agua esa parte.



Algo mas complejo quiero pensar que tenga mas condiciones en la formulación que algo menos complejo.

Obviamente la complejidad no es un parámetro pero si esta define a los conjuntos de problemas y establece rangos entre ellos puedo usarla a mi favor como un parámetro no ?





(Analizaba entropía de Shanon y un supuesto parámetro complejidad.)