If not empty, NP-P is topologically large (Q688157): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(93)90161-l / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1969182601 / rank | |||
Normal rank |
Latest revision as of 09:07, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | If not empty, NP-P is topologically large |
scientific article |
Statements
If not empty, NP-P is topologically large (English)
0 references
17 February 1994
0 references
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.
0 references
polynomial computation
0 references
Cantor topology
0 references
superset topology
0 references
meagre set
0 references