• [^] # Turing

    Posté par . En réponse à la dépêche Les promesses de la Native POSIX Threading Library et du prochain Kernel 2.6. Évalué à 2.

    En toute rigueur, la notation O(...) définit le nombre d'opérations nécessaires à une machine de Turing, pas le temps mis pour résoudre le problème. Cela veut dire par exemple que si tu considères une machine parallèle, les temps peuvent diminuer à O(...) constant. Cf. les récentes avancées en matière de cassage de RSA par Bernstein. Celui-ci n'a pas diminué la complexité algorithmique (vis-à-vis d'une machine de Turing), mais le temps mis par une machine "réelle" pour effectuer ces opérations.