기술적 요약: 백레퍼런스가 있는 정규식 매칭 문제의 복잡성

1. 문제 정의 및 동기

본 논문은 백레퍼런스가 있는 정규식 매칭 문제 (REWB) 의 세밀한 계산 복잡성을 조사한다. 고전적인 정규식 (Regex) 은 Thompson 구성을 사용하여 입력 문자열 길이 $|w|$에 대해 선형 시간 내에 매칭될 수 있지만, 실제 엔진은 백레퍼런스를 지원한다 (예: 서브스트링을 캡처하기 위한 (E)x와 이를 재사용하기 위한 \x). 이 기능은 정규식의 표현력을 엄격하게 확장하여 ($\{ww \mid w \in \Sigma^*\}$와 같은 비정규 언어를 인식할 수 있게 함) 하지만 상당한 알고리즘적 위험을 초래한다.

동기는 정규식 거부 서비스 (ReDoS) 공격에서 비롯된다. 여기서 적대자들은 매칭 엔진에서 최악의 경우 동작을 유발하도록 입력을 조작한다. Stack Overflow(2016) 와 Cloudflare(2019) 에서 발생한 주목할 만한 사건들은 백트래킹 기반 엔진에서 $O(|w|^2)$의 2 차 시간 동작조차 치명적인 서비스 중단을 초래할 수 있음을 보여주었다. 저자들은 다음과 같은 근본적인 질문을 제기한다: 선형 시간 또는 준선형 시간으로 실행되는 REWB 에 대한 ReDoS 안전 엔진을 구축할 수 있는가?

본 논문은 $k$개의 서로 다른 변수를 가지며, 모든 계산에서 백레퍼런스 실행의 총 횟수가 $r$로 제한되는 $r$-use $k$-REWB에 초점을 맞춘다.

2. 방법론 및 기술적 접근

본 논문은 조건부 하한 (hardness) 을 설정하고 특정 하위 클래스에 대한 효율적인 알고리즘을 설계하는 이중 접근법을 채택한다.

2.1 Hardness 결과

저자들은 잘 알려진 어려운 문제를 REWB 매칭으로 축소함으로써 이전의 복잡성 결과를 강화한다:

• W[2]-hardness: $k$-Dominating Set 문제를 축소함으로써, REWB 매칭이 표현식 크기 $|E|$로 매개변수화될 때 W[2]-hard 임을 증명한다. 이는 알려진 W[1]-hardness 결과를 강화한다.
• 조건부 하한 (Triangle Detection): Triangle Detection 에 대한 "거의 선형 시간 없음 가설 (No-Almost-Linear-Time Hypothesis)"을 가정할 때, 매우 제한된 2-use 2-REWB문제조차도 임의의 $\delta > 0$에 대해 $O(|w|^{1+\delta})$ 시간 내에 해결될 수 없음을 보인다.
• 조건부 하한 (k-OV): $k$-Orthogonal Vectors (k-OV) 가설 (SETH 보다 약함) 하에서, $k$-REWB 매칭은 $O(|w|^{2k-\epsilon})$ 시간 내에 해결될 수 없음을 증명한다. 이는 일반적인 $k$에 대해 준선형 시간은 불가능할 것임을 시사한다.

2.2 알고리즘적 결과

주요 알고리즘적 기여는 정확히 한 번 참조되는 하나의 변수를 가진 1-use REWB에 초점을 맞춘다.

• 정규형 변환: 저자들은 임의의 1-use REWB 가 $A, B, C, D$가 고전적인 정규식인 $A (B)_x C \backslash x D$와 같은 항들의 합으로 이루어진 정규형으로 변환될 수 있음을 증명한다. 이를 ABCBD 문제라고 한다.
• 분해 전략: ABCBD 문제는 두 개의 하위 문제로 분해된다:
  1. XYYZ 문제: $B$의 두 발생이 인접한 경우 ($w = w_A w_B w_B w_D$). 이는 Crochemore 의 최대 로컬 파워 열거와 전이 모노이드에서 유도된 **궁극적으로 주기적인 집합 (ultimately periodic sets)**의 속성을 사용하여 해결된다.
  2. 분기 ABCBD 문제: $B$의 두 발생이 비어 있지 않은 $C$에 의해 분리되고, 두 $B$ 발생 직후의 문자가 서로 다른 경우.
• 접미사 트리와 Heavy-Light 분해: 분기 경우에 대해 알고리즘은 입력 문자열 $w$의 접미사 트리를 활용한다. 검색 공간을 분할하기 위해 heavy-light 분해를 사용한다.
• 자료 구조:
  • Factorization Forests: 선형 전처리 후 상수 시간으로 부분 문자열에 대한 정규식 소속성을 평가하는 데 사용된다.
  • 전이 모노이드 (Transition Monoids): 정규식 $A, B, C, D$의 상태를 효율적으로 추적하는 데 활용된다.
  • 커스텀 열거기: 저자들은 전이 열거를 처리하기 위해 특수한 자료 구조 (RightEnumerator, LeftEnumerator, AuxiliaryEnumerator) 를 설계한다. 이러한 구조들은 부분 문자열 $w_B$의 길이에 따라 변하는 제약을 관리하기 위해 **지연 업데이트 (lazy updates)**와 불연속 집합 합집합 (DSU) 전략을 사용한다.

3. 주요 결과

Hardness

• 정리 3: REWB 매칭은 표현식 크기로 매개변수화될 때 W[2]-hard 이다.
• 정리 4: Triangle Detection 가정을 가정할 때, 2-use 2-REWB 매칭은 초선형 시간 (구체적으로 $O(|w|^{1+\delta})$이 아님) 을 요구한다.
• 정리 5: $k$-OV 가설 하에서, $k$-REWB 매칭은 $\Omega(|w|^{2k-\epsilon})$ 시간을 요구한다.

알고리즘

• 정리 7 (주요 결과): ABCBD 문제는 $O(|w| \log^2 |w|)$ 시간 알고리즘을 허용한다. 숨겨진 상수는 정규식 $A, B, C, D$의 크기에 지수적으로 의존한다 ($2^{O((|A|+|B|+|C|+|D|)^2)}$).
• 정리 8: 따라서 1-use REWB 매칭 문제는 $O(|w| \log^2 |w|)$ 시간 알고리즘을 허용한다.
• 정리 9: XY$\alpha$Z 문제 (XYYZ 를 $\alpha$ 반복으로 일반화) 은 $O(|w| \log |w|)$ 시간 알고리즘을 허용한다.

이러한 결과는 Nogami 와 Terauchi 가 MFCS 2025 에서 제시한 ABCBD 문제에 대한 이전 최선인 $O(|w|^2)$ 알고리즘보다 상당한 개선이다.

4. 중요성 및 주장

본 논문은 REWB 매칭의 복잡성 지형에 대한 근본적인 이해를 제공한다고 주장한다:

1. ReDoS 안전성: 일반적인 REWB 매칭은 준선형 시간에 대해 비실용적일 가능성이 높지만, 실용적으로 관련 있는 하위 클래스 (1-use REWB) 는 준선형 시간에 매칭될 수 있음을 확립한다. 이는 1-use 백레퍼런스를 지원하는 엔진이 이론적으로 ReDoS 안전하게 만들 수 있음을 시사한다.
2. 세밀한 복잡성: 본 연구는 처리 가능 사례와 처리 불가능 사례 사이의 경계를 규명한다. 백레퍼런스 사용 횟수를 1 에서 2 로 증가시키는 것 (변수가 2 개뿐인 경우라도) 은 문제를 준선형 영역 밖으로 밀어낼 가능성이 있음을 보여준다.
3. 알고리즘적 혁신: 본 논문은 이전에 2 차 시간이 필요하다고 생각되었던 문제를 해결하기 위해 접미사 트리, 인수 분해 숲, 전이 모노이드를 결합한 복잡하지만 매우 비자명한 알고리즘 프레임워크를 도입한다.

저자들은 명시적으로 그들의 알고리즘이 **균일 (uniform)**하다고 밝히는데, 이는 고정된 표현식에 의존하는 비균일 조언 없이 표현식과 입력 문자열을 함께 처리함을 의미한다. 그들은 표현식 크기 $|E|$에 대한 지수적 의존성이 매우 큰 표현식에 대한 제한으로 남아 있음을 인정하며, 진정한 선형 시간 알고리즘 ($O(|w|)$) 이 존재하는지 또는 로그 인자가 제거될 수 있는지에 대한 질문은 열린 채로 남겨둔다.

5. 한계 및 미해결 문제

본 논문은 여러 미해결 방향을 식별한다:

• $r$-use 1-REWB 의 복잡성: $r \ge 2$인 $r$-use 1-REWB 에 대한 복잡성은 여전히 미해결이다.
• 선형 시간: $O(|w| \log^2 |w|)$ 상한을 $O(|w|)$로 개선할 수 있는지 여부.
• 표현식 의존성: $|w|$에 대한 준선형 의존성을 유지하면서 $|E|$에 대한 지수적 의존성을 다항식으로 줄이는 것.
• 더 넓은 기능: lookarounds, 원자적 그룹화, 그리고 greedy/lazy 별표와 같은 다른 실용적인 정규식 기능으로 이러한 결과를 확장하는 것.