RE (복잡도)

1. 개요

RE (복잡도)는 계산 복잡도 이론에서 튜링 기계가 모든 '예' 인스턴스를 나열할 수 있는 결정 문제의 클래스인 RE와, RE에 속하는 언어의 보완 언어 집합인 co-RE를 다룬다. RE는 재귀적 가산 집합이자 디오판토스 집합이며, co-RE는 '아니오' 답변은 튜링 기계로 검증할 수 있지만 '예' 답변은 검증하지 못할 수도 있는 문제들을 포함한다. RE와 co-RE는 재귀 언어 R의 상위 집합이며, NRNC는 RE와 co-RE에 속하지 않는 언어의 집합이다. RE-완전은 RE에 대해 완전한 결정 문제들의 집합이며, co-RE-완전은 co-RE에 대해 완전한 결정 문제들의 집합이다. RE-완전 문제의 예시로는 정지 문제, 라이스의 정리, 포스트의 대응 문제 등이 있으며, co-RE-완전 문제의 예시로는 왕 타일에 대한 도미노 문제와 1차 논리에 대한 만족성 문제가 있다.

2. 정의

RE는 튜링 기계가 '예'로 답하는 경우를 열거할 수 있는 결정 문제의 집합을 의미한다. 반면, co-RE는 RE에 속하는 언어의 보완complement^영어 언어들의 집합으로, '아니오'로 답하는 경우를 유한한 시간 안에 검증할 수 있는 문제들의 집합에 해당한다.

2.1. RE

RE는 튜링 기계가 모든 '예' 인스턴스를 하나씩 나열할 수 있는 결정 문제의 클래스이기도 하다. 이것이 '열거 가능'이라는 용어가 의미하는 바이다.

RE의 각 구성원은 재귀적 가산 집합이며 따라서 디오판토스 집합이다.

이 정의(열거 가능성)는 튜링 기계가 특정 언어에 속하는 문자열을 입력받았을 때 정지하고 '예'라고 답하는(허용하는) 정의와 동일하다. 두 정의의 동치성은 다음과 같이 보일 수 있다.

* 열거 가능 → 허용 가능: 어떤 언어에 속하는 모든 문자열을 열거하는 튜링 기계 $E$가 주어졌다고 하자. 이 $E$를 이용하여, 특정 문자열을 입력받는 새로운 튜링 기계를 구성할 수 있다. 만약 입력받은 문자열이 $E$에 의해 열거되면, 이 새로운 튜링 기계는 해당 문자열을 '허용'한다.
* 허용 가능 → 열거 가능: 반대로, 어떤 언어에 속하는 문자열을 입력받았을 때 '허용'하는 튜링 기계 $M$이 주어졌다고 하자. 이 $M$을 이용하여, 해당 언어의 모든 문자열을 열거하는 새로운 튜링 기계를 구성할 수 있다. 이 새로운 튜링 기계는 가능한 모든 입력 문자열에 대해 $M$의 계산 과정을 번갈아 가며 조금씩 실행한다(인터리빙). 만약 $M$이 특정 문자열을 허용하게 되면, 이 새로운 튜링 기계는 그 문자열을 출력한다. 이러한 방식으로 해당 언어에 속하는 모든 문자열을 열거할 수 있다. (입력 문자열과 계산 단계의 조합은 가산 무한하므로, 모든 계산 과정을 결국 실행할 수 있는 순서(예: 대각선 방식)가 존재한다.)

2.2. co-RE

co-RE는 RE에 속하는 언어의 보완complement^영어 언어들의 집합이다. 이는 어떤 문제에 대한 '아니오' 답변은 튜링 기계로 유한한 시간 안에 검증할 수 있지만, '예' 답변은 반드시 유한한 시간 안에 검증할 수 있는 것은 아님을 의미한다.

3. 다른 복잡도 클래스와의 관계

RE는 다른 여러 복잡도 종류와 중요한 관계를 맺고 있다. 재귀 언어의 집합인 R은 RE와 co-RE의 교집합으로 정의된다.
:$\backslash mbox\{R\}\; =\; \backslash mbox\{RE\}\backslash cap\backslash mbox\{co-RE\}$

반대로, RE에도 co-RE에도 속하지 않는 언어들의 집합은 NRNC라고 불린다. 이는 RE와 co-RE의 합집합에 속하지 않는 모든 언어의 집합을 의미한다.
:$\backslash mbox\{NRNC\}\; =\; \backslash mbox\{ALL\}\; -\; (\backslash mbox\{RE\}\backslash cup\backslash mbox\{co-RE\})$

또한, 2020년 연구를 통해 RE가 양자 얽힘을 활용하는 복잡도 종류인 MIP*와 동일하다는 것이 밝혀졌다.

RE는 R을 진부분집합으로 포함하며, 일반적으로 co-RE와는 같지 않다. 즉, R은 RE보다 엄격하게 작은 집합이다.

3.1. R (재귀 언어)

재귀 언어 집합인 R은 RE와 co-RE 모두의 부분 집합이다. 실제로 R은 이 두 클래스의 교집합인데, 이는 어떤 문제가 인식기(recognizer)와 공동 인식기(co-recognizer)를 모두 가질 경우, 두 인식기를 번갈아 실행하여 유한한 시간 안에 해당 문제가 언어에 속하는지 아닌지를 결정할 수 있기 때문이다. 따라서 다음 관계가 성립한다.
:$\backslash mbox\{R\}\; =\; \backslash mbox\{RE\}\backslash cap\backslash mbox\{co-RE\}$

RE는 R보다 엄격하게 더 큰 집합이며, co-RE와는 일반적으로 같지 않다는 것이 알려져 있다.

3.2. NRNC

RE에도 co-RE에도 속하지 않는 언어의 집합을 NRNC라고 한다. 이는 어떤 언어가 해당 집합에 속하는지(멤버십) 또는 속하지 않는지(비 멤버십) 유한한 시간 안에 증명할 수 없는 언어들의 집합이다. 즉, RE 또는 co-RE에 속하지 않는 모든 언어를 포함한다. 이를 수식으로 표현하면 다음과 같다.
:$\backslash mbox\{NRNC\}\; =\; \backslash mbox\{ALL\}\; -\; (\backslash mbox\{RE\}\backslash cup\backslash mbox\{co-RE\})$

NRNC에 속하는 문제들은 결정 불가능 문제일 뿐만 아니라, 문제 자체와 그 문제의 보완 문제 모두 재귀적으로 열거될 수 없다.

3.3. MIP*

2020년 1월에 사전 출판된 한 논문에서는 RE가 MIP*라는 복잡도 종류와 동일하다는 증명을 제시했다. MIP*는 고전적인 검증자가 양자 얽힘 상태를 공유하는 여러 명의 강력한 양자 증명자와 상호작용하는 문제들의 집합을 의미한다. 이 증명은 수정되어 2021년 11월 ACM 통신에 게재되었으며, 코네스 임베딩 문제와 치렐슨 문제가 거짓임을 시사한다.

4. 완전성

계산 복잡도 이론에서 완전성(Completeness)은 특정 복잡도 종류에 속하는 문제들 중 가장 어려운 문제들을 가리키는 개념이다. 어떤 문제가 특정 복잡도 종류에 대해 완전(complete)하다는 것은, 그 문제가 해당 복잡도 종류에 속하면서 동시에 그 종류의 다른 모든 문제를 해당 문제로 환원할 수 있음을 의미한다. 즉, 해당 복잡도 종류의 본질적인 어려움을 대표하는 문제라고 할 수 있다. 이 문서에서 다루는 RE와 co-RE 복잡도 종류에도 각각 RE-완전(RE-complete)과 co-RE-완전(co-RE-complete)이라는 완전성 개념이 존재한다.

4.1. RE-완전 (RE-complete)

RE-완전은 RE에 대해 완전한 결정 문제들의 집합이다. 어떤 의미에서 이것들은 "가장 어려운" 재귀적 가산 문제들이다. 일반적으로, 사용되는 환원에는 다대일 환원이어야 한다는 것 외에는 제한이 없다.

RE-완전 문제의 예시는 다음과 같다:
* 정지 문제: 유한한 입력을 받은 튜링 기계가 실행을 완료할지 또는 영원히 실행될지 여부를 결정하는 문제.
* 라이스의 정리에 따라, 재귀 함수 집합의 임의의 비자명한 부분집합의 멤버십을 결정하는 것은 RE-어렵다. 해당 집합이 재귀적으로 가산적일 때 완전하게 된다.
* 존 마이힐 (1955)은 모든 창의적인 집합이 RE-완전함을 증명했다.
* 군 또는 반군에 대한 균일한 단어 문제. (실제로, 일부 개별 그룹에 대한 단어 문제는 RE-완전하다.)
* 일반적인 무제한 형식 문법의 멤버십을 결정하는 문제. (다시 말하지만, 특정 개별 문법은 RE-완전한 멤버십 문제를 가지고 있다.)
* 일차 논리에 대한 유효성 문제.
* 포스트의 대응 문제: 문자열 쌍의 목록이 주어졌을 때, (반복을 허용하여) 이러한 쌍에서 첫 번째 항목들의 연결이 두 번째 항목들의 연결과 같도록 선택할 수 있는지 여부를 결정하는 문제.
* 디오판토스 방정식이 정수 해를 갖는지 여부를 결정하는 문제.

4.2. co-RE-완전 (co-RE-complete)

co-RE-완전은 co-RE에 대해 완전한 결정 문제들의 집합이다. 어떤 의미에서 이것들은 가장 어려운 재귀적 가산 문제들의 여집합이다.

co-RE-완전 문제의 예는 다음과 같다.
* 왕 타일에 대한 도미노 문제.
* 1차 논리에 대한 만족성 문제.