Discusión:NP (clase de complejidad)

Gran error en la definición de NP al comienzo del artículo!

El artículo dice que NP es "el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista". Esto es precisamente lo que NP NO es. Los problemas NP no se sabe si pueden ser resuelto en tiempo polinómico por una máquina de Turing, pero lo que sí cumplen es que, ante una solución propuesta del problema, se puede verificar en tiempo polinomial si la misma es en efecto la solución. Para más detalles se puede ver el artículo de wikipedia en inglés, donde se aclara eso.

Es demasiado complejo el artículo.--190.52.143.6 (discusión) 18:04 16 oct 2009 (UTC)

Error grave

Decía: NP o "No Polinomial" es el acrónimo en inglés de No Polinómico (Non Polynomial)

Lo correcto es: NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo no determinista polinomial").

Se les ruega a las personas que no saben lo que es una máquina de Turing abstenerse de escribir en este artículo. (missing paren (discusión) 19:53 9 ago 2010 (UTC)

Antes (24/6/2010) estaba bien, pero alguien lo echó a perder [1]. Estuvo mal un mes y medio. Pensé que podía haber sido peor. (missing paren (discusión) 19:59 9 ago 2010 (UTC)

Posible Redefinición

Enlace donde se asegura en el Journal American Open Computer Science, la independencia de las definiciones NP y P dentro de la máquina de Turing. Puesto en discusión para su estudio. http://rekpub.com/American%20Open%20Computer%20Science%20Journal/Current%20Issue.php

A modo de resumen, en el artículo se expone:

1. Que efectivamente los problemas de la clase NP son los que se pueden configurar dentro de una máquina de Turing no determinística dentro de una cota polinomial y que existe un conjunto de problemas que están dentro de la clase NP pero que se demuestra que, de existir una notación de Church que encuentre la correspondencia entre la entrada y salida con su certificado (la parte a incluir dentro de la configuración de la máquina de Turing para hacerla determinística) entonces ese código no sería enumerable. Por lo que NP ≠ P.

2. Por otro lado, se dispone de la propia máquina de Turing y se demuestra una relación sorprendente: #P = P. Para ello se fuerza mediante una explosión combinatoria del número de estados para resolver el número de casos en tiempo lineal que satisfacen cualquier fórmula bien formada de la lógica booleana. Debido a que todo problema en #P es acotable polinomialmente a NP, este segundo resultado resulta paradógico con respecto al primero. De ahí la conclusión a la que se llega.

Conclusión del artículo: existen dos filosofías matemáticas (constructivista y formal) donde mediante formalismos podemos axiomatizar las matemáticas haciéndolas más imprecisas pero para obtener más resultados - no en potencia (porque la Máquina de Turing es suficientemente potente) pero sí en eficiencia. De ahí se interpreta que, si bien las aproximaciones no serían aceptables dentro de las máquinas constructivistas, sí es posible darles uso en la vida real y, por tanto, de facto se trata de dos tipos de matemáticas que nos ofrecen resultados diferentes.

El autor no se queda sólo con las palabras, publicar un artículo así es muy complejo porque anula al teorema de Cook; aunque reafirma el teorema de Gödel, porque la notación que escogía Stephen Cook ya de por sí era problemática - así como la clase NP-co. Por esa razón, este tipo de artículos no tienen conveniencia el ser conocidos.

El autor asegura que detrás de estos resultados no hay sólo teoría - también hay un código funcional.