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

Простая страница элемента
dc.creatorHemaspaandra,Lane
dc.creatorNasipak,Christopher
dc.creatorParkins,Keith
dc.date1998
dc.date.accessioned2024-02-06T12:49:39Z
dc.date.available2024-02-06T12:49:39Z
dc.descriptionHemaspaandra 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.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-004-08-0670
dc.identifierhttps://lib.jucs.org/article/27507/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/7425
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 4(8): 670-674
dc.subjectcomputational complexity
dc.subjectP-selectivity
dc.titleA Note on Linear-Nondeterminism, Linear-Sized, Karp-Lipton Advice for the P-Selective Sets
dc.typeResearch Article
Файлы
Коллекции