If not empty, NP-P is topologically large
type: Item
instance of: scholarly article
title: If not empty, NP-P is topologically large
zbMATH Open document ID: 0781.68072
DOI: 10.1016/0304-3975(93)90161-L
author: Marius Zimand
published in: Theoretical Computer Science
publication date: 1994-02-17T00:00:00Z
review text: One shows that in a combination of Cantor and supersets topologies the set \(NP\backslash P\), if not empty, is of second (Baire) category, while \(NP\)-complete sets are sets of first category. These results are extended to different levels in the polynomial hierarchy and to low/high hierarchies, \(P\)-immune sets in \(NP\), \(NP\)-simple sets, \(P\)-bi-immune sets and \(NP\)-effectively simple sets are all of second category, if not empty. Finally, one shows that if \(C\) is any of the above second category class, then for all \(B\in NP\) there exists an \(A\in C\) such that \(A\) is arbitrarily close to \(B\) infinitely often. All results are proven constructively.
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 440333
zbMATH Keywords: polynomial computation
zbMATH Keywords: Cantor topology
zbMATH Keywords: superset topology
zbMATH Keywords: meagre set
reviewed by: Cristian S. Calude
MaRDI profile type: Publication
cites work: P-Printable Sets
cites work: Q4723714
cites work: Simplicity, Relativizations and Nondeterminism
cites work: A note on a theorem by Ladner
cites work: Q4039803
cites work: Bi-immune sets for complexity classes
cites work: Topological Size of Sets of Partial Recursive Functions
cites work: Theories of computational complexity
cites work: Alternation
cites work: Q4431223
cites work: Independence results about context-free languages and lower bounds
cites work: Q3801071
cites work: On the Structure of Polynomial Time Reducibility
cites work: Category and Measure in Complexity Classes
cites work: Q5573961
cites work: Complexity of Presburger arithmetic with fixed quantifier dimension
cites work: A low and a high hierarchy within NP
cites work: Immunity, Relativizations, and Nondeterminism
cites work: Q4040892
full work available at URL: 0304-3975(93)90161-l
OpenAlex ID: W1969182601
description: scientific article; zbMATH DE number 440333