Algebraic Properties for Deterministic Selectivity
Lane A. Hemaspaandra, Harald Hempel⋆, Arfst Nickelsen · 2001
Karp and Lipton, in their seminal 1980 paper, introduced the notion of advice (nonuniform) complexity, which since has been of central importance in complexity theory. Nonetheless, much remains unknown about the optimal advice complexity of classes having polynomial advice complexity. In particular,