Fonction parité | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function. The parity function is notable for its role in theoretical investigation of circuit complexity of Boolean functions. The output of the parity function is the parity bit. The -variable parity function is the Boolean function with the property that if and only if the number of ones in the vector is odd. In other words, is defined as follows: where denotes exclusive or. Parity only depends on the number of ones and is therefore a symmetric Boolean function. The n-variable parity function and its negation are the only Boolean functions for which all disjunctive normal forms have the maximal number of 2 n − 1 monomials of length n and all conjunctive normal forms have the maximal number of 2 n − 1 clauses of length n. Some of the earliest work in computational complexity was 1961 bound of Bella Subbotovskaya showing the size of a Boolean formula computing parity must be at least . This work uses the method of random restrictions. This exponent of has been increased through careful analysis to by Paterson and Zwick (1993) and then to by Håstad (1998). In the early 1980s, Merrick Furst, James Saxe and Michael Sipser and independently Miklós Ajtai established super-polynomial lower bounds on the size of constant-depth Boolean circuits for the parity function, i.e., they showed that polynomial-size constant-depth circuits cannot compute the parity function. Similar results were also established for the majority, multiplication and transitive closure functions, by reduction from the parity function. established tight exponential lower bounds on the size of constant-depth Boolean circuits for the parity function. Håstad's Switching Lemma is the key technical tool used for these lower bounds and Johan Håstad was awarded the Gödel Prize for this work in 1994. The precise result is that depth-k circuits with AND, OR, and NOT gates require size to compute the parity function.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (4)

Cours associés (1)

Séances de cours associées (2)

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é. 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, et indépendamment à Miklós Ajtai. C

Algèbre de Boole (logique)

Lalgèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de variables, d'opérateurs et de fonctions sur les variables logiques, ce qui permet d'utiliser des techniques algébriques pour traiter les expressions à deux valeurs du calcul des propositions. Elle fut lancée en 1854 par le mathématicien britannique George Boole. L'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.

Circuit booléen

vignette|Exemple circuit booléen à deux entrées et une sortie. Le circuit contient 3 portes logique. En théorie de la complexité, un circuit booléen est un modèle de calcul constitué de portes logiques (fonctions logiques) reliées entre elles. C'est une façon de représenter une fonction booléenne. Un circuit booléen peut être utilisé pour reconnaître un langage formel, c'est-à-dire décider si un mot appartient ou non à un langage particulier. Les caractéristiques des circuits qui reconnaissent un langage permettent de définir (ou redéfinir) des classes de complexité.

CS-524: Computational complexity

In computational complexity we study the computational resources needed to solve problems and understand the relation between different types of computation. This course advances the students knowle

Optimisation booléenne: MIGs et portes majoritaires CS-472: Design technologies for integrated systems

Explore l'optimisation des fonctions booléennes à l'aide de Majority-Inverter Graphs et Majority Gates, y compris les règles algébriques et la synthèse exacte.

Automatiser les preuves logiques de premier ordre en utilisant la résolution CS-550: Formal verification

Couvre la syntaxe logique de premier ordre, la sémantique, la skolémisation, la résolution et les transformations de formes normales.