Prime Factorization in Models of PV$_1$

논문 개요

이 논문은 Ondřej Ježil (찰스 대학교) 에 의해 작성되었으며, 제한된 산술 (Bounded Arithmetic) 이론인 PV1과 이를 확장한 PV1 + BB(Σb0) 이론에서 '모든 정수는 소인수를 가진다'는 명제 (PrimeFactor) 의 증명 불가능성을 다룹니다. 저자는 소인수분해의 평균적 난이도 (average-case hardness) 에 대한 암호학적 가정을 기반으로, 해당 이론들이 소인수분해의 존재성을 증명할 수 없음을 보였습니다. 이는 해당 이론의 모델에 소인수분해가 존재하지 않는 비표준 수 (nonstandard number) 가 존재함을 의미합니다.

1. 연구 문제 (Problem)

• 배경: 제한된 산술 (Bounded Arithmetic) 은 계산 복잡도 이론과 밀접한 연관이 있는 약한 산술 이론들의 집합입니다. 특히 PV1은 다항식 시간 예측 (polynomial-time predicates) 에 대한 귀납법 (induction) 만을 허용하는 이론입니다.
• 핵심 질문: PV1 (및 그 확장 이론) 은 모든 자연수 $x \ge 2$가 소인수 $y$를 가진다는 명제 $\text{PrimeFactor}: (\forall x \ge 2)(\exists y \le x)(\text{y is prime and } y|x)$를 증명할 수 있는가?
• 기존 결과: 더 강한 이론인 $S^1_2$는 $\Sigma^b_1$-최대값 원리 ($\Sigma^b_1$-LMAX) 를 통해 소인수분해의 존재성을 증명할 수 있습니다. 그러나 PV1 에서는 이 원리가 NP $\subseteq$ P/poly 인 경우를 제외하고는 성립하지 않습니다.
• 목표: 소인수분해가 계산적으로 어렵다는 가정 하에, PV1 및 PV1+BB(Σb0) 가 소인수분해 존재성을 증명할 수 없음을 rigorously 증명하는 것입니다.

2. 방법론 (Methodology)

저자는 다음과 같은 수학적 도구와 논리적 구조를 사용하여 증명을 수행했습니다.

가. KPT 위칭 정리 (KPT Witnessing Theorem)

• KPT 정리 [KPT91]: PV1 에서 $\forall \exists \forall$ 형태의 문장이 증명되면, 다항식 시간 알고리즘 (학생, student) 이 존재하여 $\exists$에 해당하는Witness(예: 소인수) 의 후보들을 생성하고, 실패할 때마다 교정자 (teacher) 로부터 반례를 얻어 결국 올바른 답을 찾는 프로토콜이 존재함을 의미합니다.
• 확장 (CT06): PV1 에 BB(Σb0) (sharply bounded choice scheme) 를 추가한 경우, 학생이 한 번에 다항식 개수의 후보를 출력할 수 있도록 확장된 위칭 정리를 적용합니다.

나. 학생 - 교사 프로토콜 (Student-Teacher Protocols)

• 학생 (Student): 다항식 시간 함수로, 입력된 수 $x$에 대해 소인수 후보를 제시합니다.
• 교사 (Teacher): 학생의 답변이 틀렸을 때 이를 지적하고 올바른 정보를 제공하는 함수입니다. 저자는 특정 소수들의 곱 $x = p_1 \cdots p_d$에 대해, 학생이 소인수를 찾지 못하도록 설계된 효율적인 (다항식 시간) 교사 함수를 구성했습니다.
• 논리: 만약 PV1 이 소인수분해를 증명한다면, KPT 정리에 의해 다항식 시간 학생이 존재해야 합니다. 하지만 저자가 구성한 교사는 학생이 소인수를 찾지 못하도록 방해하며, 이는 소인수분해가 어렵다는 가정과 모순을 일으킵니다.

다. 집합의 필드 (Field of Sets) 와 '명백한 수' (Obvious Numbers)

• 명백한 수: 학생과 교사의 상호작용 과정에서 GCD(최대공약수) 나 나눗셈을 통해 기존에 알려진 수들의 소인수 분해로부터 유도될 수 있는 수를 의미합니다.
• 집합의 필드: 명백한 수들의 소인수 집합들이 형성하는 구조를 분석했습니다.
• 핵심 Lemma: 학생이 '명백하지 않은 수 (non-obvious number)'를 내놓지 않는 한, 교사의 응답은 학생이 소인수를 찾을 수 없도록 설계됩니다. 학생이 결국 소인수를 찾아내려면 반드시 '명백하지 않은 수'를 제시해야 하는데, 이는 다항식 시간 알고리즘으로는 불가능하다는 것을 보였습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

가. 가정 (Assumption)

• 소인수분해의 평균적 난이도: 비균일 다항식 시간 회로 (non-uniform polynomial-size Boolean circuits) 가 $n$비트 두 소수의 곱 중 일정한 비율을 소인수분해할 수 없다는 암호학적 가정을 사용합니다.

나. 주요 정리

1. PV1 에 대한 비증명성 (Corollary 3.11):

   • 위의 가정 하에, 이론 PV1은 $\text{PrimeFactor}$를 증명할 수 없습니다.
   • 즉, PV1 + $\neg$PrimeFactor 를 만족하는 모델이 존재합니다.

2. PV1 + BB(Σb0) 에 대한 비증명성 (Theorem 4.6):

   • BB(Σb0) (sharply bounded choice scheme) 를 추가한 PV1 + BB(Σb0) 이론 역시 $\text{PrimeFactor}$를 증명할 수 없습니다.
   • 이는 $S^1_2$와 PV1 사이의 중간 단계 이론에서도 소인수분해의 존재성이 증명되지 않음을 의미합니다.

3. 모델론적 함의:

   • 증명 불가능성에 의해, 비표준 모델 (nonstandard model) $M$이 존재하며, 이 모델에는 소인수분해가 존재하지 않는 수 $m$이 포함됩니다.
   • 이는 $M$이 Furstenberg domain의 양의 부분 (positive part) 이 아님을 의미합니다. (모든 비가역 원소가 기약인자를 가지는 영역).

다. 이론적 위계 분리

• 저자의 결과는 Cook 과 Thapen [CT06] 의 결과 (소인수분해가 확률적 다항식 시간에 없으면 PV1 $\nvdash$ BB(Σb0)) 와 결합되어 다음 위계를 분리하는 단일 가정을 제공합니다:
  $$\text{PV1} \prec \text{PV1} + \text{BB}(\Sigma^b_0) \prec S^1_2$$
• 이는 Buss 의 계층 구조 (hierarchy) 에서 세 개의 연속된 이론을 구분하는 강력한 결과를 제공합니다.

4. 의의 및 결론 (Significance)

• 계산 복잡도와 논리의 연결: 소인수분해라는 구체적인 계산 문제의 난이도가, 제한된 산술 이론의 증명 능력 (provability) 을 결정하는 핵심 요소임을 다시 한번 확인시켜 주었습니다.
• 모델론적 통찰: 수학적 논리에서 '모든 수는 소인수를 가진다'는 직관적인 사실이 약한 산술 이론에서는 증명될 수 없으며, 이는 해당 이론의 모델이 고전적인 정수론적 성질 (예: Unique Factorization Domain) 을 만족하지 않을 수 있음을 보여줍니다.
• 향후 연구 방향:
  • 더 높은 계층의 이론 (예: $T^1_2$, $S^2_2$ 등) 을 분리할 수 있는 가정이 존재하는지 (Question 5.2).
  • 소인수분해와 약한 비둘기집 원리 (Weak Pigeonhole Principle, iWPHP) 간의 관계 및 모델론적 분리 가능성 (Question 5.1).

요약

이 논문은 소인수분해의 계산적 난이도를 가정으로 삼아, PV1 및 PV1 + BB(Σb0) 이론이 모든 정수의 소인수분해 존재성을 증명할 수 없음을 rigorously 증명했습니다. 이를 통해 제한된 산술 이론의 위계 구조를 분리하고, 해당 이론의 모델이 소인수분해를 갖지 않는 비표준 수를 포함할 수 있음을 보여주었습니다. 이는 계산 복잡도 이론과 수리 논리학 간의 깊은 연관성을 보여주는 중요한 결과입니다.