Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets

DOI10.1016/j.tcs.2020.04.005zbMath1462.03017OpenAlexW3017238012MaRDI QIDQ5918833

Mahmoud Quweider, Fitra Khan, Hansheng Lei, Liyu Zhang

Publication date: 23 May 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.04.005

zbMATH Keywords

computational complexitybounded polynomial-time truth-table autoreducible setspolynomial-time autoreducibilityweak polynomial-time mitoticity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Unnamed Item
• Unnamed Item
• Computability and complexity theory.
• Autoreducibility, mitoticity, and immunity
• Non-mitotic sets
• Introduction to Autoreducibility and Mitoticity
• Splitting NP-Complete Sets
• Separating Complexity Classes Using Autoreducibility
• Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions
• The complexity theory companion