Lesson plan

Circuit complexity

s, the \vee nodes are OR gates, and the \neg nodes are NOT gates. In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits C_{1},C_{2},\ldots (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that \mathsf{NP}\not\subseteq \mathsf{P/poly} would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC 0 , AC, TC 0 , NC 1 , NC, and P/poly.

Back to article

Article summary

s, the \vee nodes are OR gates, and the \neg nodes are NOT gates. In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits C_{1},C_{2},\ldots (see below). Proving lower bounds on size of Boolean circuits computing explicit Boolean functions is a popular approach to separating complexity classes. For example, a prominent circuit class P/poly consists of Boolean functions computable by circuits of polynomial size. Proving that \mathsf{NP}\not\subseteq \mathsf{P/poly} would separate P and NP (see below). Complexity classes defined in terms of Boolean circuits include AC 0 , AC, TC 0 , NC 1 , NC, and P/poly.

Key claims

  1. date of establishment: 1983 — source: Wikipedia · confidence 0.95

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. The record states that the date of establishment is "1983". What evidence would count against this claim?
  3. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  4. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

  1. Wikipedia https://en.wikipedia.org/w/index.php?oldid=1378001035

Key claims and bibliography are generated from the same tracked claims and sources as the article page.