The Complexity of Finite Functions
- 1 January 1990
- book chapter
- Published by Elsevier BV
Abstract
No abstract availableThis publication has 49 references indexed in Scilit:
- Bounded-width polynomial-size branching programs recognize exactly those languages in NC1Journal of Computer and System Sciences, 1989
- Lower bounds on the size of bounded depth circuits over a complete basis with logical additionMathematical Notes, 1987
- Lower bounds on monotone complexity of the logical permanentMathematical Notes, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Short monotone formulae for the majority functionJournal of Algorithms, 1984
- A Boolean function requiring 3n network sizeTheoretical Computer Science, 1983
- On the complexity of the marriage problemAdvances in Mathematics, 1972
- The complexity of the realization of symmetrical functions by formulaeMathematical Notes, 1972
- Method of determining lower bounds for the complexity of P-schemesMathematical Notes, 1971
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965