Optimal advice
Lane A. Hemaspaandra, Leen Torenvliet · Theoretical Computer Science · 1996
Ko proved that the P-selective sets are in the advice class P/quadratic, and Hemaspaandra, Naik, Ogihara, and Selman showed that they are in PP/linear. We strengthen the latter result by establishing that the P-selective sets are in NP/linear ∩ coNP/linear. We show linear advice to be optimal.