A note on sparse sets and the polynomial-time hierarchy (Q1263964): Difference between revisions

Sparse sets, i.e. sets with \(\leq n^ k\) elements of length n (for every n and fixed k) are known to play an important role in the development of structural complexity theory. In the short note reviewed the authors prove the following: for every \(k>0\) and every sparse \(S\in \Sigma^ P_ k\), \(\Sigma^ P_ k(S)\subseteq \Delta^ P_{k+1}\) so that \(\Delta^ P_{k+1}(S)=\Delta^ P_{k+1}\).