Skip to content

Circuit Complexity And Boolean Functions

← Back to Domain-Specific Abstractions by Domain

1 domain-specific abstractions whose origin domain is Circuit Complexity And Boolean Functions.

  • Switching lemma — A random-restriction theorem showing that a bounded-width CNF or DNF Boolean formula usually simplifies to a shallow decision tree and can therefore switch to the opposite normal form.