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
expand article infoLane 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.
This article is freely available under the J.UCS Open Content License.
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
Abstract
Hemaspaandra 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.
Keywords
computational complexity, P-selectivity