If not empty, NP-P is topologically large

DOI10.1016/0304-3975(93)90161-LzbMath0781.68072OpenAlexW1969182601MaRDI QIDQ688157

Marius Zimand

Publication date: 17 February 1994

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

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90161-l

zbMATH Keywords

Cantor topologymeagre setpolynomial computationsuperset topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (3)

On the topological size of p-m-complete degrees ⋮ Effective category and measure in abstract complexity theory ⋮ Effective category and measure in abstract complexity theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on a theorem by Ladner
• A low and a high hierarchy within NP
• Independence results about context-free languages and lower bounds
• Theories of computational complexity
• Complexity of Presburger arithmetic with fixed quantifier dimension
• Immunity, Relativizations, and Nondeterminism
• Category and Measure in Complexity Classes
• Simplicity, Relativizations and Nondeterminism
• Bi-immune sets for complexity classes
• Alternation
• Topological Size of Sets of Partial Recursive Functions
• On the Structure of Polynomial Time Reducibility
• P-Printable Sets

This page was built for publication: If not empty, NP-P is topologically large