LOGCFL

계산 복잡성 이론에서 LOGCFL은 로그 공간에서 문맥이 없는 언어로 줄일 수 있는 모든 의사결정 문제를 포함하는 복잡성 등급이다.이 세분류는 전자를 포함하고 후자에 포함된다는 의미에서 NL과 AC¹ 사이에 위치한다.LOGCFL에 대해 완료된 문제에는 많은 문제가 포함되며, 이러한 문제들은 반복적인 하이퍼그래프로 특징지어질 수 있다.

• 주기적 부울 결막 쿼리 평가
• 두 개의 순환 관계 구조 사이에 동형성이 존재하는지 확인
• 반복적인 제약 만족도 문제의 해결책 존재 여부 확인

참고 항목

• 복잡도 클래스 목록

외부 링크

• 복잡성 동물원: LOGCFL