The relative power of logspace and polynomial time reductions

DOI10.1007/BF01271369zbMath0801.68063OpenAlexW1963695130MaRDI QIDQ1312179

Leen Torenvliet, Harry Buhrman, Edith Hemaspaandra

Publication date: 19 January 1994

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01271369

zbMATH Keywords

circuitsreductionspolynomial timebranching programscomplexity classeslogspacetruth-table

Mathematics Subject Classification ID

Related Items (2)

Non-uniform reductions ⋮ Planar and grid graph reachability problems

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

This page was built for publication: The relative power of logspace and polynomial time reductions