Splittings, Robustness, and Structure of Complete Sets

DOI10.1137/S0097539795279724MaRDI QIDQ4388890zbMATH OpenOpenAlexFDO

Authors Harry Buhrman, Albrecht Hoene, Leen Torenvliet

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539795279724

zbMATH Keywords

completenesscomplexitymitoticityreductions

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 512826
• Splitting NP-Complete Sets
• scientific article; zbMATH DE number 512798

Cited in

(9)

• Non-mitotic sets
• Robustness of PSPACE-complete sets
• Autoreducibility and mitoticity of logspace-complete sets for NP and other classes
• scientific article; zbMATH DE number 512826 (Why is no real title available?)
• A General Theory of Almost Splitting Sets
• Non-mitotic Sets
• Splitting NP-complete sets infinitely
• Autoreducibility, mitoticity, and immunity
• The complexity of unions of disjoint sets

This page was built for publication: Splittings, Robustness, and Structure of Complete Sets

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