ЛОГКФЛ
В сложности вычислений теории LOGCFL — это класс сложности , который содержит все проблемы принятия решений , которые можно свести в логарифмическом пространстве к контекстно-свободному языку . [1] Этот класс закрыт по дополнению. [1] Он расположен между NL и AC. 1 , в том смысле, что он содержит первый [1] и содержится в последнем. [2] Задачи, полные для LOGCFL, включают множество задач, которые можно охарактеризовать ациклическими гиперграфами :
- оценка ациклических логических конъюнктивных запросов [3]
- проверка существования гомоморфизма между двумя ациклическими реляционными структурами [4]
- проверка существования решений ациклических задач удовлетворения ограничений [3]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с Хемаспаандра, Лейн А.; Огихара, Мицунори (2002), «Спутник теории сложности» , Тексты по теоретической информатике: серия EATCS, Springer, стр. 280, номер домена : 10.1007/978-3-662-04880-1 , ISBN 9783662048801
- ^ Капрон, Брюс М., изд. (2023), Логика, автоматы и вычислительная сложность: работы Стивена А. Кука , ACM Books, Morgan & Claypool, стр. 124, ISBN 9798400707803
- ^ Jump up to: а б Готтлоб, Георг; Леоне, Никола; Скарчелло, Франческо (2001), «Сложность ациклических конъюнктивных запросов», Журнал ACM , 48 (3): 431–498, doi : 10.1145/382780.382783
- ^ Вортмайер, Нильс; Коккинис, Иоаннис (2021), «Динамическая сложность гомоморфизмов ациклических гиперграфов», у Ковалика, Лукаша; Пилипчук, Михал; Рзажевский, Павел (ред.), Теоретико-графовые концепции в информатике - 47-й международный семинар, WG 2021, Варшава, Польша, 23–25 июня 2021 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 12911, Springer, стр. 232–244, arXiv : 2107.06121 , doi : 10.1007/978-3-030-86838-3_18 , ISBN 978-3-030-86837-6