On the topological size of p-m-complete degrees

DOI10.1016/0304-3975(94)00240-JzbMath0873.68066OpenAlexW2049599272MaRDI QIDQ672460

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)

Related Items (1)

Effective category and measure in abstract complexity theory

Cites Work

• Unnamed Item
• If not empty, NP-P is topologically large
• Robust machines accept easy sets
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• On p-creative sets and p-completely creative sets
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Category and Measure in Complexity Classes
• The isomorphism conjecture fails relative to a random oracle
• Almost every set in exponential time is P-bi-immune

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