Divulgación Que es P y Que NP

[Richard R Richard]

Entre los famosos problemas del milenio está el problema de P-NP.... entonces en castellano, español, o argentino, que son los tres idiomas que leo perfectamente, y a veces comprendo.

Que es P?

y Que es NP?

He buscado por internet y tiene definiciones matemáticas no se si rebuscadas, pero si muy vagas,.. preferiria si pueden aportarme una definición algo mas terrenal....
no quiero postear lo que presupongo, quisiera una definición mas objetiva, y si no molesta un ejemplo....de ambos casos claro.

[pod]

De forma más o menos vaga (ya que has puesto divulgación), son clases de complejidad correspondientes a problemas cuya solución puede comprobarse de forma rápida. Es decir, si tengo una posible solución al problema, entonces puedo verificar si la solución está bien o no de forma rápida. En este contexto, que algo sea rápido tiene que ver en como aumenta el tiempo necesario (o, equivalentemente, el número de operaciones) según el tamaño del problema. Si n es un número que mide el tamaño del problema, entonces decimos que comprobar la solución es rápido si el tiempo que tardaremos está acotado por un polinomio en n.

Pues bien, hasta ahora lo único que hemos dicho es que es rápido verificar la solución. Sin embargo, realmente lo que nos importa es encontrar la solución. Si existe al menos un algoritmo que nos permite encontrar de forma rápida la solución (es decir, cuyo tiempo de ejecución está acotado por un polinomio en n), entonces diremos que el problema es clase P. En caso contrario, diremos que el problema es NP (es decir, el tiempo de ejecución es exponencial, como mínimo).

Demostrar que un problema es P puede resultar relativamente sencillo; si encontramos un algoritmo que se ejecuta en tiempo polinomial, entonces seguro que es P. A la inversa es más difícil: demostrar que un problema es NP no es tan sencillo, por que el hecho de no conocer un algoritmo no significa que no exista. A la práctica, lo que se hace es intentar reducir el problema que tenemos en mano a otro problema anterior conocido, que se cree que es NP. Cuando podemos hacer esto, decimos que un problema es NP-completo.

En consecuencia, todos los problemas NP-completos son equivalentes entre si. Si al final resultara que P = NP, entonces todos los problemas NP-completos podrían resolverse en tiempo polinomial, ya que al conocer la solución a uno tenemos automáticamente la solución a todos (por definición de NP-completo).

Esto es importante en muchas aplicaciones de computación. Por ejemplo, en seguridad. Consideramos seguras las comunicaciones (bien) encriptadas porque desencriptar el texto es un problema NP-completo, lo cual quiere decir que necesita muchísimo tiempo de computación; tanto que puede ser necesario más tiempo que la vida del universo. Pero si finalmente resulta que P=NP, entonces obtendremos formas eficientes de romper cualquier criptografía actual.

[Richard R Richard]

Gracias por tomarte el tiempo en contestar, en definitiva lo que no tengo claro son dos cosas,

El tiempo es polinomial cuando el tiempo de respuesta o numero de operaciones es menor que $kn^x$ con x y k constantes positivas mayores a 1? Y el problema se vuelve complejo cuando aumenta n

Y seria exponencial si fuera $kx^n$

Por otro lado , encontrar un resultado para un problema difícil, no resuelve el dilema, tampoco lo hace que sea fácil de comprobar que el resultado es correcto.
El tema pasa por conocer el enunciado de un NP completo y dar un algoritmo que lo resuelva en tiempo finito o polinomico en vez de exponencial.

Por que ando preguntando ?,por que hay problemas que dicen que si los resuelves , resuelves el dilema p-np , ej , el problema de las 1000 reinas de ajedrez, distribuir en un tablero de 1000 x 1000 , las 1000 reinas sin que estén en la misma fila, columna o diagonal.
Haces un algoritmo que halle 1 solución en tiempo finito y listo? adiós PNP ?no creo...
Hacer un algoritmo que halle todas las distribuciones posibles , lo veo mas tedioso que exponencial...
Un algoritmo que compruebe que las 1000 posiciones no están en la misma fila, columna y diagonal no tienes mas complicaciones en tiempo que n cuadrado...
no creo que esto resuelva el dilema, pues es un problema P y no NP completo..

Pregunta para otro hilo que enunciados son NP Completos?

[pod]

Gracias por tomarte el tiempo en contestar, en definitiva lo que no tengo claro son dos cosas,

El tiempo es polinomial cuando el tiempo de respuesta o numero de operaciones es menor que $kn^x$ con x y k constantes positivas mayores a 1? Y el problema se vuelve complejo cuando aumenta n

En general, lo que se mide es la complejidad de un algoritmo. En todo problema, hay dos algoritmos relevantes: el algoritmo de verificación (nos dice si una posible solución dada es correcta) y el de resolución (nos permite encontrar una solución correcta sin ningún otro input). Por lo general, nos restringimos a problemas donde el algoritmo de verificación es polinómico; si el de resolución lo es o no nos dirá si es un problema P o uno NP.

Simplemente, si el tiempo de ejecución (o el número de operaciones) al cambiar el tamaño del problema está acotado superiormente por un polinomio, entonces es un problema polinómico. Como nos interesan resultados asintóticos (cuando $n\to\infty$) es suficiente quedarse con la potencia más alta; y las constantes tampoco nos importan mucho. Por eso, suele utilizarse la notación "O-mayúscula". Por ejemplo, si puedes demostrar que el número de operaciones es de la forma $17 n^4 + 1236 n^3 - 79 n^2 + 137 n - 9$, entonces diremos que es un problema $O(n^4)$.

Un ejemplo, la multiplicación de dos matrices cuadradas $n \times n$. Según el algoritmo que nos enseñan en clase, calculamos cada entrada de la matriz resultante de uno en uno; hay $n^2$ entradas a calcular. Para calcular cada una de estas entradas, hay que hacer $n$ multiplicaciones y $n-1$ sumas. Si suponemos que una multiplicación y una suma cuestan lo mismo, eso son $2n-1$ operaciones. Por lo tanto, la complejidad del algoritmo es $2n^3 - n^2 \sim O(n^3)$. Como curiosidad: el algoritmo que nos enseñan no es optimo; se conocen algoritmos más rápidos, llegando hasta un $O(n^{2.373})$. Fíjate que, aunque este exponente no es un entero, se sigue considerando polinomial porque está acotado por un polinomio (una cota, por ejemplo, es el propio $n^3$).

Otro ejemplo, los algoritmos de ordenación. Los algoritmos más naïve, donde cada elemento se compara con los demás, tienen una complejidad $O(n^2)$. Existen otros algoritmos que son algo mejores, como por ejemplo ordenación por mezcla (merge sort, en inglés) o ordenación rápida (quick sort), estos algoritmos son $O(n \log n)$. Se puede demostrar que no puede existir un algoritmo general, basado en comparación, que tena una complejidad menor a esta. Aunque aparece un logaritmo, continúa siendo tiempo polinómico, porque está acotado por un polinomio ($n^2 > n \log n$ cuando $n\to\infty$).

Y seria exponencial si fuera $kx^n$

En efecto, eso sería tiempo no-polinómico, $O(x^n)$. Algo incluso peor que tiempo exponencial seria tiempo factorial, $O(n!)$.

Por otro lado , encontrar un resultado para un problema difícil, no resuelve el dilema, tampoco lo hace que sea fácil de comprobar que el resultado es correcto.

No se trata de encontrar un resultado. Se trata de encontrar un algoritmo que permita encontrar la solución a cualquier instancia del problema en cuestión.

Encontrar un resultado puede ser trivial. Si escogemos una instancia de reducidas dimensiones del problema, aunque sea tiempo exponencial lo podremos calcular con un ordenador potente.

Fíjate que, por construcción, todo problema NP tiene un algoritmo de verificación que es $O(n^p)$. Siempre podemos utilizar el algoritmo de fuerza bruta que consiste en probar todas y cada una de las soluciones posibles. Habrá $O\big(f(n)\big)$ soluciones posibles, así que el algoritmo de fuerza bruta tendrá complejidad $O\big(n^p f(n)\big)$. Este es el peor caso. De aquí sigue que, para todo problema NP, $f(n)$ es peor que un polinomio; si $f(n)$ fuera un polinomio, entonces el algoritmo de fuerza bruta seria también polinómico (el producto de dos polinomios es otro polinomio).

Imagínate, por ejemplo, que $f(n)$ es exponencial. Si el problema que nos interesa es pequeño, por ejemplo n=3, el número de soluciones posible, pese a ser exponencial, es pequeño ($\eee3 \approx 20$). Por eso, por ejemplo, debemos usar contraseñas largas; aunque el algoritmo de criptografía sea muy bueno (tenga alta complejidad), si la contraseña es corta será muy sencillo atacar a la contraseña por fuerza bruta.

El tema pasa por conocer el enunciado de un NP completo y dar un algoritmo que lo resuelva en tiempo finito o polinomico en vez de exponencial.

Exacto. Como cualquier problema NP completo puede reducirse a cualquier otro problema NP completo (por definición), entonces si resuelves un único problema NP, los resuelves todos.

Por que ando preguntando ?,por que hay problemas que dicen que si los resuelves , resuelves el dilema p-np , ej , el problema de las 1000 reinas de ajedrez, distribuir en un tablero de 1000 x 1000 , las 1000 reinas sin que estén en la misma fila, columna o diagonal.
Haces un algoritmo que halle 1 solución en tiempo finito y listo? adiós PNP ?no creo...
Hacer un algoritmo que halle todas las distribuciones posibles , lo veo mas tedioso que exponencial...
Un algoritmo que compruebe que las 1000 posiciones no están en la misma fila, columna y diagonal no tienes mas complicaciones en tiempo que n cuadrado...
no creo que esto resuelva el dilema, pues es un problema P y no NP completo..

No conozco este problema en particular. Pero si este problema es NP-completo, quiere decir que cualquier otro problema NP-completo se puede reducir a este. Y, por lo tanto, solucionar este significa solucionar todos los problemas NP-completos.

Fíjate que, en realidad, todos los problemas NP-completos, estrictamente hablando, están solucionados: tenemos el algoritmo de fuerza bruta. Lo único que ese algoritmo no es polinómico. Así que no basta con "resolver" el problema, tienes que resolverlo en tiempo polinómico.

Pregunta para otro hilo que enunciados son NP Completos?

Aquí tienes quizá un centenar de ejemplos: Lista de problemas NP-completos en wikipedia.

[Richard R Richard]

Sigo dándole vueltas al concepto del desafío, ...el que encuentre solución en tiempo polinómico a cualquier NP completo implicara que entonces los problemas similares NP pasen a ser P por eso quedarían todos los NP como P por lo tanto se quiere llegar a que P=NP .... de ahí esa formulita que lo enuncia simbólicamente y creo haberle entendido el significado.

Otras cosas en ciertos problemas NP completos se pide tomar decisión sobre si un conjunto cumple o no cumple cierto criterio ....
Hay veces que es fácil establecer una regla en tiempo polinómico de los conjuntos que NO cumplen las premisas del enunciado, sin embargo lo difícil es establecer, si el resto de los conjuntos son todos los que Si las cumplen, pues bien podría hacer otro subconjunto que no lo cumpla... Ahora bien esas reglas son parte de la solución o no?

Ej el problema de partición , o partición de números , es la tarea de decidir si un conjunto múltiple S dado de enteros positivos se puede dividir en dos subconjuntos S 1 y S 2 de modo que la suma de los números en S 1 es igual a la suma de los números en S 2 .

es claro que si $S_T=\dst{ \sum \limits_{i=1}^{n} N_i=S_1+S_2=2S_1=2S_2}$ la suma total es impar sabemos que no hay posibilidad de encontrar dichos subconjuntos,.

del mismo modo que si existe algun elemento $N_i>\dfrac{S_T}{2}$

o si existen $N_i,N_j,N_k$ tales que $N_i+N_j\geq N_i+N_k\geq N_j+N_k >\dfrac{S_T}{2}$

que permiten tomar decisiones rápidas y limitar el uso de la Fuerza bruta o bajar los tiempos de la verificación en "tiempos polinómicos", en ese caso estas comprobaciones pueden formar parte parte del algoritmos de verificación....

porque lo que se espera del algoritmo P es que de un simple Si/No correcto para cualquier conjunto...

lo mismo en

El problema de 3 particiones .... decidir si un conjunto múltiple de enteros dado se puede dividir en triples que tienen la misma suma. Dado un conjunto múltiple S de $n = 3 \cdot m$ enteros positivos, ¿se puede dividir S en $m$ tripletes $S 1 , S 2 , ..., S m$ de modo que la suma de los números en cada subconjunto sea igual? Los subconjuntos S 1 , S 2 , ..., Sm debe formar una partición de S en el sentido de que son disjuntos y cubren S . Si $B$ denota la suma (deseada) de cada subconjunto $S i$ , o que la suma total de los números en S sea $m\cdot B$ . El problema es NP-completo cuando cada número entero en S está estrictamente entre $\dfrac{B}{ 4}$ y $\dfrac{B} {2}$.


de nuevo es fácilmente verificable que $S_T=\dst\sum\limits_{i=1}^n N_i= m \cdot B$

luego descomponiendo m y B en minimos común múltiplos y comprobar que $S_T$ sea divisible por todos ellos, para que cualquier otro analisis posterior sea posible...
o bien verificando si $\dfrac{nB}{3}=S_T$

como mis herramientas intelectuales apuntan a resolver todo por fuerza bruta,es que mi pensamiento lineal no me deja alejarme de estas cosas, pero es claro que cualquiera de los dos enunciados es tan vago en cuanto a la aleatoriedad,y variedad de conjuntos que al tener $n\to \infty$ y tratarse de problemas de combinatoria, cualquier combinatoria tiene resultados sobre $n!$ explorar todas las posibles combinaciones es imposible por tiempo.


Del mismo modo se puede analizar para el problema de la partición algunas posibles combinaciones que seguro Si tienen solución, ej

si con subconjuntos disjuntos cuyas sumas sean todos los cuadrados elementos de la sucesion $2\mathbb N$ ascendentes de los números naturales y que la suma de todos ellos supere $\dfrac{S_T}{2}$ entonces ese conjunto puede partirse en dos subconjuntos iguales mientras como dije $S_T$ sea par....

Pero de nuevo esto no garantiza el resultado positivo del 100% de los casos ya que los hay sin que tal regla empírica se cumpla.

En definitiva lo que se busca con este tipo de problemas de decisión es como dije un si/no para el 100% de los casos con n elementos de valor entero aleatorio. Visto así no hay forma más pulida que la propia fuerza bruta... porque es la unica que garantiza la respuesta correcta, tarde lo que se tarde.

[Visitante]

A ver Richard, lo voy a intentar explicar en términos de algo que sé que conoces.

Imagina que el problema al que nos enfrentamos es decir:

Dado un número N cualquiera, cuales son los dos únicos números primos que al multiplicarlos dan como resultado ese N.
(En computación el método de encriptación de la clave pública y la clave privada).

SI N es un número de dos cifras, probablemente me puedas dar la respuesta inmediatamente.

Si el número N es de 50 cifras, puedes poner a una computadora a buscar todos los números primos anteriores al N dado y dividirlo para ver si el resultado es exactamente otro número primo.

Si el número N es de un millón de cifras, no podrás ni con todo el poder computacional del mundo utilizado por 10.000 años dar con la respuesta.

Ves así como resolver el problema pasa de fácil, a medianamente complicado, luego a difícil y finalmente a imposible de resolver en un tiempo razonable, con tan solo aumentar el valor de N.

Sin embargo y aquí está el meollo del asunto, si yo te digo cual fue uno de los números primos que utilicé para obtener el número gigantesco, tu podrás con una simple división, que no te tomará mucho tiempo computacional, obtener el otro número primo.

De manera que la comprobación de una posible solución siempre se realiza en un tiempo razonable.

Pero todo esto al día de hoy, si mañana nos aparece un genio con una fórmula o algoritmo para obtener los dos factores primos al instante, se acabó el problema, porque el grado de complejidad de un problema es el equivalente al grado de complejidad del algoritmo que mejor lo resuelve.

En resumen:
.- La comprobación, dada una posible respuesta, siempre, para cualquier N es casi inmediata.
.- Pero, hacer la búsqueda de una solución es una tarea que crece enormemente en complejidad, con tan solo aumentar un poco el valor de N.

Lo que realmente quieren determinar con el dilema de P = NP es:

¿Siempre es posible encontrar un mejor algoritmo o fórmula que optimice el proceso de búsqueda de la solución y que lo convierta en algo tan sencillo de resolver como la tarea de comprobar si una posible respuesta es la correcta?.

También recomiendo ver el video del enlace:

[Richard R Richard]

Hola , creo que ya he comprendido la diferencia entre P y NP, en P está el meollo, pero veo en la base de los problemas NP completos algo que me tiene un poco todavía por ver para donde van los tiros...
Por ejemplo en la ordenación tu tienes cierta referencia al elemento del grupo, que te permite tomar una decisión y ordenarlo antes de o después de ...., pero en los NP completos, no hay tal referencia, solo se sabe alguna propiedad de grupo que debe ser valida, una propiedad de conjunto que debe ser valida, ni siquiera numero de datos, ni su valor máximo, ni su distribución, es claro que una vez dados, algunas son fácilmente computables o otras no porque requieren explorar muchísimas combinaciones.

Bueno toda mi corta experiencia programando , simples programas, para resolver tal o cual cosa, los he encarado por Fuerza Bruta, incluso la generación de primos, hasta que me enseñaste la criba de eratóstenes, que me hizo ganar un buen tiempo, y dedicar mas esfuerzo a aprender a sumar, restar, multiplicar, dividir, potenciar y radicar stings de números, para sobrepasar la capacidad de calculo de un ordenador normal, y tener números de muchas cifras que puedan ser tratados como enteros.

Bueno hallar un algoritmo para resolver NP completos, es obvio que no es tarea fácil, el video lo vi hace un par de días antes de casualidad, y creo que dice al final que es la forma más difícil de ganar 1 M dolares.

A que iba con eso a que hay en toda solución P que también incluye la capacidad de decir que ese problema tiene o no tiene solución, para lo cual hay ciertos atajos de tiempo polinómico que permiten verlo fácilmente. Pero si tu me dices, que esto es un problema abierto, que va a encontrar un algoritmo que no sea solo fuerza bruta, para cualquier cantidad de datos, con inputs de valor aleatorio, "que por lo menos son números naturales y no reales".. yo de movida digo $P\neq NP$ pero...

a la vez lo veo como un proceso lógico, si tengo un progama que da una solución A , pues lo chequeo con uno mas facil B

si A entonces B sería lo mismo que no B entonces no A , es decir que "no se puede programar solo lo que no puedes chequear".... fin del meollo, P=NP que la solución me tarde mas que el tiempo del universo es otro problema y no de lógica, pero que solucion hay la hay....que la quieran para ya!! es otro tema,y si eliminan la fuerza bruta , alpiste...perdiste.

por eso veo que ciertos problemas NP tiene un P fácil para n pequeños pero también un P fácil para n grandes solo que el tiempo de respuesta del algoritmo , es elevado...

Entonces no veo porque la solución debe necesariamente ser un algoritmo de tiempo polinómico, y no la sucesión de pasos formar un conjunto y con él probar la solución NP ,si es correcto, y se guarda la información, si se vuelve a repetir el mismo conjunto, la solución es inmediata, que necesitamos computadores grandes para conjuntos grandes pues no vamos a ordenar todos los átomos del universo es decir n =10^80

por otro lado generar una tabla,con para generar los primos de 1000000 de cifras, requiere tiempo, que solo vas a emplear una vez y no cada vez que resuelvas el siguiente problema, y tambien bastante memoria, si cada numero tiene varias paginas de dígitos, pero no es tan descabellado como digo, seguir intentando por fuerza bruta, por lo menos los bancos, las criptomonedas, estarán seguros unos cuantos años... y en en cuanto te acerques , le duplicas la cifra y tienes para otros 10000 años de diversión.

A que voy, no entiendo la desigualdad P NP , la veo como igualdad, lo que no es fácil es lograrla en tiempo que a los ordenadores les sea posible resolver en un tiempo humanamente provechoso, y si por lo pronto ningún cráneo de esta era ha podido con esto pasados ya 50 años de era digital, no cero que se lo logre a futuro.

tampoco veo provechoso escoger un Primo de Mersene de esos con notación exponencial, porque una cosa es que se sepa que es primo, debido a una propiedad y otra es escribir en texto de todos sus dígitos....y otra es escribir todos los primos anteriores a es, y dividirlos por todos ellos, para probar que es primo, la verdad no se si eso se ha hecho sobre los mas grandes que han encontrado, juraría que no.
Para codificar la clave pública y privada no le veo diferencia a escoger al azar una porción de un número irracional, sin decir de que número irracional se trate, pues tienes infinitos tanto números como dígitos.... cual sería la utilidad de los primos, que pasa si lo divides por el primo o bloque equivocado, nada no puedes leer igual nada....

[Visitante]

Más que una igualdad matemática creo que lo deberíamos enfocar desde la teoría de conjuntos.

P: Engloba a todos los problemas que pueden ser resueltos en un tiempo razonable.

NP: Se corresponde a todos aquellos problemas en los que si te doy una posible solución tu la puedes “Comprobar o Chequear” en un tiempo razonable, pero encontrar la solución desde cero no es tan sencillo.

De manera que P está contenida dentro de NP, ya que si puedo resolver el problema en un tiempo razonable, también podré comprobar una solución cualquiera en un tiempo razonable.

De forma que “Todo lo que es P” también “es NP”….

Pero lo contrario nadie lo puede asegurar ni negar. No sabemos si todo lo que es NP también es P, porque siempre cabe la duda de si en algún momento llegara a descubrirse un algoritmo que resuelva a todos los problemas NP en un tiempo razonable. Actualmente no existe ese algoritmo, pero no sabemos si en un futuro alguien se lo pueda idear.

No se trata de si los problemas tienen solución o no la tienen, sabemos que la tienen, y tampoco se trata de si necesito todo el tiempo del universo para encontrar la solución o no.

De lo que se trata es de que el ALGORITMO de resolución del problema debe tardar IGUAL o MENOS tiempo en “Encontrar una solución desde cero” que el tiempo que nos tomaría el “COMPROBAR o CHEQUEAR” si una “solución DADA” es la correcta.

Imagina que le doy a un Sujeto A un número muy grande y dos números primos más pequeños y le digo que compruebe si son factores del número grande. Lo único que tiene que hacer es multiplicarlos y verificar que el resultado sea el mismo.

Imagina ahora que te doy a ti solamente el número muy grande y te pido que me encuentres los dos números primos… Te doy todo el tiempo del universo y tú con un algoritmo de fuerza bruta me darás la solución… Solo que te tomará mucho más tiempo que la simple multiplicación del sujeto A.

Imagina Que le damos solo el número muy grande a un Sujeto B, y le hacemos la misma pregunta que a ti, y el sujeto B hace uso de un algoritmo de “Bola de Cristal” que le da inmediatamente, como resultado los dos números primos que al multiplicarse dan el número más grande.

El sujeto B habrá comprobado que P y NP son lo mismo. Ya que encontró la respuesta desde cero más rápidamente de lo que el sujeto A comprobó si tenia los primos correctos, O sea que todo lo que está contenido en NP también está en P.

Muchos de los rompecabezas a los que se enfrenta la computación actual son difíciles de resolver en términos del tiempo, no es que se desconozca como encontrar la solución, es simplemente que se sabe que el algoritmo que de seguro encontrará la solución, no podrá terminar de resolver el problema sino hasta dentro de 10 millones de años. Lo que hace al algoritmo bastante inútil.

Pero los procesos de Búsqueda y Optimización avanzan, todo lo ideado para la Inteligencia Artificial actualmente está enfocado en resolver con mejores algoritmos problemas muy complicados. No es de casualidad que AlphaZero haya entrenado solamente por 14 horas para llegar a un nivel de Ajedrez superior a DeepBlue.

Por acá otro video, pero está en ingles.

Saludos.

[pod]

Comentario quisquilloso sobre tu primera frase: la igualdad de conjuntos es una igualdad matemática.

Todo lo demás es, hasta donde yo llego, correcto.

[Richard R Richard]

Bueno, digamos que la fuerza bruta se le puede llamar tambien algoritmo, que es ineficiente en tiempo, para dar la solución, antes que un algoritmo de comprobación. Bien
Este debate viene por la inexistencia de un algoritmo mas rápido, y sobretodo preciso..

Aún mantengo una duda y creo que me la pueden quitar.

digamos este enunciado, construya un algoritmo, que guarde en archivo una lista o la imprima de los primeros 50 numeros naturales, tratando números como strings por ejemplo,para no cambiar mucho código para números mas grandes.

Salvo mala vista o falta de atención ,podría comerse una unidad, chequeando a vista la lista.

usando recursividad el siguiente número a imprimir es el anterior más 1. supongamos tiempo , 1 milésima de segundo cortando cuando el número es 50

cambiemos y pongamos un input, para establecer el corte en n como número natural, que agregamos entonces..., primero chequeamos que n es natural, y luego a cada paso chequeamos que el último valor sea el de corte.

muy poco varía el tiempo si le ponemos n=50
el tiempo se estira a unos segundos si n es un 1000000.

pero que pasa si es es 10^80 ? un 1 y 80 ceros, el string lo toma...

cuanto tarda el problema en darte la lista, y lo mas difícil en que guardas la lista, no hay tantos átomos en el universo!!!!

Que quiero decir con esto, es que con solo variar n pasamos de un problema sencillo, a uno irresoluble físicamente. No me puedes decir que hay un algoritmo que guarda la lista, noooo, la lista es la solución. Entonces si a una computadora le pido resolver un problema no imposible, sino arduo a cualquier velocidad, no podemos pretender que hay un algoritmo que lo haga mejor. Es decir que haya un algoritmo mejor que la fuerza Bruta.

El problema de la Partición le pasa lo mismo, saber si un conjunto se puede separar en dos conjuntos que sumen igual, es fácilmente checable, y para bajos n , tengo la solución antes que tomes la calculadora para sumar los dos grupos... En este caso, tampoco tengo claro si la respuesta debe ser entregar , el conjunto de números que componen el subconjunto, o decir con certeza si ese conjunto puede o no ser dividido en dos conjunto con igual suma.
Cuando n crece lo que estamos haciendo es pedirle a un ordenador que haga algo "irresoluble" y lo destaco , por los grados de libertad que tienen los posibles inputs, en cantidad y valor unitario.

Ej entras n y la cadena de valores, mientras la entras, la sumas , si la suma es impar , no hay solución, listo al menos el 50% de los conjuntos no tienen solución...

si n=2 entonces compruebas que A=B=Suma/2 listo un P con soluciones positivas y negativas , fin, ese algoritmo sirve... si lo que quieres es complicarla con n más grandes creo que no tiene nada que ver pues ya se que existe un P más rápido que un NP...

si todo el meollo es complicarla con n mas grandes, pues hasta el más sencillo de los problemas es irresoluble fisicamente en algun momento!!!

en definitiva si te dicen n es tanto, y el máximo input es tanto , probablemente , te la puedas ingeniar para llegar a algún algoritmo, pero la combinatoria de posibilidades con n y x_i variables, hace fallar a cualquier método de ordenación de conjuntos, ergo, no se le puede pedir peras al olmo, ni a un CPU procesar tamaña cantidad de posibilidades....

puedes establecer algunas normas que se tienen que cumplir en todos los conjuntos

como dijimos la suma total Par
si existe un elemento igual a la mitad de la suma total, hay solución
si existe un elemento mayor a la mitad de la suma total,no hay solución
que existan 3 elementos que tomados de a dos sumen mas que la mitad de la suma total, entonces no hay solución.
que si todos lo elementos son pares y la suma total no es divisible por 4 ,no hay solución.
si es posible encontrar elementos que sean todos los cuadrados menores a la mitad de la suma hay solución
y lo mismo si se pueden hallar conjuntos disjuntos tales que cada uno sume el valor de cada cuadrado menor a la mitad de la solución, pues entonces también hay solución.

Etc, y puedo pensarme otras, n=3 es igual de fácil que n=2 y n=4 es resoluble aplicando solo algunos de estos párrafos anteriores.

y pulir algunos conceptos mas, que reducen mas el porcentaje de soluciones posibles para cualquier n, pero pedir precisión a n muy grandes, me pregunto para que...

entiendo los otros NP de m conjuntos de tanta suma S ,pero me sucede lo mismo, que 2 conjuntos m de los millones quede con más o menos de S en que afecta.... aquí interviene algo sencillo y es que S da el tamaño máximo de los valores que se pueden poner en un subconjunto.

Por otro lado si los datos pertenecen a una sucesión de números aleatorios normales llevados a natural, es muy factible, que si haya solución,
un tanto menos obvio si es una distribución gausiana...
pero mucho mas allá , al menos en mi ingenuidad creo que no se puede avanzar,
cuando la suma total es muy grande , y no hay muchos valores alejados de la media y cuando n también es grande , es fácil crear un algoritmos que creen dos subconjuntos que difieran en la mínima cantidad .El error al relativo de la suma de esos subconjuntos con la mitad necesaria es el mínimo lógicamente, incluso 1 unidad en miles de millones, acaso eso importa, cual es la finalidad de la exactitud para justificar millones de horas extra de proceso por cambiar un subconjunto de elementos de un grupo al otro, con el objeto que sumen uno unidad más y otro una unidad menos, y entonces hay solución,

Que es más importante que sea exacto, a tiempo casi infinito, o con mínimo error en un tiempo acotado, para n muy grandes si se quiere....

[Visitante]

Se trata de ¿Cómo crece el grado de complejidad a medida que crece el Problema?

Utilicemos como ejemplo al rompecabezas del Sudoku y acotemos el estudio a la familia de los sudokus cuadrados, para no liarnos tanto.

Tenemos una n que indica la base del sudoku y que puede variar de uno en uno, así que para el primer problema utilizaremos n=1.

CASO TRIVIAL (n=1)
Para determinar la grilla del sudoku haremos
n * n = 1 * 1 = 1
De tal manera que el primer problema de sudoku que puedo plantear es el que utiliza:
1 fila, 1 columna, 1 región y solo 1 dígito
El único problema que puedo plantearte es darte una casilla vacía y la única solución es llenarla con un 1
En resumen para el caso de n = 1 tenemos
n=1, Espacio de soluciones = 1, Espacio de Problemas =1

Ahora demos un paso más y tomemos n = 2

CASO SHI-DOKU (n=2)
Para determinar la grilla del sudoku haremos
n * n = 2 * 2 = 4
De tal manera que para este caso el problema de sudoku que puedo plantear es el que utiliza:
4 filas, 4 columnas, 4 regiones y 4 dígitos
Ahora la cantidad de soluciones posibles son 288 y la cantidad de problemas que puedes plantear son 13.579.680

Ahora demos un paso más y tomemos n = 3

CASO SUDOKU TÍPICO (n=3)
Para determinar la grilla del sudoku haremos
n * n = 3 * 3 = 9
De tal manera que para este caso el problema de sudoku que puedo plantear es el que utiliza:
9 filas, 9 columnas, 9 regiones y 9 dígitos (Este es el juego que aparece en todos los diarios)
Ahora la cantidad de soluciones posibles son 6.670.903.752.021.072.936.960 y la cantidad de problemas que puedes plantear aún no han sido calculadas a ciencia cierta.


Pero demos un paso más y tomemos n = 4

CASO EXTENDIDO (n=4)
Para determinar la grilla del sudoku haremos
n * n = 4 * 4 = 16
De tal manera que para este caso el problema de sudoku que puedo plantear es el que utiliza:
16 filas, 16 columnas, 16 regiones y 16 dígitos
Ahora la cantidad de soluciones posibles se estiman en 5.9584×10^98 y simplemente no se sabe la cantidad de problemas posibles

Aclarando entonces algunos conceptos:

.- La fuerza bruta es el “Algoritmo por Excelencia” para resolver problemas en los que se conoce el espacio de las soluciones, esto es porque, tal como ya lo aclaró POD, siempre puedes encontrar la solución al problema recorriendo el espacio de las soluciones hasta hallar la indicada.

.- En cuestiones de Sudoku por ejemplo para un n = 10, ya estaríamos tratando con una grilla o matriz de 100x100 números, de tal modo que ni siquiera puedo pensar en calcular el espacio de soluciones que tendrá un problema de este grado, por lo que un algoritmo de “fuerza bruta” nos resultará bastante inútil en la práctica. Sin embargo, si te doy una posible solución, un algoritmo solo tendrá que comprobar una lista de 10.000 números, para ver si tomados de 100 en 100 no se repiten nunca en filas, columnas ni regiones.

.- Y aunque parece una pérdida de tiempo dedicar tanto razonamiento y estudio matemático, junto con bastantes horas de cálculo computacional a algo tan trivial como un rompecabezas de Sudoku, ocurre que también como lo indicó POD, todos los problemas del tipo NP Completos se pueden reducir a solo UNO, y por tanto el algoritmo que resuelva correctamente y en un tiempo igual o menor que la simple comprobación un problema del Sudoku luego puede ser adaptado para resolver problemas de mayor relevancia.

.- Para finalizar como se trata de ¿Cómo crece el grado de complejidad a medida que crece el Problema?
En el ejemplo del sudoku los problemas crecen polinómicamente en “n cuadrado”, sin embargo el espacio de soluciones pasa de 1 a 288 y luego a 6.670.903.752.021.072.936.960 y luego se estima que a 5.9584×10^98, lo que me parece que es un incremento más que exponencial, por lo que un algoritmo de fuerza bruta queda obsoleto e inoperante muy rápidamente, para valores de n muy bajos.

Como ves no se intenta arrancar desde cero con un problema de plano ya imposible en cuestiones de tiempo o átomos totales en el universo para poder almacenar resultados, sino en estudiar a todos los problemas en conjunto y tratar de entender no solo a un problema en particular sino a toda la familia de problemas del mismo tipo.

Algunas de las páginas consultadas para dar los datos

http://theory.tifr.res.in/~sgupta/sudoku/shidoku.html

https://en.wikipedia.org/wiki/Mathematics_of_Sudoku

[Richard R Richard]

Gracias por contestar. . esta claro lo del crecimiento super archi super claro .....con posibilidades de que no lo entienda como de una en dodecagono del 1000 de este video

pero en el sudoku , cual es la incógnita?para ser calificado como un NP que no se sabe de P

1. la incógnita es resolver un sudoku ? por medio de un ordenador? el de 3x3 con pistas no lleva mas de media hora a mano , no puedes decir que en ese tiempo mi cerebro analizó 6.670.903.752.021.072.936.960 posibilidades....
2. obtener el número de posibles sudoku que se pueden formar a partir de una matriz de n elementos por lados? ... debe haber una fórmula teórica le aplicas que quieres y te da el numero... fin del rollo... que me dices que no existe tal fórmula , "que flipo y no me la creo" ya me parezco a un español contestando , jaja
3. Empezando de 0 hallar una matriz de nxn donde no se repitan los números en fila y columna, es tan sencillo como listar los números por fila, hacer $(n\times n) -1$ matrices restantes,sin repetir elementos donde las n-1 a la derecha o avanzando por fila, las consigues cambiando la primera fila de la arriba y colocandola en la ultima fila abajo ., y vuelves a repetir tomando base en la segunda matriz para hacer la tercera matriz.Del mismo modo avanzas descendiendo en la misma columna, cambias la primera columna dela izquierda y la colocas última ala derecha, de ese modo no puedes repetir números en toda la columna.Si sigues ese criterio, para las restantes matrices que o bien te quedan a la derecha o abajo, listo tienes una solución...Menos de un segundo le lleva a un programa darte una solución, ...... que ....que no es aleatoria? bueno llenas la primer matriz en orden aleatorio, escoges una rutina de millones aleatoriamente. 1 x 3 la 3 x 2,etc sin que se hagan lazos cerrados para intercambiar filas sin repetir y si quieres criterio otro distinto para columnas.... repites el criterio para formar las nxn, y tienes un sudoku $n^2\times n^2$ instantáneo y bastante aleatorio....que es difícil ?...no lo creo... lo difícil es dejar las pistas para que sea resoluble por pensamiento lógico, al extraer la mayoría de su contenido....eso si ya lo creo...
4. Que lo difícil es hacer los lazos cerrados.... mmm no se para n pequeños es fácil hasta visualizando con grafos de cada numero de fila o columna deben venir dos conectores, uno de entrada y uno de salida, que no haya lazos cerrados significa que si empiezo a recorrer los conectores, para volver al mismo nodo debo haber pasado por todos los restantes...

De este modo te hago un sudoku de $n^2\times n^2$ en fracción de segundos.... o me salto algo,quiza, nose se que el número de sudoku posibles crece factorialmente respecto de n,pero quien se los resuelve todos, y si los quieres tener impresos para ir borrando los que crees se pueden completar por lógica deductiva , no te alcanzan los átomos del universo facilmente...pero de nuevo para que o con qué objeto alguien se pondría a resolver un sudoku de 10000 x 10000 , le llevaría la vida intentar dar solución ,y no creo que se tarde segundos en crearlo.
eso si creo a ojo de buen cubero que se tarda más tiempo en crearlo que en checarlo,

el tema es así si con soluciones NP en tiempos polinómicos cualquier problema cuyo n tienda a infinito se vuelve inalcanzable igual para cualquier máquina, porque exigirle eso mismo a P ...

en el problema de la partición lo difícil es hallar el subconjunto, para dar una solución, en el sudoku no....por el contrario siempre es posible crear uno de las dimensiones que sean
en ambos checar es fácil es decir son NP..,no se si completos....
en el del sudoku siempre hay solución posible, y resolución lógica partiendo de pistas precisas, pero en el de la partición no hay seguridad de que haya solución.
en ambos la cantidad de posibles escenarios es altísima....Pero entonces , es esta es la incógnita cuántas posibles combinaciones hay?
como te digo no se puede construir un programa general que cree todas las sumas de n números enteros aleatorios y sin limite de valor absoluto, que se pueda dividir en dos conjuntos cuya suma se al misma
pero si un programa que cree un sudoku $n^2\times n^2$ en un tiempo relativamente corto.
creería que no son dificultades del mismo tipo.


me he puesto a calcular cual es el numero de combinaciones del sudoku de n y es$N=\dst\prod\limits_{i=0}^{n^2} (n^2-i)!$

para n=2 tenemos N=288
para n=3 no coincido N=$9!8!7!6!5!4!3!2!1!0!=1834933472251084800000$ posibilidades que no son pocas

también se puede hallar haciendo $N=\dst\prod\limits_{i=1}^{n^2} i^{(n^2-i+1)}$

[Visitante]

para n=2 tenemos N=288
para n=3 no coincido N=$9!8!7!6!5!4!3!2!1!0!=1834933472251084800000$ posibilidades que no son pocas

también se puede hallar haciendo $N=\dst\prod\limits_{i=1}^{n^2} i^{(n^2-i+1)}$

Contar las posibles soluciones del Sudoku 9x9 no fue tan fácil, por acá tienes la página de los que contaron y enumeraron a cada una de las soluciones.

http://www.afjarvis.staff.shef.ac.uk...u/bertram.html

En un Problema de Sudoku te dan una grilla con algunos datos o pistas, al menos 17 pistas para asegurarse de que sea un problema de una sola solución, y el trabajo consiste en encontrar los números que faltan, cada uno de los números es el único que cabe en cada casilla para completar correctamente el Sudoku. De tal manera que en cada FILA en cada COLUMNA y en cada REGIÓN estén contenidos todos los dígitos del 1 al 9 sin repetición.

Si son 81 casillas en total y ya nos están dado 17 pistas nos quedan 81-17 = 64 casillas para ser llenadas. En programación y por fuerza bruta nos podríamos ingeniar unos 64 bucles anidados de 1 a 9 de tal manera que solucionaríamos de seguro el problema en 9^64 pasos como máximo. (= 1,1790184577738583171520872861413e+61)

Por supuesto que utilizando la Lógica el problema planteado puede ser resuelto de forma más expedita (20 minutos como bien dices por una persona y fracciones de segundos por un computador), sin considerar recorrernos todas las posibles soluciones y tampoco tener que buscar exhaustivamente en todas las combinaciones posibles. Utilizando atajos heurísticos.

La cuestión está en que incluso utilizando la lógica el problema crece mucho en complejidad cuando se trata de un Sudoku 16x16 , en nuestro siguiente "n", y dicha complejidad crece en general mucho más rápidamente que lo que hacemos crecer a "n".

Así la cosa, en un Sudoku Cuadrado de 5000x5000 podemos plantear un problema, y cualquier programa de computadora al que le demos una posible respuesta nos podrá decir en un tiempo más que razonable si dicha respuesta es la correcta o no. O sea podrá solicitar la Comprobación y esperar por el resultado.

Sin embargo si le pedimos a esa misma computadora que nos calcule la solución del problema sin darle ningún dato adicional, sino solamente el problema en cuestión, seguramente que nos podremos sentar a esperar la repuesta porque tardará más de un año en poder darla.

Saludos.