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 impaire. 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
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
- 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
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.