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

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.