Cosmological lower bound on the circuit complexity of a small problem in logic.
Larry J. StockmeyerAlbert R. MeyerPublished in: J. ACM (2002)
Keyphrases
- lower bound
- worst case
- upper bound
- digital circuits
- logic synthesis
- delay insensitive
- branch and bound
- branch and bound algorithm
- optimal solution
- computational complexity
- objective function
- np hard
- complexity analysis
- modal logic
- lower and upper bounds
- space complexity
- decision problems
- circuit design
- high speed
- average case complexity
- sample complexity
- multi valued
- logic circuits
- small number
- special case
- truth table