In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth
Boolean circuits. It was first introduced by
Johan Håstad
Johan Torkel Håstad (; born 19 November 1960) is a Swedish theoretical computer scientist most known for his work on computational complexity theory. He was the recipient of the Gödel Prize in 1994 and 2011 and the ACM Doctoral Dissertation ...
to prove that
AC0 Boolean circuits of depth ''k'' require size
to compute the
parity function 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 it ...
on
bits.
He was later awarded the
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...
for this work in 1994.
The switching lemma describes the behavior of a depth-2 circuit under ''random restriction'', i.e. when randomly fixing most of the coordinates to 0 or 1. Specifically, from the lemma, it follows that a formula in
conjunctive normal form
In Boolean algebra, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs.
In au ...
(that is, an AND of ORs) becomes a formula in
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster c ...
(an OR of ANDs) under random restriction, and vice versa. This "switching" gives the lemma its name.
Statement
Consider a width-
formula in
disjunctive normal form
In boolean logic, a disjunctive normal form (DNF) is a canonical normal form of a logical formula consisting of a disjunction of conjunctions; it can also be described as an OR of ANDs, a sum of products, or in philosophical logic a ''cluster c ...
, the
OR of clauses
which are the
AND of ''w'' literals (
or its negation
). For example,
is an example of a formula in this form with width 2.
Let
denote the formula under a random restriction: each
is set independently to 0 or 1 with probability
. Then, for a sufficiently large constant ''C'', the switching lemma states that
:
where
denotes
decision tree complexity, the number of bits of
needed to compute the function
.
Proof
Intuitively, the switching lemma holds because DNF formulas shrink significantly under random restriction: when a literal in a clause is set to 0, the whole AND clause evaluates to zero, and therefore can be discarded.
The original proof of the switching lemma involves an argument with
conditional probabilities. Arguably simpler proofs have been subsequently given by and . For an introduction, see Chapter 14 in .
Bounds on AC0 circuits
The switching lemma is a key tool used for understanding the circuit complexity class
AC0, which consists of constant-depth circuits consisting of AND, OR, and NOT. Håstad's initial application of this lemma was to establish tight exponential lower bounds for such circuits computing
PARITY, improving on the prior super-polynomial lower bounds of
Merrick Furst,
James Saxe
James may refer to:
People
* James (given name)
* James (surname)
* James (musician), aka Faruq Mahfuz Anam James, (born 1964), Bollywood musician
* James, brother of Jesus
* King James (disambiguation), various kings named James
* Prince Ja ...
and
Michael Sipser
Michael Fredric Sipser (born September 17, 1954) is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massa ...
[Merrick Furst, James Saxe and Michael Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Annu. Intl. Symp. Found.Computer Sci., 1981, '' Theory of Computing Systems'', vol. 17, no. 1, 1984, pp. 13–27, ] and independently
Miklós Ajtai
Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (devel ...
. This is done by applying the switching lemma
times, where
is the depth of the circuit: each application removes a layer of the circuit until one is left with a very simple circuit, whereas PARITY is still PARITY under random restriction, and so remains complex. So, a circuit that computes PARITY must have high depth.
The switching lemma is the basis for bounds on the Fourier spectrum of AC
0 circuits
and algorithms for learning such circuits.
See also
*
AC0
*
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inpu ...
*
Circuit satisfiability
*
Circuit value problem
*
Parity function 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 it ...
References
*
*
*
*
{{refend
Computational complexity theory
Circuit complexity