Remove ads
La fonction parité est une fonction booléenne. La sortie vaut 1, si et seulement si, le nombre de 1 dans l'entrée est impair. Un cas particulier est la fonction parité avec deux entrées, qui est connue sous le nom de XOR. Cette fonction est centrale dans l'étude des circuits booléens. Le résultat est parfois appelé bit de parité.
La fonction parité un exemple de fonction qui n'est pas dans la classe de complexité nommée AC0. Ceci a été démontré par Furst, Saxe et Sipser[1], et indépendamment à Miklós Ajtai[2].
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads