Linear-Nondeterminism Linear Advice for the P-Selective Sets
Lane A. Hemaspaandra, Christopher Nasipak, Keith Parkins · 1997
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 extend this by showing that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and linear nondeterminism. 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 likely than the other to be in the set.") Definition 1....