If not empty, NP-P is topologically large (Q688157): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q235567
Property / reviewed by
 
Property / reviewed by: Cristian S. Calude / rank
Normal rank
 

Revision as of 14:48, 11 February 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
    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

    Identifiers