Algebraic Properties for Selector Functions

Simple item page
dc.creatorHemaspaandra, Lane A.
dc.creatorHempel, Harald
dc.creatorNickelsen, Arfst
dc.date2005-01-11
dc.date.accessioned2026-07-07T03:22:21Z
dc.date.available2026-07-07T03:22:21Z
dc.descriptionThe 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.
dc.descriptionMore recent version of most of this report appears in SICOMP, but the appendix here is not included there
dc.identifierhttps://arxiv.org/abs/cs/0501022
dc.identifierhttp://arxiv.org/abs/cs/0501022
dc.identifierSICOMP, V. 33, Number 6, pp. 1309--1337, 2004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32561
dc.subjectComputational Complexity
dc.subjectF.1.3; F.1.2; F.1.1
dc.titleAlgebraic Properties for Selector Functions
dc.typetext

Files

Collections

arXiv