The NP-completeness column: An ongoing guide
- 1 June 1986
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 7 (2) , 289-305
- https://doi.org/10.1016/0196-6774(86)90011-8
Abstract
No abstract availableKeywords
This publication has 17 references indexed in Scilit:
- The monotone circuit complexity of boolean functionsCombinatorica, 1987
- Unbounded fan-in circuits and associative functionsJournal of Computer and System Sciences, 1985
- Must "Hard Problems" Be Hard?Science, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- A Boolean function requiring 3n network sizeTheoretical Computer Science, 1983
- ∑11-Formulae on finite structuresAnnals of Pure and Applied Logic, 1983
- Some Exact Complexity Results for Straight-Line Computations over SemiringsJournal of the ACM, 1982
- A time-space tradeoff for sorting on non-oblivious machinesJournal of Computer and System Sciences, 1981
- A second step toward the polynomial hierarchyTheoretical Computer Science, 1979