パリティ関数
計算の複雑さに関する初期の研究の例として、Bella Subbotovskayaによって1961年に示された、パリティを計算するブール式のサイズは少なくとも O ( n 3 / 2 ) {\displaystyle O(n^{3/2})} でなければならないというものがある。これにはrandom restrictionsの手法が用いられた。この指数部の 3 / 2 {\displaystyle 3/2} はその後の慎重な解析によって、PatersonとZwickによって 1.63 {\displaystyle 1.63} に増加され(1993)、さらにHåstadによって 2 {\displaystyle 2} に増加された(1998)。
1980年代初頭、Merrick Furst、James Saxe、Michael Sipserの3人、そしてそれと独立にMiklós Ajtaiが、
パリティ関数に対する constant-depth なブール回路のサイズに関する超多項式下界を確立し、すなわち、多項式サイズの constant-depth な回路ではパリティ関数を計算できないことを示した。同様の結果は,パリティ関数からのreductionによって,多数決関数,乗法関数,推移的閉包関数についても確立された.
Håstad (1987)では、パリティ関数に対するconstant-depth ブール回路のサイズに関する厳しい指数下界が確立されている。Håstad's Switching Lemmaはこれらの下界を得るのに鍵となるテクニカルな補題で、Johan Håstadは1994年にこの研究でゲーデル賞を受賞した。