RE (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
- 2.1. RE
- 2.2. co-RE
3. 다른 복잡도 클래스와의 관계
4. 완전성
- 4.1. RE-완전 (RE-complete)
- 4.2. co-RE-완전 (co-RE-complete)
참조

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차 논리에 대한 만족성 문제가 있다.

더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

RE (복잡도)
개요
분류	재귀 열거 가능 언어
계산 복잡도 종류	복잡도 종류
관련 종류	R (복잡도) co-RE NP (복잡도) P (복잡도)
완전한 문제	정지 문제
정의
설명	형식 언어 L에 대해, L이 RE 등급에 속한다는 것은 L이 튜링 기계에 의해 인식될 수 있음을 의미한다.
한국어 번역	즉, 튜링 기계가 L의 문자열을 입력으로 받아들이면, 기계는 궁극적으로 정지하고 수락한다.
추가 설명	그러나 문자열이 언어에 속하지 않으면, 기계는 정지하거나 영원히 루프할 수 있다.
속성
속성 1	언어 L이 RE이고, RE 언어 L2에 다대일로 축소 가능하다면, L2도 RE이다.
속성 2	언어 L이 RE이면, 언어 L도 RE이다. 여기서 L은 L의 클레이니 스타이다.
속성 3	두 개의 RE 언어의 합집합과 교집합은 RE이다.
속성 4	언어와 그 보완 모두 RE이면, 그 언어는 결정 가능 언어이다.

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'''의 교집합으로 정의된다.^[3]

: $\mbox{R} = \mbox{RE}\cap\mbox{co-RE}$

반대로, '''RE'''에도 '''co-RE'''에도 속하지 않는 언어들의 집합은 '''NRNC'''라고 불린다. 이는 '''RE'''와 '''co-RE'''의 합집합에 속하지 않는 모든 언어의 집합을 의미한다.

: $\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{co-RE})$

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

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

3. 1. R (재귀 언어)

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

:

\mbox{R} = \mbox{RE}\cap\mbox{co-RE}

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

3. 2. NRNC

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

:

\mbox{NRNC} = \mbox{ALL} - (\mbox{RE}\cup\mbox{co-RE})

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

3. 3. MIP*

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

4. 완전성

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

4. 1. RE-완전 (RE-complete)

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

RE-완전 문제의 예시는 다음과 같다:

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

4. 2. co-RE-완전 (co-RE-complete)

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

co-RE-완전 문제의 예는 다음과 같다.

왕 타일에 대한 도미노 문제.
1차 논리에 대한 만족성 문제.

참조

_[1] 기타
_[2] 서적 Logic and Algorithms, With Applications to the Computer and Information Sciences https://archive.org/[...] Wiley
_[3] 기타
_[4] arXiv MIP*=RE
_[5] 학술지 MIP* = RE 2021-11
_[6] 간행물 Creative sets

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com