JUCS - Journal of Universal Computer Science 4(8): 670-674, doi: 10.3217/jucs-004-08-0670
A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets
Lane A. Hemaspaandra‡,
Christopher Nasipak§,
Keith Parkins§‡ Department of Computer Science, University of Rochester, Rochester, NY, United States of America§ Department of Computer Science, University of Rochester, Rochester, NY 14627, United States of America
Corresponding author:
Lane Hemaspaandra
(
lane@cs.rochester.edu
)
© Lane Hemaspaandra, Christopher Nasipak, Keith Parkins. Citation:
Hemaspaandra LA, Nasipak C, Parkins K (1998) A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets. JUCS - Journal of Universal Computer Science 4(8): 670-674. https://doi.org/10.3217/jucs-004-08-0670 | ![Open Access](/i/open_access_icon_colour.svg) |
AbstractHemaspaandra and Torenvliet showed that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and quasi-linear nondeterminism. We show that each P-selective set can be accepted by a polynomial-time nondeterministic machine using linear advice and linear nondeterminism.
Keywordscomputational complexity, P-selectivity