RE(복잡성)

RE (complexity)

연산성 이론과 계산 복잡성 이론에서 RE(재귀적으로 열거할 수 있음)는 튜링 기계에 의해 유한한 시간 내에 '예' 대답을 검증할 수 있는 의사결정 문제의 등급이다.[1]비공식적으로, 문제 사례에 대한 대답이 '예'라면, 이것을 결정하는 데 유한한 시간이 걸리는 절차가 있다는 뜻이며, 이 절차는 진정한 답이 '아니오'일 때 결코 '예'를 거짓으로 보고하지 않는다.그러나, 진정한 답이 '아니오'일 때, 그 절차는 멈출 필요가 없다; 일부 '아니오' 사례에 대해서는 '무한 루프'로 갈 수도 있다.이러한 절차를 의사결정 문제에 대한 완전한 해결책으로 정의되는 알고리즘과 구별하기 위해 세미 알고리즘이라고 부르기도 한다.[2]

마찬가지로, co-RE는 RE에서 언어를 보완하는 모든 언어의 집합이다.어떤 의미에서, co-RE는 제한된 시간 내에 회원 자격이 반증될 수 있는 언어를 포함하고 있지만 회원 자격을 증명하는 것은 영원히 걸릴 수 있다.

등가정의

동등하게, RE는 튜링 기계가 모든 '예' 인스턴스를 하나씩 열거할 수 있는 의사결정 문제의 등급이다(이것이 바로 '지속할 수 있는' 의미임).RE의 각 멤버는 재귀적으로 열거할 수 있는 집합이므로 디오판틴 집합이다.

이 값을 동등하게 표시하려면 허용된 모든 입력을 열거하는 시스템 이(가) 있는 경우 문자열을 사용하는 다른 시스템에서 을(를) 실행하고 문자열이 열거된 경우 승인할 수 있다는 점에 유의하십시오.반대로 기계 이(가) 입력 언어일 때 수락하는 경우, 다른 기계는 된모든 입력 및 출력 에서 M {\displaystyle 의 시뮬레이션을 인터리빙하여 언어의 모든 문자열을 열거할 수 있다(결국 모든 실행 단계에 도달하는 실행 순서가 있음).입력과 단계의 순서 쌍이 거의 많기 때문이다).

타계급과의 관계

재귀 언어 집합(R)은 RE와 co-RE의 하위 집합이다.[3]사실, 그것은 그 두 등급의 교차점이다. 왜냐하면 우리는 단순히 결과를 얻을 때까지 인식자와 공동인식이 존재하는 문제를 상호 교환함으로써 결정할 수 있기 때문이다.따라서 다음과 같다.

.

반대로, RE도 co-RE도 아닌 언어 집합을 NRNC라고 한다.이것들은 멤버쉽이나 비 멤버쉽이 한정된 시간 내에 증명될 수 없는 언어들의 집합이며, RE나 co-RE에 없는 다른 모든 언어들을 포함하고 있다.즉,

이러한 문제들은 돌이킬 수 없을 뿐만 아니라, 그것들 또한 그들의 보완도 반복적으로 열거되지 않는다.

2020년 1월, 한 프리프린트가 RE가 클래스 MIP*에 해당한다는 증거를 발표하였다(고전 검증자가 얽힘을 공유하는 복수의 전지전능한 양자 프로버들과 상호작용하는 클래스).[4]

재완성

RE-complete는 RE에 대해 완료된 의사결정 문제의 집합이다.어떤 의미에서, 이것들은 반복적으로 열거되는 가장 "힘든" 문제들이다.일반적으로 사용 감소가 다수 1 감소여야 한다는 것을 제외하고는 어떤 제약도 없다.

재완성 문제의 예:

  1. 중지 문제:제한된 입력이 주어진 프로그램이 실행을 마칠 것인지 아니면 영원히 실행될 것인지 여부.
  2. 라이스의 정리(Rice's Organization)에 따르면, 재귀함수 집합의 비종교적 부분집합에서 멤버십을 결정하는 것은 RE-hard이다.그것은 세트가 반복적으로 열거될 때마다 완성될 것이다.
  3. 존 마이힐(1955)은 모든 창조적인 세트가 RE-Complete라는 것을 증명했다.[5]
  4. 그룹 또는 세미그룹에 대한 통일 단어 문제. (사실, 일부 개별 그룹의 단어 문제는 RE-complete이다.)
  5. 일반적인 무제한 형식 문법에서의 멤버십 결정. (또한, 특정 개별 문법에는 RE-완전 멤버십 문제가 있다.)
  6. 1차 논리 타당성 문제.
  7. 사후 대응 문제:문자열 쌍의 리스트를 지정하면 첫 번째 항목(쌍의 쌍)의 결합이 두 번째 항목의 결합과 같도록 이러한 쌍(반복 허용) 중에서 선택할 수 있는지 여부를 결정한다.
  8. 디오판타인 방정식에 정수 용액이 있는지 확인.

공동 RE-완료

co-RE-완성은 co-RE에 대해 완료된 의사결정 문제의 집합이다.어떤 의미에서, 이것들은 가장 어려운 반복적으로 열거된 문제들의 보완물이다.

공동 RE 완료 문제의 예:

  1. 왕 타일의 도미노 문제.
  2. 1차 논리 만족도 문제.

참고 항목

참조

  1. ^ 복잡성 동물원: 클래스 RE
  2. ^ Korfhage, Robert R. (1966). Logic and Algorithms, With Applications to the Computer and Information Sciences. Wiley. p. 89. A method of solution will be called a semi-algorithm for [a problem] P on [a device] M if the solution to P (if one exists) appears after the performance of finitely many steps. A semi-algorithm will be called an algorithm if, in addition, whenever the problem has no solution the method enables the device to determine this after a finite number of steps and halts.
  3. ^ 복잡성 동물원: 클래스 co-RE
  4. ^ Ji, Zhengfeng; Natarajan, Anand; Vidick, Thomas; Wright, John; Yuen, Henry (2020). "MIP*=RE". arXiv:2001.04383 [quant-ph].
  5. ^ Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1 (2): 97–108, doi:10.1002/malq.19550010205, MR 0071379.