The NP-completeness column: An ongoing guide

DOI10.1016/0196-6774(86)90011-8zbMath0608.68033OpenAlexW4240842367MaRDI QIDQ5903311

David S. Johnson

Publication date: 1986

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(86)90011-8

zbMATH Keywords

monotone circuit complexitybounded depth complexitybounded width branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (5)

Classification of the index sets of low \([n^ p\) and high \([n]^ p\)] ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\) ⋮ Algorithmic aspects of switch cographs ⋮ \(NC^ 1\): The automata-theoretic viewpoint ⋮ Non-uniform automata over groups

This page was built for publication: The NP-completeness column: An ongoing guide