Complexités

**mio** · 05/09/2002, 17h24

lol, enfin je me comprends...

**victorracine** · 05/09/2002, 18h23

est ce que les ordinateurs quantiques (s'il existait) fonctionneraient comme des machines de turing non deterministes?

**mio** · 05/09/2002, 18h38

Je te conseille vivement de lire cet article si tu veux la reponse a ta question.
http://www.cagou.com/informatique/quantas.htm

Quantum computers can, in theory, make computations which are impossible to do exactly with classical computers or achieve exponential speedup. Since nobody has yet (as of November 2001) implemented more than a few bit operations, problems such as decoherence and measurement error may limit quantum computation to a few specialized roles.

**victorracine** · 06/09/2002, 11h16

ben c'est cool tout ça, il y aura du boulot en algorithmique qui ils arriveront...

**btavernier** · 06/09/2002, 13h27

Ca sera moins cool quand on aura cassé l'algorithme clé publique-clé privée...

Ca va être un beau bazard ce jour là...

**victorracine** · 06/09/2002, 13h54

ça doit quand meme etre possible de trouver des algo de cryptage donc le decryptage soit exponencielle pour une machine de Turing non deterministe...

**mio** · 06/09/2002, 15h29

Evidemment, aucune raison que ca n'existe pas. D'ailleurs il y a des problemes plus difficiles que les problemes np-complet.
http://www.myoo.fr.st/algo/complexite.php