The shrinking property for NP and coNP (Q627189)

A class \(C\) is said to have the shrinking property if for all \(A, B \in C\) there exist disjoint \(A', B'\!\in C\) with \(A'\!\subseteq A\), \(B'\!\subseteq B\) and \(A\cup B = A' \cup B'\). The authors prove that NP and coNP do not have the shrinking property unless the polynomial hierarchy is finite. This solves an open question of the third author. After further results on the shrinking and separation properties, they prove that the assumption \(\text{NP}\neq \text{coNP}\) is too weak to refute the shrinking property for NP in a relativisable way. The proof works by constructing an oracle. Its explicit existence solves an open question by \textit{A. Blass} and \textit{Y. Gurevich} [SIAM J. Comput. 13, 682--689 (1984; Zbl 0545.68035)].