Properties of NP‐Complete Sets

DOI10.1137/S009753970444421XMaRDI QIDQ3434997zbMATH OpenOpenAlexFDO

Authors Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta

Publication date 3 May 2007

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

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

zbMATH Keywords

disjoint unionsimmunityNP-completenessone-way permutationsrobustness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• Mathematical Foundations of Computer Science 2005
• Bi-immunity separates strong NP-completeness notions
• scientific article; zbMATH DE number 2086403

Cited in

(7)

• Immunity of complete problems
• Bi-immunity separates strong NP-completeness notions
• Robustness of PSPACE-complete sets
• scientific article; zbMATH DE number 4047100 (Why is no real title available?)
• NP-Creative sets: A new class of creative sets in NP
• Unions of disjoint NP-complete sets
• Autoreducibility, mitoticity, and immunity

This page was built for publication: Properties of NP‐Complete Sets

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