The relative power of logspace and polynomial time reductions
From MaRDI portal
Publication:1312179
DOI10.1007/BF01271369zbMath0801.68063MaRDI QIDQ1312179
Harry Buhrman, Leen Torenvliet, Edith Hemaspaandra
Publication date: 19 January 1994
Published in: Computational Complexity (Search for Journal in Brave)
circuits; reductions; polynomial time; branching programs; complexity classes; logspace; truth-table
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- A comparison of polynomial time completeness notions
- Space-bounded reducibility among combinatorial problems
- A comparison of polynomial time reducibilities
- On log-tape isomorphisms of complete sets
- Relationships between nondeterministic and deterministic tape complexities
- Completeness for nondeterministic complexity classes
- Relativization of questions about log space computability
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- The complexity of theorem-proving procedures
- Recursively enumerable sets of positive integers and their decision problems