Computer Science – Computational Complexity
Scientific paper
2005-01-11
SICOMP, V. 33, Number 6, pp. 1309--1337, 2004
Computer Science
Computational Complexity
More recent version of most of this report appears in SICOMP, but the appendix here is not included there
Scientific paper
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.
Hemaspaandra Lane A.
Hempel Harald
Nickelsen Arfst
No associations
LandOfFree
Algebraic Properties for Selector Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algebraic Properties for Selector Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algebraic Properties for Selector Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-179546