ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
Abstract
Informally put, the semifeasible sets are the class of sets having a polynomial-time algorithm that, given as input any two strings of which at least one belongs to the set, will choose one that does belong to the set. We provide a tutorial overview of the advice complexity of the semifeasible sets. No previous familiarity with either the semifeasible sets or advice complexity will be assumed, and when we include proofs we will try to make the material as accessible as possible via providing intuitive, informal presentations.
Karp and Lipton introduced advice complexity about a quarter of a century ago.18 Advice complexity asks, for a given power of interpreter, how many bits of "help" suffice to accept a given set. Thus, this is a notion that contains aspects both of descriptional/informational complexity and of computational complexity. We will see that for some powers of interpreter the (worst-case) complexity of the semifeasible sets is known right down to the bit (and beyond), but that for the most central power of interpreter—deterministic polynomial time—the complexity is currently known only to be at least linear and at most quadratic.
While overviewing the advice complexity of the semifeasible sets, we will stress also the issue of whether the functions at the core of semifeasibility—so-called selector functions—can without cost be chosen to possess such algebraic properties as commutativity and associativity. We will see that this is relevant, in ways both potential and actual, to the study of the advice complexity of the semifeasible sets.
Supported in part by grant NSF-CCF-0426761. Based on an invited presentation at the 6th Workshop on Descriptional Complexity of Formal Systems (2004).
