Discusión:Teoría de la complejidad computacional

Traducción

Una cosa... este artículo es una mala traducción. No sé si del inglés o de otro idioma, salta a la vista que no es original del español. Hay cientos de adjetivos antepuestos al nombre, palabras mal usadas, etc. He intentado corregir la parte de Intratabilidad, pero no he podido hacer mucho. — El comentario anterior fue realizado desde la IP 83.38.82.148 (discusión • bloq) con fecha 17 nov 2006.

Definiciones

Sé que hay definiciones de P y NP mucho más entendibles y que no necesitan que uno busque en otros artículos para entenderlas. Está bien que se quiera elegancia en las definiciones pero esta enciclopedia está dedicada al público general.

¿ Error de concepto ?

Analizando el artículo de Complejidad computacional, me surgue una duda respecto al siguiente párrafo:

"Hoy en día las máquinas resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas con coste factorial o combinatorio están agrupados en NP. Estos problemas no tienen una solución práctica, es decir, una máquina no puede resolverlos en un tiempo razonable."

La oración resaltada en negrita, creo que expresa un grave error de concepto: los problemas NP no son aquellos que poseen un coste factorial o combinatorio (generalizando, un tiempo No Polinómico), sino que, según el artículo NP, "Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista". Es decir, la N es de "No Determinista" y no de "No Polinómico".

Dejo abierta la discusión para que, en caso de existir un error de concepto, llevemos a cabo lo corrección de dicho error lo antes posible.

Eliminación de sección "Investigadores en el área"

Hola a todos:

Creo que esta sección debe eliminarse. Podría incluir fácilmente a otros 100 personajes a esta lista, lo que sería demasiado, y por otra parte, ponernos a idear criterios de relevancia para ver quién merece estar o no en ella, me parece poco útil. Además, para eso están las categorías (véase, por ejemplo: Categoría:Informáticos teóricos) o bien los anexos (véase Anexo:Lista de informáticos teóricos). Saludos! Farisori (discusión) 22:11 17 abr 2008 (UTC)

Error en la forma de expresar el contenido?

Este parrafo chirria un poco :

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo una complejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y su tiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas que no pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que en general poseen costes factorial o combinatorio, pero podrían ser procesados por una Máquina No Determinística, están agrupados en el conjunto NP. Estos problemas no tienen una solución práctica, es decir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiempo razonable.

Creo que deberiamos dejar a las computadoras, entendiendolas como las maquinas que tenemos cada uno delante de nuestras narices, fuera de este partido. En todo caso se deberia hablar de maquinas deterministas (como algo abstracto) que funcionan como una maquina universal. Es decir, el asunto de P o NP puede ser mas un problema ligado al modelo de computacion que a otra cosa (hasta que se demuestre lo contrario que esta por ver).

Cre que hay un error en la forma de expresarse porque unas veces dice una cosa y otras otra. No es correcto decir que las computadores resuelven solamente problemas mediante algoritmos de complejidad polinomial. Como todos sabemos, un problema de complejidad exponencial suele ser llamado intratable. Vale, pero es que estamos hablando para una "entrada arbitrariamente grande" lo que no significa que para entradas pequeñas se puedan obtener resultados en un tiempo razonable incluso mejor que otro algoritmo polinomial. No se si me explico. Solo hay que recurrir a la definicion matematica de las notaciones Ogrande, omega, Theta, etc.. Por ejemplo, se dice que una funcion f1 esta en el orden de magnitud de otra funcion f2 (notacion O) si se cumple que 0<= f(n) < f2(n)*c / n > k. Esto no implica que para un "n" < k la f1(n) < f2(n)*c. En otras palabras..para "n" < k la funcion f2(n) puede ser mas eficiente que f1(n). En otras palabras de las otras palabras...Un algoritmo exponencial puede ser mas eficiente que un algoritmo polinomico para "n" < k!!. En otras palabras, etc.... SI hay casos en los que puede ser necesario usar algoritmos no polinomiales siempre que se resuelvan en un tiempo relativamente pequeño.

Me imagino que lo que se ha querido decir es que existe una limitacion en el modelo de computacion de modo que este tipo de problemas no puede ser resuelto en cualquier ambito y para cualquier caso pero creo que no es acertado expresarlo asi. Vamos, una cosa es que no se resuelva en un tiempo practico y otro que no puedan resolverse que es lo que se dice en alguna frase (Los problemas que no pueden ser resueltos por nuestras computadoras ). O no se si es que se esta mezclando con el concepto de no computabilidad. No es lo mismo un algoritmo que se resuelve en un tiempo arbitrariamente grande en funcion de la entrada pero con la seguridad de que siempre da una respuesta que un algoritmo que no se sabe si en algun momento encontrara la respuesta. Estos son problemas no computables que, efectivamente, no son computables y no los resuelve.

Creo que habria que revisarlo.

J. Robledo (discusión) 08:05 24 jun 2008 (UTC)

Ciertamente, el artículo posee demasiadas imprecisiones. Lo he agregado en la lista de "artículos por mejorar" en el Wikiproyecto:Matemáticas, a ver si alguien con más tiempo puede hacer las mejoras. Muchos saludos, y gracias. Farisori [mensajes] 17:27 23 jun 2008 (UTC)

Errores gramaticales

Pésima redacción. Se empleó el modo subjuntivo donde debería utilizarse el modo potencial.

Por ejemplo, el autor escribió:

"un algoritmo con tiempo de ejecución exponencial pudiera ser perfectamente aceptable"

Lo correcto es:

"un algoritmo con tiempo de ejecución exponencial podría ser perfectamente aceptable" — El comentario anterior fue realizado desde la IP 190.216.51.10 (discusión • bloq) con fecha 4 nov 2015.

Por favor, adelante, Wikipedia la hacemos todos y no hay un único autor. Puedes modificar los errores cuando gustes. Saludos cordiales, Farisori » 20:22 29 nov 2015 (UTC)