Es p=np? (actualizado)

Lo que estás a punto de ver, es una puerta que abre un antes y un después en toda la historia de la Computación y de las Ciencias humanas, a tal punto que desde sus mas de 40 años donde se empezo a plantear el problema aún sigue sin Solución y logró trascender en la Historia de la Humanidad.








Antes de seguir el tema, es necesario comprender que es un algoritmo.
Un algoritmo, básicamente es un conjunto de métodos e instrucciones ordenadas para la solución de un problema en particular, hasta ahí todo bien, resulta que es el modo con el que las computadoras pueden resolver aquellos problemas que les presentamos a diario. Existen algoritmos de todo tipo, como por ejemplo este:



Este es un ejemplo claro para tener una noción de Algoritmo.
Un algoritmo funciona paso a paso corriendo por distintos estados según los datos que le son administrados hasta llegar a una solución, que se denominan como "entradas". El conjunto de pasos asi como de variables es finito y su solución no presenta ambiguedades, exceptuando algoritmos como los de Newton o Gauss que presentan relaciones con el infinito que funcionan bajo teoría, pero en práctica no se pueden determinar.



Por qué les hablo de esto?? Porque este tema está íntimamente relacionado a los algoritmos y precisamente a la solución de los problemas.

Todos los problemas tienen solución?

Es una pregunta que nos hacemos a diario, ya sea en la ducha o minutos antes de dormir; implícita o explícitamente, en cada problema que surgue en nuestra mente. Nuestro cerebro tiene ese talento para resolver problemas.
Desde que nacemos, nos enfrentamos a diversos obstáculos que nos presenta la naturaleza. Muchos de ellos son:
-Cómo podré caminar?
-Qué pasa si observo esto?
-Qué pasa si hago tal cosa?
-Como hago una tarta de frutilla?

Estos los resolvemos a medida que vamos creciendo.
Cuando nos damos cuenta de nuestras piernas, nos preguntamos sobre como aprender a caminar, empezamos gateando. Vamos aprendiendo de nuestro entorno hasta que movemos nuestras piernas de una manera poco habitual, es ahí donde nos paramos y al principio nos caemos, pero luego de un par de caídas y demás crueldades de la vida empezamos a ver la realidad con otros ojos.
Aprendemos a caminar.







Ahora bien,
Existe una clasificación que los une y es que son "Problemas".
Que pensarías si yo te dijera que:
-las enfermedades terminales acabarían en un cerrar de ojos?
-se podría viajar en el tiempo?
-se podría determinar como se originó el mundo?

No señores, no es Magia ni ningún tipo de brujería, esto se puede convertir en realidad de la noche a la mañana solo porque P es igual a NP y no solo eso, sino que podríamos imaginar cualquier tipo de situación inalcanzable hecha REALIDAD!



No estoy enloqueciendo y ustedes tampoco están siendo estafados. Para que entiendan de la magnitud de la que les estoy hablando les simplificaré tal desafío mental:



De qué manera me influye P=NP? Primero que aún, no hay solución sobre si P es igual a NP. Por ende, o bien es distinto, o bien es igual. Entender este problema es entender hasta que punto el mundo es computable. Cuáles son los límites de los que una computadora puede resolver o hacer?



La computadora ha sido por excelencia, uno de los productos mas brillantes de la Humanidad en sus intentos por controlar el mundo que lo rodeaba según sus necesidades y beneficios de él y quizá, el de las demas criaturas.

En Ciencias de la Computación, existe una variante que se desprende de la Teoría de la Computación y se llama "Complejidad Computacional", esta se encarga de analizar y estudiar de una manera técnica, la complejidad que viene atada a la solución de una problemática que se puede computar. (Es decir, ser tratado por una computadora)
Por ende, se intenta estudiar que recursos se necesitan para abordar y solucionar un problema a manera de tiempo y espacio. Esto se puede concebir a travéz de las operaciones que los algoritmos suponen.

~a manera simple, todas las cosas que puede hacer una computadora están dadas por la cantidad de operaciones que realiza de manera visible y no visible.

:



Problemas

Son los desafíos a los que una máquina debe resolver.
Estos se dividen en dos grandes grupos:

Problemas Decidibles:

Se pueden algoritmizar.

Problemas Indecidibles:No son algoritmizables o su
estructura supone una complejidad difícil de ser entendida
para transformarla en un algoritmo.

dentro del grupo Decidible encontramos a los problemas "tratables" e "intratables".

Un problema Tratable puede no ser resuelto por un algoritmo debido a:

-No se conocen los algoritmos polinomiales para su resolución. ~Los polinomios son series de números que operan junto a variables, donde la variable no tiene raíz y no divide al número. Por ejemplo: "1x+2"

-Requiere una respuesta de magnitud Exponencial. ~Las cifras exponenciales crecen muy rápido en el tiempo.

-EXPTIME-completo ~Es un derivado de problemas de la calificación "EXPTIME" que esta es es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista. La rama "-completo" es el mas difícil de abordar como por ejemplo: "el problema de evaluar una posición en ajedrez generalizado o damas". Estos juegos tienen una posibilidad de ser EXPTIME-completo porque los juegos pueden durar para varios movimientos a un ritmo exponencial.

No obstante, los problemas intratables pueden ser resueltos por teoría pero no en práctica.

Dentro de los problemas tratables encontramos a los:

-Problemas de Clase P: Son clases de problemas o preguntas que pueden ser resueltos por algoritmos de manera eficiente (resolubles en tiempo polinómico). Hay problemas para los que una posible solución se puede verificar en tiempo polinomial (hay un algoritmo en P que decide la validez de una solución). Este tipo de problemas se encuentran en la clase NP (problemas resolubles de forma no determinista en tiempo polinómico). ~Con esto hace referencia a que, un problema como por ejemplo una ecuación,una computadora puede encontrarle una solución de una forma sencilla y dentro de un tiempo razonable (no tarda mucho en resolverla). se pueden resolver en un tiempo polinómico P(n^k), donde "n" es el tamaño de la entrada (datos que le damos a un algoritmo), "k" es una constante. Esto es la estimación de tiempo donde el ordenador tarda en hacer una operación.

Ejemplo:"La Sucesión de Fibonacci" ~Una suma númerica donde los números se van sumando y cada resultado proviene de los dos número anteriores. (Ejemplo: 0,1,1,2,3,5,8...etc).




-Problemas de Clase NP, donde NP hace referencia a la "No determinación de un tiempo polinómico". Permiten ser resueltos por una máquina de Turing no determinista en tiempo polinómico ~Son problemas de descisión difíciles de resolver si no
hay otros datos adicionales de los cuáles apoyarse, entonces el problema se le puede encontrar solución. Por tanto se emplean modos heurísticos de resolución, (es un algoritmo que abandona uno o ambos objetivos; por ejemplo, normalmente encuentran buenas soluciones, aunque no hay pruebas de que la solución no pueda ser errónea en algunos casos; o se ejecuta razonablemente rápido, aunque no existe tampoco prueba de que siempre será así. Las heurísticas generalmente son usadas cuando no existe una solución óptima bajo las restricciones dadas (tiempo, espacio, etc.), o cuando no existe del todo.) por que su
desenvolvimiento algorítmico y en práctica suelen ser complicados.

Dentro de la clase NP tenemos:

-Problemas NP-completos:
Son problemas de gran complejidad algorítmica y se caracterízan por ser todos iguales que teoría se pretenden "simplificar" con el concepto de transformación polinomial y con ellos poder resolverlos de una manera mas alcanzables por medios computacionales.

Ejemplo:"El Camino Hamiltoniano" ~Un juego que cuyas reglas son las de pasar por todos los vértices de un"camino" sin que pase por un grafo mas de una vez (Un grafo es en sí, un conjunto de "vértices" unidos por enlaces que no formarían una figura geométrica cerrada y que representan relaciones binarias entre elementos en un conjunto).



Actualmente, todos los algoritmos conocidos para problemas NP-completos demandan tiempo exponencial, por lo que se desconoce si hay algoritmos mas rápidos, que es ahí donde quiero destacar.



-Problemas NP-duros: Son problemas dentro de la clasificación -completos donde no son problemas de desición y son "imposibles" de algoritmizar.

Conclusión:

Con esta simplificación si la clase P es igual a NP, entonces todos los problemas podrían tener un atajo que permitan ser resueltos en un tiempo corto para las computadoras, es decír que lo que podría tomar siglos o incluso una cantidad infinita de tiempo en resolver problemas complejísimos lo podría resolver en cuestión de instantes con el método adecuado pasando por diversos estados de abstracción en un problema específico, con esto me refiero a que los problemas podrían ser reductibles. No obstante, si P es distinto de NP, lamentablemente existirá una limitación para cualquier inteligencia artificial o natural. Esa limitación se dará a manera de un tiempo extremadamente largo para la solución algorítmica de problemas a modo exacto o un tema realmente intratable para cualquier inteligencia. Actualmente, muchos científicos están dando por sentado que son distintos.

~Porque de eso tratan de estudiar los investigadores dentro de la Complejidad Computacional, una manera mucho mas fácil y sencilla de convertir un desafío algorítmico en
una suerte de camino mucho mas corto a seguir para la solución de casos exhorbitantemente difíciles en práctica y no solo teórico para computadoras promedio.






Tu que opinas?

P=NP?

Un problema abierto desde 1971. Este problema esta facturado para el que lo resuelva no
solo con 1 millón de dólares, sino con los otros 5 MILLONES de dólares, solo porque sabiendo el resultado de si P=NP con esto se podrían resolver los 7 problemas matemáticos del milenio. Es sin duda una de la multiplicidad de cosas que se podrían llevar a cabo en todas las ciencias computacionales.
Son estos temas interesantes que hacen que la realidad que nos rodea sea mas extraña de lo que aparenta.

Review article. The Status of the P Versus NP Problem

PD: Cualquier error en su interpretación les pido que lo comenten para hacer resurguir la Inteligencia Colectiva. Desde ya muchas gracias