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 of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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)

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

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)