A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets

Lane A. Hemaspaandra (Department of Computer Science, University of Rochester, USA)

Christopher Nasipak (Department of Computer Science, University of Rochester, USA)

Keith Parkins (Department of Computer Science, University of Rochester, USA)

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: P-selectivity, computational complexity

Categories: F.1