추론의 복잡도: 프로파일이 존재하는 이유

📍 현재 위치: 2부 · 서술 논리 — 7장. OWL 2 프로파일은 표준 온톨로지 언어를 EL, QL, RL 하위 언어로 분류했습니다; 이 장은 그 분류 뒤에 있는 힘 — 모든 프로파일이 그 위의 의도적으로 선택한 하나의 지점인 표현력 대 비용의 단일 곡선 — 을 설명합니다.

이전 장에서 다룬 세 프로파일은 마케팅 등급이 아닙니다. 각각은 언어가 말할 수 있는 것과 그 언어로 추론하는 데 드는 비용을 맞바꾸는 하나의 곡선 위, 정확한 지점에 놓이도록 설계되었습니다. 이 장은 그 곡선을 그리고, 그 위의 이정표들에 이름을 붙이며, 학계 세계 자신의 완성 실행 위에서 "저렴함"이 실제로 눈앞에서 펼쳐질 때 어떤 모습인지 보여줍니다.

쉽게 말하면

카메라를 사는 상황을 상상해 보십시오. 폰 카메라는 즉각적이고 주머니에 쏙 들어가지만, 모든 것을 담아낼 수는 없습니다. 완전한 스튜디오 장비는 무엇이든 촬영할 수 있지만, 무겁고 느리며 전문가가 다뤄야 합니다. 서술 논리도 같은 방식으로 작동합니다. 작고 빠른 언어는 모든 질문에 눈 깜짝할 사이에 답하지만 표현할 수 있는 범위는 그만큼 제한적입니다. 최대로 표현력이 풍부한 언어는 거의 모든 상황을 기술할 수 있지만, 단 하나의 질문에 답하는 데 우주의 나이보다 더 오랜 시간이 걸릴 수도 있으며 — 가장 완전한 언어는 아예 답하지 못할 수도 있습니다. OWL 2 프로파일은 바로 이 카메라 라인업입니다: 각각은 얼마만큼의 표현력을 보장된 빠른 응답과 맞바꿀 것인지를 놓고 선택한 하나의 타협안입니다.

이 장에서 다루는 내용

복잡도 속성 강의 — "결정 가능(decidable)", "PTIME", "ExpTime", "결정 불가능(undecidable)"이 무엇을 의미하는지, 복잡도 이론에 대한 사전 지식을 전혀 가정하지 않고 각각 평이한 한 문단으로 설명합니다.
트레이드오프 논제 — 부정, 논리합, 개수 제한(cardinality) 등 구성자를 하나씩 추가할 때마다 표현력을 얻는 대신 최악의 경우 시간이 대가로 따라붙습니다; 표 하나로 여러 DL과 OWL 방언들을 비용 곡선 위에 배치합니다.
EL이 다항식적으로 유지되는 이유 — 그 완성 알고리즘은 어휘 크기의 제곱을 결코 넘어설 수 없는 사실 집합 위에서 단조 고정점(monotone fixpoint)을 반복합니다; 학계 세계에서 그것이 3라운드 만에 안정되는 과정을 지켜봅니다.
표현력이 풍부한 논리가 폭발하는 이유 — 논리합과 부정은 경우 분할을 강제하여, 다항식적인 사실 추가를 지수적으로 분기하는 탐색으로 바꿔 놓습니다.
결정 불가능성의 벽 — 완전한 1차 논리는 결코 멈추지 않는 계산을 인코딩할 수 있으므로, 어떤 알고리즘도 항상 답할 수는 없습니다.
결합 복잡도 대 데이터 복잡도 — EL이 TBox를 더 빠르게 분류함에도 불구하고, 거대한 ABox를 질의하는 데는 왜 QL이 알맞은 프로파일인지 설명합니다.

복잡도 속성 강의: 알아야 할 네 단어

추론은 옳은 답과 함께 종료되거나 그렇지 않으며, 종료된다면 그것은 실행할 만큼 충분히 빠르거나 그렇지 않습니다. 네 개의 단어가 이 경우들을 정확히 짚어 줍니다; 아래에서 각각을 처음부터 설명합니다.

결정 가능(Decidable). 예/아니오 문제는, 모든 가능한 입력에 대해 반드시 멈추고 올바른 답을 반환하는 단일 알고리즘이 존재할 때 결정 가능(decidable)합니다. "이 TBox에서 $A \sqsubseteq B$ 가 함의되는가?"는 우리가 다루는 모든 서술 논리에서 결정 가능합니다: 언제나 끝나고 결코 거짓말을 하지 않는 절차를 작성할 수 있습니다. 결정 가능성은 속도에 대해서는 아무것도 말해 주지 않습니다 — 오직 기계가 항상 멈춘다는 것만을 말해 줍니다.

PTIME(다항 시간). 어떤 알고리즘이 밟는 단계 수가 입력 크기 $n$ 에 대한 다항식 — $n$ , $n^2$ , $n^3$ 과 같은 것이지, $n$ 이 지수 자리에 나타나는 일은 결코 없는 — 으로 한정될 때 그 알고리즘은 다항 시간(polynomial time)으로 실행됩니다. 이것이 바로 다루기 쉬움(tractable)의 실질적 의미입니다: 입력을 두 배로 늘리면 실행 시간은 고정된 배수만큼 늘어날 뿐, 전체 작업량이 제곱이 되지는 않습니다. $\mathrm{PTIME}$ 에 속한 문제는 실제 데이터 규모로 확장됩니다.

ExpTime(지수 시간). 어떤 알고리즘의 단계 수가 어떤 다항식 $p$ 에 대해 $2^{p(n)}$ 으로 한정될 때 그 알고리즘은 지수 시간(exponential time)으로 실행됩니다. 이제 입력에 기호 하나를 추가하는 것만으로도 작업량이 두 배가 될 수 있습니다. 지수 함수는 거의 곧바로 벽에 부딪힙니다 — $n = 40$ 일 때 이미 그 수는 수조 단위에 이릅니다. N2ExpTime("비결정적 이중 지수 시간(nondeterministic doubly exponential time)")은 그보다도 더 나쁘며, 대략 $2^{2^{p(n)}}$ 입니다: 이미 지수적인 수를 다시 지수로 올리는 것입니다. 어떤 문제가 $\mathrm{ExpTime}$ -완전(complete)하다고 불릴 때, 이는 단순한 상한이 아닙니다 — 그 문제가 그 클래스 안의 그 무엇 못지않게 어렵다는 것이 증명 가능하다는 뜻이며, 따라서 아무리 영리한 알고리즘도 최악의 경우 그 벽을 벗어날 수 없습니다 [1].

결정 불가능(Undecidable). 어떤 문제를 모든 입력에 대해 결정하는 알고리즘이 전혀 없다면 — 느린 것 하나조차, 어떤 것도 없다면 — 그 문제는 결정 불가능(undecidable)합니다. 때로는 답이 "예"일 때는 언제나 올바르게 "예"라고 답하지만 답이 "아니오"일 때는 영원히 멈추지 않을 수도 있는 준결정기(semi-decider)를 만들 수는 있습니다. 완전한 1차 논리(first-order logic)에서의 함의(entailment)가 대표적인 예입니다: 항상 옳은 판정과 함께 멈추는 기계는 존재하지 않습니다.

트레이드오프: 모든 구성자에는 대가가 있다

이 장의 논제를 한 줄로 요약하면 이렇습니다. 표현력과 복잡도는 서로 맞바꿔지는 관계에 있습니다. 어떤 논리가 허용하는 개념 구성자(concept constructor) — 논리곱(conjunction) ⊓, 존재 제한(existential restriction) ∃, 논리합(disjunction) ⊔, 부정(negation) ¬, 개수 제한(number restriction), 역할의 역(inverse role), 노미널(nominal) — 하나하나는 더 많이 말할 수 있게 해 주며, 동시에 추론기에게 더 많은 분기(branch) 방법을 주는데, 이는 최악의 경우 시간으로 드러납니다. 우리 동반 코드가 구현하는 EL 계열은 ⊓와 ∃만을 유지하며(EL++에서는 여기에 ⊥, 역할 사슬(role chain), ABox가 더해집니다), 바로 이 검소함 덕분에 그 포섭 문제가 $\mathrm{PTIME}$ 안에 머무릅니다 [2]. 빠져 있던 구성자들을 다시 하나씩 쌓아 올리면 비용은 다항식에서 지수, 이중 지수를 거쳐 결정 불가능성의 절벽에 이르기까지 단계마다 치솟습니다.

논리 / OWL 2 프로파일	추가하는 구성자	포섭 (일반 TBox 기준)
EL, EL++ / OWL 2 EL	⊓, ∃, ⊥, 역할 사슬	$\mathrm{PTIME}$ -완전
DL-Lite / OWL 2 QL	제한된 ∃, 역할의 역	TBox 상에서는 다루기 쉬움; 질의 응답은 1차 재작성 가능(first-order rewritable)
OWL 2 RL	혼(Horn) 형태의 규칙 공리	$\mathrm{PTIME}$ -완전 (인스턴스 검사, instance checking)
ALC	¬, ⊔, ∀	$\mathrm{ExpTime}$ -완전
SHIQ	+ 전이적 역할(transitive role), 역할 위계(role hierarchy), 역(inverse), 개수 제한	$\mathrm{ExpTime}$ -완전
SROIQ / OWL 2 DL	+ 노미널, 복합 역할 포함(complex role inclusion)	$\mathrm{N2ExpTime}$ -완전
1차 논리	완전한 한정, 임의의 술어	결정 불가능

EL에서 ALC로의 도약은 단 하나의 아이디어 — ¬와 ⊔를 쓸 수 있는 능력 — 의 값이며, 이는 곧 $\mathrm{PTIME}$ 과 $\mathrm{ExpTime}$ 의 차이입니다 [3]. 이 표 전체를 하나의 계단으로 읽으십시오: 프로파일들은 모델러가 자신에게 필요한 보장 수준에 맞는 계단을 선택할 수 있도록 정확히 이렇게 깎여 나온 것입니다.

OWL 2 프로파일들이 그 위의 선택된 지점들인 표현력 대 비용 곡선: 원점 근처의 다항식적 EL, SROIQ에서의 이중 지수 벽, 그리고 완전한 1차 논리가 지도 밖으로 벗어나는 결정 가능성의 절벽. 저자가 AI의 도움을 받아 직접 제작한 원본 도해.

EL이 다항식적으로 유지되는 이유: 폭발할 수 없는 고정점

el_completion.py에 있는 EL 추론기는 1권의 전방 연쇄(forward-chaining) 엔진과 같은 모양을 하고 있습니다 — 단조 고정점(monotone fixpoint)입니다: 사실들의 집합을 씨앗으로 심고, 오직 사실을 추가하기만 하는 고정된 규칙 집합을 발동시키며, 전체 순회가 아무것도 추가하지 못하면 멈춥니다. 여기서 사실이란 포섭(subsumption) 관계입니다. 이 알고리즘은 두 개의 표를 유지합니다(독스트링, el_completion.py 20–21번째 줄): $A$ 가 그것에 의해 포섭된다고 알려진 개념 이름들의 집합인 $S(A)$ , 그리고 $A$ 가 $\exists r.B$ 를 만족한다고 알려진 쌍 $(A, B)$ 의 집합인 $R(r)$ 입니다. 완성 규칙(completion rule) CR1–CR4와 바닥 규칙(bottom rule), 역할 사슬 규칙이 고정점에 도달할 때까지 이 표들을 포화시킵니다(complete, 177–261번째 줄).

다항식적 보장 전체는 단 하나의 한계로부터 나옵니다. $N$ 을 개념 이름의 개수라 합시다. 그러면 $S(A)$ 는 이름들의 부분집합이므로 $|S(A)| \le N$ 이고, $R(r)$ 은 이름 쌍들의 부분집합이므로 $|R(r)| \le N^2$ 입니다. 어휘 전체에 대해 합하면,

|S| \;=\; \sum_{A} |S(A)| \;\le\; N^2, \qquad |R| \;=\; \sum_{r} |R(r)| \;\le\; |\text{roles}| \cdot N^2 .

완성 규칙은 결코 아무것도 삭제하지 않으므로, 각 라운드는 최소한 하나의 새로운 사실을 추가하거나 루프가 종료되며, 따라서 라운드의 수는 있을 수 있는 사실의 총 개수 — 많아야 $N^2 + |\text{roles}| \cdot N^2$ , 즉 다항식 — 로 한정됩니다. 각 라운드는 다항식 양의 스캔을 수행합니다. 다항식 비용의 라운드가 다항식 번 반복되어도 여전히 다항식이므로, EL에서의 포섭은 $\mathrm{PTIME}$ 안에 있습니다 — EL++에 대해 건전하고(sound) 완전하며(complete), 수십만 개의 개념을 지녀서 어떤 지수적 논리에서도 가망이 없을 SNOMED CT와 Gene Ontology를 분류하기에도 충분히 빠릅니다(독스트링, 38–40번째 줄) [2].

단조적이고 분기 없는 핵심부는 단 열 줄뿐입니다 — 모든 규칙이 $S$ 에 추가하고 changed를 뒤집을 뿐, 그 무엇도 철회되지 않으므로 대가를 치러야 할 역추적(backtracking)이 없다는 점에 주목하십시오(el_completion.py 210–219번째 줄):

    rounds = [sizes()]
    changed = True
    while changed:
        changed = False

        # CR1: A' ∈ S(A), A' ⊑ B  ⟹  B ∈ S(A)
        for _, a_prime, b in nf1:
            for A in names:
                if a_prime in S[A] and b not in S[A]:
                    S[A].add(b); changed = True

모듈을 실행하면 다항식적 거동이 하나의 출력물로 나타납니다. 기록을 담당하는 함수 sizes(205–208번째 줄)는 매 순회 후 $|S|$ 와 $|R|$ 을 기록하며, 그 트레이스는 상승이 상한에 도달해 멈추는 모습을 보여줍니다:

normalization: 14 axioms → 16 normal-form axioms, introducing 2 fresh names ['_N1', '_N2']
  by normal form: {'chain': 1, 'nf1': 6, 'nf2': 2, 'nf3': 3, 'nf4': 4}

saturation reached a fixpoint in 3 rounds
  round : |S| |R|  (derived subsumers, derived role pairs)
      0 :  23   0
      1 :  34   7
      2 :  39   7
      3 :  39   7

가운데 열을 단조적으로 커지는 사실 집합으로 읽으십시오: 규칙은 오직 추가만 하므로, 각 라운드의 집합 $S$ 는 이전 라운드의 것을 포함합니다, $S_0 \subseteq S_1 \subseteq S_2 \subseteq S_3$ , 그래서 그 개수는 오직 늘어날 수만 있습니다, $|S| = 23 \le 34 \le 39 \le 39$ . 학계 세계에는 개념 이름이 겨우 열두 개뿐입니다 — 공리에 등장하는 여덟 개의 선언된 이름, 정규화(normalization)가 도입하는 두 개의 새로운 이름, 그리고 ⊤와 ⊥입니다(_concept_names, 160–174번째 줄). 각 이름은 처음에 자기 자신과 ⊤에 의해 포섭된다는 것만을 압니다(S = {a: {a, TOP} ...}, 187번째 줄), 그래서 트레이스는 정확히 $|S| = 23 = 2 \times 12 - 1$ 에서 시작합니다(⊤는 두 번째 항목이 필요 없습니다). 이론적 상한은 $N^2 = 144$ 개의 포섭자(subsumer)이며, 고정점은 그보다 한참 아래인 $39$ 에서, 3라운드 만에 안착합니다. 마지막 라운드인 $39 \to 39$ 와 $7 \to 7$ 은 엔진이 스스로 끝났음을 증명하는 순간입니다 — changed 플래그가 거짓으로 남고 루프가 멈춥니다. 열네 개의 공리에 3라운드가 걸린 것은 마법의 상수가 아닙니다; 이는 그 보장의 형태 그 자체입니다 — 사실의 개수는 오직 늘어날 수만 있으며, 다항식적 상한을 결코 넘어설 수 없습니다.

표현력이 풍부한 논리가 폭발하는 이유: 논리합은 추측하게 만든다

EL의 완성은 결코 분기하지 않는데, EL에는 분기할 대상 자체가 없기 때문입니다. EL의 구성자인 ⊓와 ∃는 결정적(deterministic)입니다: 어떤 개념이 $C \sqcap D$ 라면, 그것은 $C$ 이면서 동시에 $D$ 입니다 — 선택의 여지가 없습니다. 논리합(disjunction) ⊔를 추가하는 순간(그리고 부정 ¬를 안쪽으로 밀어 넣으면 필연적으로 따라오는 그 동반자까지 더하면), 진정한 선택이 도입됩니다. 어떤 개체가 $C \sqcup D$ 일 수 있는지 검사하려면, 추론기는 두 개의 세계를 고려해야 합니다 — 하나는 그것이 $C$ 인 세계, 다른 하나는 그것이 $D$ 인 세계입니다 — 왜냐하면 이 둘은 서로 다른 모순으로 이어질 수 있기 때문입니다. 이것이 테이블로(tableau) 방법입니다: 모든 논리합에 대해 분기하여 후보 모델을 구축하고, 어떤 분기가 $C$ 와 ¬ $C$ 가 함께 나타나는 것과 같은 충돌(clash)로 막히면 역추적합니다.

비용이 자리 잡는 곳이 바로 분기입니다. $k$ 개의 독립적인 논리합을 지닌 개념 표현식은 최대

2^{k}

개의 잎을 가진 탐색 트리를 강제하며, $k$ 는 TBox의 크기에 따라 커집니다. 다항식적 사실 추가가 지수적 탐색이 되어 버렸습니다: EL의 "모든 귀결을 한 번씩 추가한다"가 ALC의 "모든 선택의 조합을 시도한다"로 바뀝니다. 이것이 바로 표에서의 도약 뒤에 있는 메커니즘입니다 — 일반 TBox에 대한 포섭은 ALC에서 $\mathrm{ExpTime}$ -완전이며, SHIQ에서 역할의 역과 개수 제한을 추가해도 여전히 지수적이고, OWL 2 DL의 기반이 되는 논리인 SROIQ에서 노미널과 복합 역할 포함이 상호작용하면 $\mathrm{N2ExpTime}$ -완전에 이릅니다 [1]. HermiT와 Konclude 같은 추론기는 고도로 최적화된 테이블로(및 하이퍼테이블로) 탐색을 구현하는데, 이는 정확히 완전한 언어에 대해서는 다항식적 탈출구가 존재하지 않기 때문입니다. 학계 세계의 충족 불가능한 두 개념은 EL에서 아무런 분기 없이 붙잡힙니다: TenuredStudent는 논리곱 규칙 CR2가 Professor ⊓ Student ⊑ ⊥에서 발동하기 때문에 붙잡히는데(el_completion.py 221–225번째 줄), S(TenuredStudent)가 이미 Professor와 Student를 둘 다 포함하고 있기 때문입니다. 그리고 TenuredStudentAdvisor는 바닥 규칙 CR⊥가 advises를 따라 ⊥를 거꾸로 전파하기 때문에 붙잡히는데(240–244번째 줄), 그것의 유일한 advises 엣지가 이제 충족 불가능해진 TenuredStudent를 가리키고 있기 때문입니다 — 그러나 두 도출 모두, 우리가 서로소(disjointness)를 표현력이 풍부한 논리라면 쓸 수 있었을 부정이 아니라 ⊥로 표현했기 때문에 가능한 것일 뿐입니다.

결정 불가능성의 벽: 알고리즘이 존재하지 않는 질문들

힘을 계속 더해 가다 보면 결국 점선이 표시하는 절벽에서 떨어지게 됩니다. 완전한 1차 논리 — 임의의 술어, 제한 없는 ∀와 ∃, 한계 없는 중첩 — 는 임의의 계산 기계가 한 단계씩 실행되는 과정을 기술할 만큼 충분히 표현력이 풍부합니다. "이 기계는 결국 멈춘다"를 1차 함의로 인코딩할 수 있으므로, 함의를 항상 결정하는 알고리즘이 있다면 그것은 증명 가능하게 풀 수 없는 정지 문제(halting problem)도 풀어낼 것입니다. 그래서 1차 함의는 결정 불가능합니다: 우리가 얻을 수 있는 최선은 진짜 함의는 확인해 주지만 함의가 아닌 경우에는 영원히 멈추지 않을 수도 있는 준결정기뿐입니다.

서술 논리는 의도적으로, 그 절벽의 안전한 쪽에 머무르도록 선택된 1차 논리의 부분집합(fragment)입니다 — 위 표에 있는 모든 DL은 결정 가능합니다. 이 벽은 4부에서 다시 등장하는데, 그곳에서는 존재 규칙(existential rule)(머리가 무언가가 존재한다고 주장하는 규칙)이 온톨로지의 역할 공리를 일반화합니다. 그런 규칙을 발동시키면 그 규칙을 다시 촉발할 수 있는 새로운 개체가 발명되므로, 전방 연쇄 과정 — 체이스(chase) — 은 영원히 계속되면서 익명의 증인들로 이루어진 끝없는 탑을 만들어낼 수 있습니다. 일반적인 존재 규칙은 1차 논리의 결정 불가능성을 물려받으며, 어떤 제한된 형태가 결정 가능성을 되찾아 오는지에 대한 연구는 4부의 주제입니다. 지금 새겨 둘 교훈은 냉정합니다: 어떤 표현력의 한계를 넘어서면 "그냥 답을 기다린다"는 더 이상 계획이 될 수 없는데, 왜냐하면 어떤 입력에 대해서는 답이 결코 오지 않기 때문입니다.

두 개의 잣대: 결합 복잡도 대 데이터 복잡도

단일 곡선이 감추고 있는 미묘한 지점이 하나 있으며, 이것이 바로 OWL 2 QL이 EL과 나란히 존재하는 이유 전부입니다. 복잡도는 두 가지 방식으로 측정될 수 있습니다. 결합 복잡도(combined complexity)는 TBox, ABox, 질의 전체를 함께 셉니다. 데이터 복잡도(data complexity)는 TBox와 질의를 상수로 고정한 채 오직 ABox(데이터)만을 셉니다. 이 구분이 중요한 이유는, 실제 배포 환경에는 수천 개의 TBox 공리로 이루어진 그리 크지 않은 스키마와 수십억 개의 단언으로 이루어진 천문학적 규모의 ABox가 있기 때문입니다. 그 규모에서는 데이터가 압도적이므로, 질의를 위한 정직한 잣대는 데이터 복잡도입니다.

이제 두 프로파일이 갈라집니다. EL은 TBox를 $\mathrm{PTIME}$ 안에서 분류하고 풍부한 스키마 위에서 추론하지만, 그 ABox에 대해 논리곱 질의(conjunctive query)에 답하는 것은 $\mathrm{PTIME}$ -완전한 데이터 복잡도를 지닙니다: 그 작업을 평범한 관계형 데이터베이스에 넘길 수는 없으며 — 모든 데이터에 대해 맞춤형 포화를 실행해야 합니다. QL(DL-Lite 계열)은 스키마 표현력을 희생하는 대신 질의 게임에서 확실히 승리합니다: 어떤 질의든 QL TBox와 결합되면 표준 데이터베이스 안의 원본 ABox에 대해 직접 평가되는 단일 1차(SQL 방식) 질의로 재작성(rewrite)될 수 있습니다. 그 데이터 복잡도는 $\mathrm{PTIME}$ 보다 엄격히 낮은 $\mathrm{AC}^0$ 에 속합니다 — 이것이 바로 1차 재작성 가능성(first-order rewritability)입니다 [3]. 그러므로 선택은 "어느 프로파일이 더 빠른가"가 아니라 "당신이 최적화하려는 문제가 무엇인가"입니다: 크고 표현력이 풍부한 TBox를 분류하려면 EL을, 데이터베이스를 통해 거대한 ABox를 질의하려면 QL을 택하십시오. 두 개의 잣대, 두 개의 승자, 그리고 이것이 표준이 하나 이상의 프로파일을 제공하는 이유입니다.

아직 풀리지 않은 부분

EL에 붙은 $\mathrm{PTIME}$ 배지는 최악의 경우에 대한 약속이며, 최악의 경우는 프로그램이 아닙니다. 그 한계는 오직 어떤 알고리즘이 다항 시간 안에 끝난다는 것만을 말해 줄 뿐, 그 자체로 알고리즘을 손에 쥐여 주지는 않으며, 순진한 알고리즘이라면 매 라운드의 매 규칙마다 어휘 전체를 스캔할 수도 있는데, 이는 다항식적이긴 하지만 낭비적입니다. "원리상 다항식적"과 "실제로 SNOMED CT 위에서 밀리초 단위"라는 것 사이의 간극은 이론이 그저 보장만 해 주는 완성 과정을 공학적으로 구현함으로써 메워집니다: 규칙이 바뀐 사실만을 건드리도록 $S$ 와 $R$ 을 색인화하는 것, 재스캔을 피하도록 규칙 적용 순서를 정하는 것, 그리고 — 무엇보다 먼저 — 모든 공리를 규칙들이 상수 시간에 매칭할 수 있는 소수의 균일한 패턴으로 재구성하는 것입니다. 우리의 실행은 이미 그 마지막 단계에 의존하고 있었습니다: 14 axioms → 16 normal-form axioms가 바로 CR1이 단 한 번의 집합 소속 검사로 발동할 수 있게 해 준 전처리입니다. 다항식적 약속이 실제로 현금화(cash)되는지는 전적으로 그 장치에 달려 있으며, 그것이 바로 3부가 다음에 구축할 내용입니다.

왜 중요한가

신경-기호(neuro-symbolic) 시스템은 추론기를 학습기와 함께 루프 안에 배치하며, 흔히 학습이나 추론 과정에서 그것을 수천 번씩 호출합니다. 다항식적인 추론 단계는 반복해서 호출해도 감당할 수 있는 구성 요소이지만, 지수적인 단계는 시스템 전체를 지배할 수 있는 병목이 되고, 결정 불가능한 단계는 시스템을 무한정 멈추게 할 수 있습니다. 따라서 어떤 논리가 이 곡선 위 어디에 자리 잡고 있는지 아는 것은 이론적인 각주가 아니라 시스템 설계의 결정입니다. 이는 또한 "더 표현력이 풍부하다"는 것이 무엇을 대가로 치르는지를 다시 규정합니다: 하이브리드 모델이 원하는 추가 구성자 하나하나 — 더 풍부한 사전 지식(prior)을 인코딩하기 위한 것이든, 더 부드러운 규칙이든, 개수 제한 하나이든 — 는 곡선 위에서 오른쪽으로, 더 느리거나 심지어 답할 수 없는 추론 핵심을 향한 이동입니다. 프로파일들은 그 거래의 지도이며, 이를 능숙하게 읽어내는 것이야말로 학습 시스템이 실시간으로 실제로 작동시킬 수 있는 상징적 엔진을 고르는 방법입니다.

핵심 용어

결정 가능(Decidable) — 어떤 단일 알고리즘이 항상 올바른 답과 함께 멈추는 문제; 이 장에 나오는 모든 서술 논리는 결정 가능하지만, 완전한 1차 논리는 그렇지 않습니다.
PTIME(다항 시간) — 입력 크기에 대한 다항식 $n^k$ 으로 단계 수가 한정되는 것; 다루기 쉬움의 실질적 의미이며, EL의 포섭이 자리 잡은 곳입니다.
ExpTime / N2ExpTime — 단계 수가 각각 $2^{p(n)}$ 과 $2^{2^{p(n)}}$ 으로 한정되는 것; ALC와 SROIQ의 포섭이 각각 부딪히는 벽입니다.
결정 불가능(Undecidable) — 모든 입력에 대해 그것을 결정하는 알고리즘이 존재하지 않는 것; 1차 함의, 그리고 종료하지 않는 체이스를 통한 일반적인 존재 규칙이 대표적인 사례입니다.
-완전(-complete) — 어떤 복잡도 클래스 안의 그 무엇 못지않게 어려워서, 최악의 경우 그 한계를 뛰어넘을 수 없는 것(예: EL은 $\mathrm{PTIME}$ -완전이고, SROIQ는 $\mathrm{N2ExpTime}$ -완전입니다).
단조 완성 고정점(Monotone completion fixpoint) — EL의 추론을 오직 커지기만 하는 사실 집합으로 본 것으로, $N$ 개의 이름에 대해 $N^2$ 개의 포섭자로 한정되며, 여기서는 3라운드 만에 도달합니다; 분기도, 역추적도 없습니다.
테이블로 분기(Tableau branching) — 논리합과 부정이 강제하는 경우 분할로, 최대 $2^k$ 개의 탐색 분기를 만들어 다항식적 포화를 지수적 탐색으로 바꿉니다.
결합 대 데이터 복잡도(Combined vs data complexity) — 비용을 전체 입력에 대해 측정하는가, 아니면 ABox만을 대상으로 측정하는가의 차이; EL이 더 풍부한 스키마를 분류함에도 불구하고 거대한 데이터를 질의할 때는 QL이 더 나은 이유입니다.
1차 재작성 가능성(First-order rewritability) — 질의와 TBox가 결합되어 원본 ABox에 대한 하나의 SQL 질의가 되는 QL의 속성으로, $\mathrm{AC}^0$ 의 데이터 복잡도를 부여합니다.

이 장이 이끄는 곳

이 곡선은 EL이 왜 저렴한지를 설명해 주지만, 그 저렴한 알고리즘이 어떻게 만들어지는지는 아직 보여 주지 않습니다. 완성 규칙 CR1–CR4가 상수 시간에 발동할 수 있었던 것은 오직 모든 공리가 이미 정확히 네 가지 균일한 형태 중 하나로 다듬어져 있었기 때문입니다 — 포화가 시작되기 전에 14 axioms를 조용히 16 normal-form axioms로 바꾸어 놓은 바로 그 단계입니다. 다음 장인 정규화는 3부를 열면서 그 전처리를 정밀하게 다룹니다: 네 가지 EL 정규형, 복합 하위개념에 이름을 붙여 없애 버리는 새 이름 붙이기(fresh-name) 기법, 그리고 그 재작성이 모든 포섭 관계를 보존하는 보존적 확장(conservative extension)이라는 증명입니다. 이것이 바로 3부가 이 장에서 약속하기만 했던 다항식적 추론기를 조립할 수 있게 해 주는 토대입니다.

이 장에서 다루는 내용​

복잡도 속성 강의: 알아야 할 네 단어​

트레이드오프: 모든 구성자에는 대가가 있다​

EL이 다항식적으로 유지되는 이유: 폭발할 수 없는 고정점​

표현력이 풍부한 논리가 폭발하는 이유: 논리합은 추측하게 만든다​

결정 불가능성의 벽: 알고리즘이 존재하지 않는 질문들​

두 개의 잣대: 결합 복잡도 대 데이터 복잡도​

아직 풀리지 않은 부분​

왜 중요한가​

핵심 용어​

이 장이 이끄는 곳​