On Sparse Complete Sets

DOI10.1002/MALQ.19850311411MaRDI QIDQ3346297zbMATH OpenOpenAlexFDO

Authors Gerd Wechsung

Publication date 1985

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19850311411

zbMATH Keywords

sparsityNP-completenessreducibilityNPcoNPrandom polynomial time class

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• scientific article; zbMATH DE number 4080915
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• scientific article; zbMATH DE number 1318517

Cited in

(13)

• Sparse sets in NP-P: EXPTIME versus NEXPTIME
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
• scientific article; zbMATH DE number 3984573 (Why is no real title available?)
• Sparse NP-complete problems over the reals with addition
• Sparse selfreducible sets and nonuniform lower bounds
• scientific article; zbMATH DE number 1072529 (Why is no real title available?)
• Highly sparse sets as additive complements for a prescribed density
• Highly spare sets as additive complements for a prescribed density: an open problem
• scientific article; zbMATH DE number 4106271 (Why is no real title available?)
• Some consequences of non-uniform conditions on uniform classes
• Existence of some sparse sets of nonstandard natural numbers
• scientific article; zbMATH DE number 4106273 (Why is no real title available?)
• scientific article; zbMATH DE number 5363789 (Why is no real title available?)

This page was built for publication: On Sparse Complete Sets

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