Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

DOI10.1007/978-3-642-39206-1_40zbMath1336.68089OpenAlexW2283269415MaRDI QIDQ5326584

Maximilian Witek, Selman, Alan L., Christian Reitwießner, Christian Glaßer, Dung Tien Nguyen

Publication date: 6 August 2013

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-39206-1_40

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets

This page was built for publication: Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions