A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets.
Lane A. Hemaspaandra, Christopher Nasipak, Keith Parkins · 1998
: Hemaspaandra and Torenvliet showed that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and quasilinear nondeterminism. We show that each P-selective set can be accepted by a polynomial -time nondeterministic machine using linear advice and linear nondeterminism. Key Words: computational complexity, P-selectivity Category: F.1 1 Introduction The P-selective sets, sometimes referred to as the semi-feasible sets, were introduced by Selman [Sel79] as polynomial-time analogs of the semi-recursive sets of recursive function theory. They have played an active role in many facets of complexity theory (see [HNOS96b] and the survey [DHHT94] for references and discussion). By definition, the P-selective sets are those sets that have a polynomial-time function that chooses one of any two given strings, and that never chooses one that is out of the set if the other is in the set. (Informally, the function chooses one that is "no less lik...