A Post's program for complexity theory.

zbMATH Open1169.68426MaRDI QIDQ3396548FDOQ3396548

Authors: Harry Buhrman, Leen Torenvliet 

Publication date: 19 September 2009

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.

Mathematics Subject Classification ID

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

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)