On the topological size of p-m-complete degrees

DOI10.1016/0304-3975(94)00240-JMaRDI QIDQ672460zbMATH OpenOpenAlexFDO

Authors Marius Zimand

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(94)00240-j

zbMATH Keywords

NP-complete sets

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 782046
• Publication:4866587
• If not empty, NP-P is topologically large
• A note on complete problems for complexity classes

Cites work

• Almost every set in exponential time is P-bi-immune
• Category and Measure in Complexity Classes
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• If not empty, NP-P is topologically large
• On p-creative sets and p-completely creative sets
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Robust machines accept easy sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• The isomorphism conjecture fails relative to a random oracle

Cited in

(5)

• Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
• scientific article; zbMATH DE number 782046 (Why is no real title available?)
• scientific article; zbMATH DE number 850635 (Why is no real title available?)
• Effective category and measure in abstract complexity theory
• If not empty, NP-P is topologically large

This page was built for publication: On the topological size of p-m-complete degrees

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