Introduction to autoreducibility and mitoticity

DOI10.1007/978-3-319-50062-1_5MaRDI QIDQ2973718zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Alan L. Selman, Maximilian Witek, Dung T. Nguyen

Publication date 4 April 2017

Published in Computability and Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-50062-1_5

zbMATH Keywords

autoreducibilitycomputational complexitymitoticityrecursion theoryrecursively enumerable setsreducibilities

Mathematics Subject Classification ID

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

Recommendations

• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Redundancy in Complete Sets
• Non-mitotic Sets
• Non-mitotic sets

Cites work

• A Post's program for complexity theory.
• Autoreducibility of complete sets for log-space and polynomial-time reductions
• Autoreducibility, mitoticity, and immunity
• Complete Problems and Strong Polynomial Reducibilities
• Completely mitotic r. e. degrees
• Completeness for nondeterministic complexity classes
• Creative sets
• Degrees of Splittings and Bases of Recursively Enumerable Subspace
• Friedberg splittings of recursively enumerable sets
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• Minimal degrees for polynomial reducibilities
• Mitotic recursively enumerable sets
• On being incoherent without being very hard
• On the Universal Splitting Property
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Separating Complexity Classes Using Autoreducibility
• Splitting NP-Complete Sets
• Splitting properties of r.e. sets and degrees
• Splitting theorems and the jump operator
• Splitting theorems in recursion theory
• The Degrees of R.E. Sets Without the Universal Splitting Property

Cited in

(11)

• Non-mitotic sets
• Completely mitotic r. e. degrees
• Space-efficient informational redundancy
• Some observations on mitotic sets
• scientific article; zbMATH DE number 3869312 (Why is no real title available?)
• Anti‐Mitotic Recursively Enumerable Sets
• scientific article; zbMATH DE number 3954888 (Why is no real title available?)
• Mitotic Classes
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Polynomial-time axioms of choice and polynomial-time cardinality
• Splitting NP-complete sets infinitely

This page was built for publication: Introduction to autoreducibility and mitoticity

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