Quelle est la taille minimale d'un circuit qui calcule la PARITÉ?
C'est un résultat classique que chaque circuit fan-in 2 ET-OU-NON qui calcule la PARITÉ à partir des variables d'entrée a une taille d'au moins , ce qui est net. (Nous définissons la taille comme le nombre de portes ET et OU.) La preuve est par élimination de porte et elle semble échouer si nous...