Splitting NP-complete sets infinitely

DOI10.1016/J.IPL.2024.106472zbMATH Open1548.68093MaRDI QIDQ6551699

Fitra Khan, Mahmoud Quweider, Hansheng Lei, Liyu Zhang

Publication date: 7 June 2024

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

many-one reductionauto-reducible languagessplitting NP-complete languages

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Computability and complexity theory.
• Autoreducibility, mitoticity, and immunity
• Non-mitotic sets
• Introduction to Autoreducibility and Mitoticity
• Splitting NP-Complete Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Splittings, Robustness, and Structure of Complete Sets
• Separating Complexity Classes Using Autoreducibility
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• The complexity theory companion

This page was built for publication: Splitting NP-complete sets infinitely

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