RSA v/s DSA - Checked by Vexira DEMO version - - Checked by Vexira

[Claudio Baeza Retamal]

Hola,

No leiste bien, explique claramente a que me referia con deterministico,
para que no se confundiera con la nocion de Problemas de decision y
Teoria de Complejidad :) .

Se perfectamente lo que es un problema NP :).

Se supone que una aplicacion de un computador cuantico seria para
problemas NP, pero que pasaria si alguien se ilumina y demuestra
que P=NP?  Ademas se ganaria 1 millon de dolares :), pues pagan 
eso a quien lo resuelva (tambien pagan 1 millon por resolver otros
problemas, como algunos propuestos por Hilbert a principios del siglo
pasado).
 
NP: Ya lo definiste
NP-hard: un problema ¨1¨ de decision es NP-duro, si cualquier problema
         NP se puede reducir en tiempo polinomial a ¨1¨. 
NP-completo: NP y NP-hard
co-NP: no recuerdo muy bien, pero parece que es el problema
complementario al NP, algo si como la negacion o lo contrario al
problema NP. 

El computador cuantico funciona con el principio de ¨entanglement¨, no
se como traducir eso, pero se refiere que el estado cuantico de dos o
mas objetos se puede describir mirando el estado de cada uno de los
objetos, bueno no soy fisico ni matematico, soy informatico, asi que
no se explicarlo con palabras mas simples :).

EL problema de la maquina cuantica, es definir algo que pueda ejecutar
un algoritmo, con las carasteristicas propias de un algoritmo...

Yap voy a seguir trabajando mejor, este tema me gusta mucho...

claudio




On Thu, 2004-06-03 at 17:04, Alvaro Herrera wrote:
> On Thu, Jun 03, 2004 at 04:04:13PM -0400, Claudio Baeza Retamal wrote:
> > El problema es saber si una maquina cuantica sera determinista, en el
> > sentido de que para un mismo problema siempre de la misma solucion, que
> > para un mismo problema, los tiempos de resolucion esten acotados (en el
> > sentido que si para un problema se demoro 2 segundos en resolverlo, en
> > otro intento para el mismo problema no se demore 1 hora), cosas
> > basicas que esperamos de un computador.
> 
> No, precisamente el punto de un computador cuantico es que es no
> deterministico: la idea es poder resolver problemas NP en tiempo P (no
> importa si el tiempo de ejecucion varian de una ejecucion a otra).
> 
> Un problema NP(*) es aquel que "resuelves en tiempo no polinomial en un
> computador deterministico" (donde "tiempo no polinomial" significa que
> el tiempo que necesitas para resolverlo crece exponencialmente segun el
> taman~o de los datos del problema).  En un computador no deterministico
> los puedes resolver en tiempo polinomial.  Ejemplo de esto es la
> solucion del problema del vendedor viajero usando una jugarreta con
> moleculas de ADN llamada "reaccion en cadena de la polimerasa" (PCR).
> Un computador cuantico no es muy diferente en este sentido.  La
> factorizacion es un problema de este tipo.
> 
> Y ojo, aqui decimos "computador cuantico" y a lo que nos estamos
> refiriendo es a una solucion (i.e. un liquido con algunas porquerias
> flotando) de determinadas moleculas a las que se les aplica tal y tal
> estimulo y los resultados se leen de tales y tales maneras
> (espectrografia, cromatografia, ionizacion, fluorescencia, que se yo).
> No es una caja con un teclado y una pantalla.
> 
> (*) la clasificacion de problemas tiene mucha terminologia que
> desconozco; NP-hard, co-NP, muchas otras; cada una tiene propiedades
> particulares, la definicion que doy aqui es vaga.
-- 
Claudio Baeza Retamal <claudio en ing-mat.udec.cl>
Universidad de Concepcion
------------ próxima parte ------------
Se ha borrado un mensaje que no está en formato texto plano...
Nombre     : no disponible
Tipo       : application/pgp-signature
Tamaño     : 189 bytes
Descripción: This is a digitally signed message part
Url        : https://listas.inf.utfsm.cl/pipermail/linux/attachments/20040604/f98629c0/attachment.bin