Splittings, Robustness, and Structure of Complete Sets

DOI10.1137/S0097539795279724zbMath0906.03039OpenAlexW1978196595MaRDI QIDQ4388890

Albrecht Hoene, Leen Torenvliet, Harry Buhrman

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

complexitycompletenessreductionsmitoticity

Mathematics Subject Classification ID

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

Related Items

Robustness of PSPACE-complete sets ⋮ Autoreducibility and mitoticity of logspace-complete sets for NP and other classes ⋮ Autoreducibility, mitoticity, and immunity ⋮ The complexity of unions of disjoint sets ⋮ Non-mitotic Sets ⋮ Non-mitotic sets