If not empty, NP-P is topologically large

DOI10.1016/0304-3975(93)90161-LzbMATH Open0781.68072OpenAlexW1969182601MaRDI QIDQ688157FDOQ688157

Authors: 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

Recommendations

• On the topological size of p-m-complete degrees
• scientific article; zbMATH DE number 782046
• Separating NP-completeness notions under strong hypotheses
• Publication:4866587
• scientific article; zbMATH DE number 4002078

zbMATH Keywords

Cantor topologymeagre setpolynomial computationsuperset topology

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

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

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Effective category and measure in abstract complexity theory
• On the topological size of p-m-complete degrees
• Effective category and measure in abstract complexity theory

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

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