A Post's program for complexity theory.

MaRDI QIDQ3396548zbMATH OpenFDO

Authors Harry Buhrman, Leen Torenvliet

Publication date 19 September 2009

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Separating Complexity Classes Using Autoreducibility
• scientific article; zbMATH DE number 90342
• scientific article; zbMATH DE number 1747699
• Redundancy in Complete Sets
• Post's program and incomplete recursively enumerable sets.

Cited in

(7)

• Splitting NP-complete sets infinitely
• Introduction to autoreducibility and mitoticity
• Autoreducibility of NP-complete sets under strong hypotheses
• Non-uniform reductions
• Autoreducibility, mitoticity, and immunity
• Robustness of PSPACE-complete sets
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets

This page was built for publication: A Post's program for complexity theory.

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