On the structure of \(\Delta_ 2\!^ p\) (Q789386)

The paper gives some structural results on the class \(\Delta_ 2\!^ p\) of the polynomial hierarchy which hold if \(NP=co\)-NP. If so, then there exist sets in \(\Delta_ 2\!^ p\) that are neither NP-hard, nor in NP, nor in co-NP. Moreover, in this case it is undecidable whether a given set in \(\Delta_ 2\!^ p\) is in P, in NP, or NP-hard. The result can be generalized to all classes \(\Delta_ k\!^ p\) and is proved using a theorem published previously by the same author.