Algebraic Properties for Deterministic and Nondeterministic Selectivity
Lane A. Hemaspaandra, Harald Hempel⋆, Arfst Nickelsen · 2002
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 and the best current lower bound is linear. .pp 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. .pp We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.