LOGCFL - LOGCFL

В теории сложности вычислений , LOGCFL является классом сложности , который содержит все проблемы , решение , которые могут быть сокращены в логарифмическом пространстве к контекстно-свободному языку . Этот класс расположен между NL и AC ¹ в том смысле, что он содержит первый и содержится во втором. Проблемы, которые являются полными для LOGCFL, включают множество задач, экземпляры которых могут быть охарактеризованы ациклическими гиперграфами :

• оценка ациклических логических конъюнктивных запросов
• проверка существования гомоморфизма между двумя ациклическими реляционными структурами
• проверка существования решений ациклических задач удовлетворения ограничений

Смотрите также

• Список классов сложности

внешние ссылки

• Зоопарк сложности : LOGCFL