On f-sparse sets in NP-P

DOI10.1007/3-540-63774-5_121MaRDI QIDQ4373559zbMATH OpenFDO

Authors Vladimír Glasnák

Publication date 20 September 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63774-5_121

zbMATH Keywords

hashing functionsstructural complexitytruth-table reducibility

Mathematics Subject Classification ID

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

Recommendations

• Sparse Sets in : Relativizations
• On reductions of NP sets to sparse sets
• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• scientific article; zbMATH DE number 3984573
• Sparse sets, approximable sets, and parallel queries to NP
• Sparse sets, approximable sets, and parallel queries to NP
• A note on sparse sets and the polynomial-time hierarchy
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• scientific article; zbMATH DE number 4081538

Cited in

(6)

• A note on sparse sets and the polynomial-time hierarchy
• Sparse sets and collapse of complexity classes
• There are no sparse NP\(_{w}\)-hard sets
• scientific article; zbMATH DE number 4068281 (Why is no real title available?)
• scientific article; zbMATH DE number 1332663 (Why is no real title available?)
• scientific article; zbMATH DE number 1834655 (Why is no real title available?)

This page was built for publication: On f-sparse sets in NP-P

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