Content deleted Content added
→References: use direct link to Allender article |
→History: mention Shannon |
||
Line 23:
==History==
Circuit complexity goes back to [[Claude Shannon|Shannon]] (1949), who proved that random Boolean functions with ''n'' inputs require circuits of size Θ(2<sup>''n''</sup>/''n''). In his 1999 book on circuit complexity, Vollmer states (pg. 1) that "the direction which ''complexity theoretic research on circuits'' took was heavily influenced by Savage's textbook", citing Savage 1976.
===Key results===
| |||