A Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets
Дата
Авторы
Hemaspaandra,Lane
Nasipak,Christopher
Parkins,Keith
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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.
Ключевые слова
computational complexity , P-selectivity