Hola Kiko gregoris.

Yo tb estudié hace algunos años la complejidad computacional, autómatas,
lenguajes, máquinas de turing, etc. Intercambio contigo lo que entendí

En este contexto, como bien dices, la "complejidad" de una solución se mide en
tiempo.

Hay varias familias de problemas que no pueden resolverse en tiempo polinomico
(problemas NP) en una máquina de turing. En otras palabras, hay problemas que
son irresolubles (en el sentido que tomaría muchísimo tiempo) por una máquina de
turing para entradas de datos o o parámetros lo suficientemente grandes. Por eso
lo de "problemas complejos" y lo de "complejidad".

Una cosa que me parece interesante es que hay "intereses contrapuestos" en
estudiar este tipo de problemas: por un lado hay gente que busca diseñar
soluciones no complejas para problemas que se creían complejos con motivo de
obtener salidas más rápidamente. Pero por otro lado, hay gente que utiliza el
problema para resolver otros problemas: por ej: los sistemas de encripcatión que
se basan en que no existe un algoritmo que no sea NP para determinar los
factores primos de un natural.

También es interesante ver como se relaciona el tema de la complejidad con el
sistema de cómputo y lo que se estudia en la facultad vale solo para máquinas de
turing. Ver como por ejemplo los sistemas cuánticos de cómputo, al no ser
máquinas de turing, tienen otro conjunto de problemas NP.

Un saludo

P/D: es de mala etiqueta componer mensajes de correo en formato html. se leen
como se ve más abajo.

On Sat, 7 Jun 2008 06:49:12 -0700 (PDT)
kikoGregoris <kikogregoris@...> wrote:

> Hola
> &nbsp;
> Estoy cursando ciencias de la computación y se me ha pedido una monografía
sobre Complejidad Computacional.
> &nbsp;
> Lo primero que me llama la atención es que se usa la palabra complejidad
relacionado a un coste de tiempo o espacio para computar un algoritmo por parte
de una maquina.
> Según entiendo la complejidad esta dada por el grado de interrelación que
tienen los subsistemas de un sistema dado.
> La pregunta es:
> Porqué se mete el termino complejidad en algo que esta relacionado con un
coste para computar un algoritmo ¿?.
> &nbsp;
> Por otra parte veo que hasta el día de hoy, no se&nbsp; ha podido avanzar
mucho mas de lo que definió hace algunas décadas Alan Turing, es decir la
maquina de turing.
> Lo digo por que hoy seguimos pensando en&nbsp; lenguaje de computación que no
es, ni mas ni menos que&nbsp; una MT, como así también lo es una computadora
actual.
> &nbsp;
> Ahora la parte donde quiero relacionar a ST con estas cosas.
> &nbsp;
> Mirando un mail sobre AI de hace algún tiempo encuentro esto que decía Ale:
> &nbsp;
> En los abordajes relacionados con AI siempre encuentro
> &nbsp;la cota del "computo" (y el&nbsp;embelezamiento&nbsp;por lo reflexivo)
> &nbsp;es decir, lo encuentro acotado a la computación; y por eso
> &nbsp;se asegura una cota en la simulación.
> Nuestro motivante en cambio esta relacionado con&nbsp;la informática
> &nbsp;y no poseemos el limite de "la computadora" .
> Nosotros estamos dentro de lo que nos convoca.
> &nbsp;
> Lo que me interesaría es si es posible explicar un poco mas esto de no poseer
los limites de la computación.
> &nbsp;
> También encontré este comentario en un mail histórico.
> &nbsp;
> Generalmente estos temas parecen no llevarnos a nada,
> pues lejos estamos de que haya un avance en "hardware"
> que nos permita explorar o acentar las ideas. De todas
> maneras, aunque estemos lejos y tratando de sacar chispas
> en esta edad de piedra de los objetos, creo que no debemos
> perder de vista hacia donde vamos y marcar al menos
> algunas veces que no estamos acotados por el uso de
> computadoras ni por el esquema de Turing.
> &nbsp;
> Bueno, Escucho ofertas..
> &nbsp;Saludos kiko
>
> __________________________________________________
> Correo Yahoo!
> Espacio para todos tus mensajes, antivirus y antispam ¡gratis!
> ¡Abrí tu cuenta ya! - http://correo.yahoo.com.ar


--
Sebastian Gurin <sgurin@...>