Fonction parité

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é. Il ne faut pas confondre parité d'un nombre, et le fait qu'il soit pair ou impair (au sens mathématique du terme). Le nombre binaire 00000011 (3 en nombre décimal) est impair (non-divisible par 2) mais de parité paire (nombre pair de bits à 1).

Circuits booléens

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].

Notes et références

  1. ↑ Merrick Furst, James B. Saxe et Michael Sipser, « Parity, circuits, and the polynomial-time hierarchy », Math. Syst. Theory, vol. 17,‎ , p. 13-27 (ISSN 0025-5661, DOI 10.1007/bf01744431, zbMATH 0534.94008)
  2. ↑ Miklós Ajtai, « ∑ 1 1-formulae on finite structures », Annals of pure and applied logic, vol. 24, no 1,‎ , p. 1-48
  • icône décorative Portail de l'informatique théorique
  • icône décorative Portail des mathématiques
Cet article est issu de Wikipédia. Sauf mention contraire, le texte est disponible sous Creative Commons Attribution-Share Alike 4.0. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.