Rytter의 경계를 초월하다: $O(n^3(\log\log n)^2/(\log n)^2)$ 시간 복잡도로 모든 쌍의 CFL 도달 가능성을

요약

본 논문은 문맥 자유 도달 가능성(CFL reachability) 및 2NPDA 인식 문제에 대한 알고리즘 개선을 제시합니다. 기존의 최적 시간 복잡도($O(n^3/\log n)$)를 뛰어넘어, $O(n^3(\log\log n)^2/(\log n)^2)$의 시간을 달성하는 결정론적 알고리즘을 제안했습니다. 이 개선은 새로운 데이터 구조와 포화 상태 건너뛰기 기능을 활용합니다.

핵심 포인트

• CFL 도달 가능성과 2NPDA 인식 문제에 대한 알고리즘 개선 제시
• 새로운 시간 복잡도: $O(n^3(\log\log n)^2/(\log n)^2)$ 달성
• 공간 복잡도는 $O(n^{2+\varepsilon})$를 사용하며 결정론적임
• 개선은 교차 개수 유지 및 포화 상태 건너뛰기 기능에 기반함