En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE.
Intuitivement, cette classe contient les problèmes que l'on peut décider avec un nombre constant de pointeurs sur des cases mémoires de l'entrée du problème et un nombre constant de données supplémentaires (des compteurs dont les valeurs sont entre 0 et une grandeur polynomiale en la taille de l'entrée, des booléens, etc.).
Si l'on appelle l'ensemble de tous les problèmes qui sont décidés par des machines de Turing déterministes utilisant un espace (en plus de l'entrée) pour une fonction en la taille de l'entrée , alors on peut définir L formellement par :
Le langage est dans L. Voici un algorithme qui décide en espace logarithmique :
procedure M(w)
si w vide
accepter
i = 0
tant que w[i] == 0
i := i+1
compteurzero := i
tant que w[i] == 1
i := i+1
si w[i] != ' ' (différent de la fin de mot)
refuser
si compteurzero == (i - compteurzero)
accepter
sinon
refuser
Le mot w n'est pas modifié : c'est l'entrée et elle n'est pas comptabilisée dans le calcul de la mémoire utilisée. On ne compte que la mémoire supplémentaire, à savoir, les variables i et compteurzero qui sont des entiers positifs bornées par |w| et que l'on peut coder en espace logarithmique en |w|.
Le langage des mots généré par la grammaire algébrique suivante est dans L : S --> (S) | SS | ε.
La représentation binaire de l'entier est notée dans cette section. Le langage
est dans L.
L'algorithme suivant reconnait en utilisant un
espace en , où est la taille de son entrée. L'algorithme prend en entrée trois entiers n, m et p vérifie que la multiplication de n par m vaut bien p. Il calcule à chaque itération le i bit du résultat de la multiplication et le compare au i bit de p.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
En informatique théorique, et notamment dans la théorie de la complexité, la classe L est la classe des problèmes de décision décidés par une machine de Turing déterministe qui utilise un espace de taille logarithmique en fonction de la taille de l'entrée. Pour être plus précis, l'exigence sur l'espace de taille logarithmique se réfère à l'espace supplémentaire utilisable. Elle est aussi parfois notée LOGSPACE.
En théorie de la complexité, un problème NP-complet ou problème NPC (c'est-à-dire un problème complet pour la classe NP) est un problème de décision vérifiant les propriétés suivantes : il est possible de vérifier une solution efficacement (en temps polynomial) ; la classe des problèmes vérifiant cette propriété est notée NP ; tous les problèmes de la classe NP se ramènent à celui-ci via une réduction polynomiale ; cela signifie que le problème est au moins aussi difficile que tous les autres problèmes de l
En théorie de la complexité, un conseil est une entrée supplémentaire passée à une machine de Turing qui dépend de la taille de l'entrée, afin d'aider la machine à reconnaître un langage. Cette notion est introduite par Richard Karp et Richard J. Lipton en 1982. Étant donnés une fonction et une classe de complexité , la classe est l'ensemble des langages tels qu'il existe un langage et une suite de conseils de taille tels que pour toute entrée de taille , si et seulement si .
In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation.This course advances the students knowle
Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science,
as well as on real-world secure systems. They underlie delegation of computation protocols a
Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a
Couvre les défis dans le raisonnement précis de bits, y compris les résultats SMT-COMP, AIG, bit-blasting, Tseitin transformation, et les classes de complexité.