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é.
Circuits booléens
modifierLa 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
modifier- 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)
- Miklós Ajtai, « ∑ 1 1-formulae on finite structures », Annals of pure and applied logic, vol. 24, no 1, , p. 1-48
