Algebraic Properties for Selector Functions
<|reference_start|>Algebraic Properties for Selector Functions: The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets--i.e., the amount of Karp--Lipton advice needed for polynomial-time machines to recognize them in general--the best current upper bound is quadratic [Ko, 1983] and the best current lower bound is linear [Hemaspaandra and Torenvliet, 1996].   We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound (which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P=NP.   We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.<|reference_end|>
@article{hemaspaandra2005algebraic,
    title={Algebraic Properties for Selector Functions},
    author={Lane A. Hemaspaandra, Harald Hempel, and Arfst Nickelsen},
    journal={SICOMP, V. 33, Number 6, pp. 1309--1337, 2004},
    year={2005},
    number={URCS-TR-778 (January 7, 2004 revision)},
    archivePrefix={arXiv},
    eprint={cs/0501022},
    primaryClass={cs.CC}
}