On small generators
From MaRDI portal
Publication:802309
DOI10.1016/0304-3975(84)90058-6zbMath0558.68040OpenAlexW2004060519MaRDI QIDQ802309
Publication date: 1984
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(84)90058-6
Related Items
The complexity of combinatorial problems with succinct input representation, On characterizations of the class PSPACE/poly, Graph isomorphism is in the low hierarchy, Strong and robustly strong polynomial-time reducibilities to sparse sets, Logarithmic advice classes, Probabilistic complexity classes and lowness, On some natural complete operators, Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
Cites Work
- Some consequences of non-uniform conditions on uniform classes
- A note on sparse oracles for NP
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- The polynomial-time hierarchy
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Computational Complexity of Probabilistic Turing Machines
