Complete sets and structure in subrecursive classes

MaRDI QIDQ4218523zbMATH OpenFDO

Authors Harry Buhrman, Leen Torenvliet

Publication date 10 October 1999

zbMATH Keywords

class structureclasses of languagescomplete setscomplexity classesoracle Turing machinespolynomial timereductionsset structure

Mathematics Subject Classification ID

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

Review text

In this expository paper the authors study the structure of complete sets in several complexity classes. The main complexity classes considered in the paper are the classes of languages recognized by: deterministic and nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, deterministic polynomial space, deterministic and nondeterministic linear exponential time, deterministic exponential time, and nondeterministic exponential time bounded Turing machines, respectively. The authors give an overview of recent results on both set structure and class structure induced by various notions of reductions. For the entire collection see [Zbl 0893.00029].

Recommendations

• Structural properties of complete problems for exponential time
• On existence of complete sets for bounded reducibilities
• A note on complete problems for complexity classes
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes

Cited in

(9)

• Classes bounded by incomplete sets
• On regular set systems containing regular subsystems
• Axiomatizing resource bounds for measure
• scientific article; zbMATH DE number 540524 (Why is no real title available?)
• Structural properties of complete problems for exponential time
• The subset relation and 2‐stratified sentences in set theory and class theory
• Observations on complete sets between linear time and polynomial time
• Comparing reductions to NP-complete sets
• Autoreducibility, mitoticity, and immunity

This page was built for publication: Complete sets and structure in subrecursive classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218523)