역색인덱스 순회의 P-완전성: 부울 쿼리 DAG 평가의 복잡성에 관하여

현대 AI 에이전트는 복잡한 신경-기호 추론 워크플로우를 실행하기 위해 검색 인프라에 크게 의존한다. 이러한 워크플로우는 텍스트 필드 위 깊은 중첩 구조의 비단조(non-monotonic) 부울 쿼리로 컴파일되지만, 기존 역색인덱스 평가 전략은 이론적 한계에 직면한다.

기존 문서 단위(DAT) 모델은 NC^1 공식 평가로 구조적으로 제한되어 재수렴 로직을 전개할 때 최악의 경우 O(2^|Q|) 지수적 폭발을 겪는다. 반면 단어 단위(TAT) 모델은 문서 유니버스에 대한 논리적 부정 평가 시 Ω(|U|) 공간 복잡도 페널티(유니버설 스캔)를 감수해야 한다.

본 연구는 역색인덱스 위에서 복잡한 로직을 네이티브로 실행하는 이론적 경계를 확립한다. DAG 기반 검색 언어(L_R)를 정형화하고 그 평가 문제가 엄밀히 **P-완전(P-Complete)**임을 증명했다. 이를 해결하기 위해 결정론적이고 희소성(sparse)을 고려한 평가 알고리즘 ComputePN을 도입했다.

ComputePN은 양-음(P-N) 이중 표현을 통해 논리적 부정을 유니버스 규모 물리화에서 분리하고, 네이티브 DAG 메모이제이션을 활용한다. 이를 통해 평가 시간을 O(|Q| · |U_active|)로 엄밀히 제한하여 조합적 트리 확장 병목과 유니버설 스캔 페널티를 모두 회피한다. 이는 계산적 검색(computational retrieval)의 형식적 기반을 마련한다.