La renovada revista Communications of the ACM ofrece en su edicion de setiembre 2009 un articulo que describe lo avanzado hasta el momento en la resolucion del problema P vs. NP. Respuesta corta? Sigue sin resolverse.

Los artículos que attacho son algunos ejemplos donde se demuestra el porqué de ciertos problemas NP Completos. Espero sea de utilidad. Coloco aquí los abstract de modo sea una guía más fácil.

Corte Máximo

El presente documento brinda un análisis al problema del Corte Máximo. Estudiando su
NP completitud en primer lugar, y dando a conocer mejor función de aproximación que existe
hasta el momento. Junto a ello se muestra un pseudocódigo que permite implementar dicha
función a través de un algoritmo voraz. Dicho algoritmo presenta una complejidad polinómica

Este es el algoritmo que transforma una gramatica, a la forma normal de chomsky; este algoritmo consta de varios algoritmos mas que son su pre requisito: eliminacion de reglas unitarias, eliminacion de reglas lambda(vacio), eliminacion de reglas inutiles y antes de realizar el algoritmo tambien se debe de verificar si existe recursividad en la variable inicial...este trabajo fue realizado para el curso LENGUAJES FORMALES Y AUTOMATAS, entre renzo berru, henry goicochea y yo :P...el programa esta en basic.net(2005)...les dejo el ejecutable tal vez les sea util...saludos......:P

El sudoku es un juego de tipo puzzle que se ha hecho muy popular en todo el mundo, la simplicidad de sus reglas de juego y la complejidad para encontrar la solución al mismo, hacen una combinación un tanto difícil de explicar pero que, en una simple frase "te conviertes en adicto al sudoku".

Sin embargo, el sudoku no es un juego común y corriente, muy por el contrario, en el ámbito de las matemáticas es visto como un problema de satisfacción de restricciones. En el ámbito de la computación, el sudoku es un problema de tipo NP-completo, varios autores lo han demostrado de distintas maneras, por mi parte, basandome en algunos trabajos he hecho lo mío.

Aca dejo un link para que los interesados o los que les gusta el curso de lenguajes formales y automatas y tratan de anticiparse a lo que el profesor hace para que no los jale :P ...les dejo el link de donde el profesor hace clases eBook Automatas y Lenguajes

El presente envio consta del algoritmo para transformar un AFD a ER desarrollado para el curso de lenguajes formales y automatas donde dado un automata finito determinista nos permite determinar cual es la expresión regular propiamente dicha para dicho automata, desarrollado en visual basic; espero sea de mucha ayuda.

En esta nueva entrega les dejo el algoritmo de eliminación de reglas inutiles del curso de automátas, espero les sea de ayuda.

Solo me falta agregar un pequeño codigo donde elimino reglas que se vuelven redundantes, espero les sea de mucha ayuda.

Cualquier duda o comentario es bienvenido.