환원(재발론)

계산가능성 이론에서는 많은 환원성 관계(감소, 환원성 및 환원성의 개념이라고도 함)를 연구한다.그들은 질문에 동기를 부여한다: $자연수$의 A$$ ${\displaystyle A}$ $및{\displaystyle }$ B$$ ${\displaystyle B}$ 집합이 주어진다면, $B{\displaystyle }$ ${\displaystyle B}$의 멤버쉽을 결정하는 방법을 $A{\displaystyle }$ ${\displaystyle A}$의 멤버쉽을 결정하는 방법으로 효과적으로$$ 변환할 수 있는가$?$ 이 질문에 대한 대답이 긍정이라면n $A{\displaystyle }$ ${\displaystyle A}$은(는) $B{\displaystyle }$ ${\displaystyle B}($으)로 축소할 수 있다고 한다$$$.$

환원 가능성 개념에 대한 연구는 의사결정 문제에 대한 연구에 의해 동기 부여된다.많은 축소 가능성의 개념에서, 만약 어떤 비컴퓨팅 세트가 A $집합$으로 축소될 수 있다면, $A$ ${\디스플레이$ 스타일 $A}$도 역시 계산 불가능해야 한다$$.이것은 많은 세트가 컴퓨팅이 불가능하다는 것을 증명하는 강력한 기술을 제공한다.

환원성 관계

환원성 관계는 자연수 집합에 대한 2진수 관계로서 다음과 같다.

• 반사성: 모든 세트는 스스로 줄일 수 있다.
• Transitive: 세트 $A{\displaystyle }$ ${\displaystyle A}$을(를) $세트{\displaystyle }$ B ${\displaystyle B}$로 $축소$할$$수 $있고$, B {\$displaystyle$$$B}을$$(를) $세트{\displaystyle }$ C$$${\displaystyle C}$로 축소할 수 있는 $경우$,$${\$displaystystyle A}$은(으)로 축소할 수 있다$.$

이 두 가지 특성은 환원성이 자연수의 파워셋에 대한 사전 순서임을 암시한다.그러나 모든 예약주문이 환원 가능성 개념으로 연구되는 것은 아니다.계산가능성 이론에서 연구된 개념은 $B{\displaystyle }$ ${\displaystyle B}$에 대한 의사결정 절차가 A ${\displaystyle A}$에 대한 의사결정 절차로 효과적으로 변환될 수 있는$$ 경우에만$$ $A{\displaystyle }$ ${\displaystyle A}$이(가) $B{\displaystyle }$ ${\displaystytle B}($으)로$$ 축소될 수 있다는 비공식 특성을 가지고 있다$.$서로 다른 환원성 관계는 그러한 변환 과정을 허용하는 방법에 따라 다르다.

환원성 관계의 정도

모든 환원성 관계(사실, 모든 사전 순서)는 두 세트가 서로 환원 가능한 경우에만 등가성 관계를 유도한다.계산가능성 이론에서 이러한 동등성 클래스를 환원성 관계의 정도라고 한다.예를 들어 튜링도는 튜링 환원성에 의해 유도된 고유성 집합의 동등성 등급이다.

환원성 관계의 정도는 다음과 같은 방식으로 부분적으로 관계에 의해 정렬된다.$\le {\displaystyle }$ ${\displaystyle \leq }$을(를) 환원성 관계가$$ 되게 하고 $C{\displaystyle }${\$displaystyle C}$과 D$${\$displaystyle D}$을(를) 그 정도의 두 개로 한다$$.Then ${\displaystyle C\leq D}$ if and only if there is a set ${\displaystyle A}$ in ${\displaystyle C}$ and a set ${\displaystyle B}$ in ${\displaystyle D}$ such that ${\displaystyle A\leq B}$. This is equivalent to the property that for every set ${\displaystyle A}$ in ${\di$$Splaystyle C}$과(와) $D{\displaystyle }$ ${\displaystyle D$ A$$ B {\$displaystyle$ A$\leq$ B$}$의 모든 $세트{\displaystyle }$ B ${\$displaystyle D}의 두 세트가 동일하고 $D{\displaystyle }$ ${\displaystystyle D}$의 두 세트가 동일하기$$ 때문이다$.$여기에 보이는 것처럼, 도를 나타내기 위해 굵은체 표기법을 사용하는 것이 일반적이다.

튜링 환원성

가장 근본적인 환원성 개념은 튜링 환원성이다.자연수$$ 집합 A {\$displaystyle A}$은(는) $A{\displaystyle }$ ${\displaystyle B}$을(를) 오라클 집합으로$$ 실행할 때 $A{\displaystyle }$ ${\displaystyle A}$의 지시 함수(특성 함수$)$를 계산하는 오라클 튜링 시스템이 있는 경우에만$$ 설정 B {\$displaystyle$ $B}$로 $축소$할 수 있다$.$"$B{\displaystyle }$ ${\displaystyle B}$에 $n{\displaystyle }$ ${\displaystyle n}$이(가) 있는 경우 A ${\displaystyle A}$에 대한 표시기 함수를 계산하는 알고리즘이 있는 경우에만$$$$ $Turing style$ A$}$을$($를) B {\displaystystyle $B}$로 축소할 수 있다$$.$$

튜링 환원성은 교회-튜링 논문에 따르면 가장 일반적인 환원 가능성 관계가 유효하기 때문에 다른 환원 가능성 개념의 구분선 역할을 한다.튜링 환원성을 암시하는 환원성 관계는 강한 환원성으로 알려져 있는 반면, 튜링 환원성에 의해 암시되는 환원성은 약한 환원성이다.동등하게, 강한 환원성 관계는 정도가 튜링도보다 더 미세한 동등성 관계를 형성하는 관계인 반면, 약한 환원성 관계는 튜링 동등성보다 더 강한 등가성 관계를 형성하는 관계인 것이다.

튜링 환원성보다 강력한 감소

강한 환원성은 다음을 포함한다.

• 1-1 축소 가능성:${\displaystyle \mathrm{모든}}$ $x{\displaystyle }$ ${\displaystyle x}$에 $대해{\displaystyle }$ A${\displaystyle (}$ x${\displaystyle }$)${\displaystyle }$= ${\displaystyle B(}$ ${\displaystyle x}$)$${\$displaystyle A(x)=B(x)}$을(를) 가진$$ 계산 가능한 일대일 $함수{\displaystyle }$ f ${\displaystyle f}$이(가) 있는 경우$$, A$${\displaystystytyle $}$은 1로 $축소$할 수 있다$$$.$
• 다원 축소 가능성:${\displaystyle \mathrm{모든}}$ $x{\displaystyle }$ ${\displaystyle x$에 대해 계산 $가능$한 ${\displaystyle \mathrm{함수}}$f${\displaystyle }${\$displaystyle f}$이(가) 있고 A${\displaystyle (}$ x ) = ${\displaystyle B(x}$) ${\displaystyle$A($x)=B(x)}$이(가) 있는$$ 경우$$${\displaystystyle$$A$}은$($가)로 여러 개 축소할 수 있다$$.
• 진리 테이블 축소 가능:${\displaystyle }$$A{\displaystyle }$ ${\displaystyle A}$이(가) 단일(오라클)을$$ $통해{\displaystyle }$ B ${\displaystyle B}($으)로 튜링할 수 있는 경우$$ ${\displaystyle A}$ ${\displaystyle$ $A$$}$은(는) B ${\displaystystyle$ B$}($)로 진실로 축소할 수 있다$$.모든 오라클과 관련된 전체 기능을 생성하는 튜링 머신.
• 약한 진리 테이블 축소 가능:${\displaystyle }$Turing이 $B{\displaystyle }$ ${\displaystyle$ $B$$}$에서 A ${\displaystyle$ A$}($으)로 감소하고 계산$$ 가능한 $함수{\displaystyle }$ f ${\displaystyle$ f$}($으)가 사용 범위를 벗어나는$$ 경우 ${\displaystyle$ $A$$}$은(으$)$로 약한 진실-표적 $감소$가 가능하다.$A{\displaystyle }$ ${\displaystyle A}$이(가) B ${\displaystyle B$ $A{\displaystyle }$ ${\displaystyle A}$은(는) B ${\displaystyle$ B$\}($$으{\displaystyle }$)로 축소될 때마다 모든 오라클의 트리 위에서 계산 가능한 경계를 구성할 수 있으므로 B {\displaystytype B$}$로도 축소할$$ 수 있다.모든 웅변
• 양의 환원 가능:${\displaystyle A}$ is positive reducible to ${\displaystyle B}$ if and only if ${\displaystyle A}$ is truth-table reducible to ${\displaystyle B}$ in a way that one can compute for every ${\displaystyle x}$ a formula consisting of atoms of the form ${\displaystyle B(0),B(1),..$$.}$ 이러한$$ 원자가 및/또는 에 의해 결합되는 경우$,$ $여기$서 a${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle a$$}$과(와$)$ $b{\displaystyle }$ {\$displaystyle$ a$=$$1$$}$ 및 b =${\displaystyle }$1 ${\displaystyle b=1}$등인$$ 경우 및(와$)$가 ${\displaystyle 1}$이다.
• 열거 축소 가능성:$A{\displaystyle }$ ${\displaystyle A}$에서 $B{\displaystyle }$ ${\displaystyle B}$까지의 열거성 유효 절차에 관련된 양의 환원성과 유사하다$.$
• 분리 환원 가능:또는 그것만이 허용되는 추가 제약조건으로 양수축 가능과 유사하다.
• 결막 환원성:양수 환원성과 유사하며, 와 의 추가 제약 조건만 허용된다.
• 선형 축소 가능성:양의 환원성과 유사하지만 $B{\displaystyle }$(${\displaystyle n}$) ${\displaystyle B(n)}$ 형식의 모든 원자가 배타적 또는 의 원자에 의해 결합되는$$ 제약조건과 유사하다.In other words, ${\displaystyle A}$ is linear reducible to ${\displaystyle B}$ if and only if a computable function computes for each ${\displaystyle x}$ a finite set ${\displaystyle F(x)}$ given as an explicit list of numbers such that ${\displaystyle x\in A}$ if and only if ${\displa$$ystyle F(x)}$에는 $B{\displaystyle }$ ${\displaystyle B}$의 홀수 개수의 요소가 포함되어$$ 있다$.$

이들 중 상당수는 포스트(1944년)에 의해 소개되었다.Post는 중지 문제가 Turing으로 축소될 수 없는 비컴퓨팅적이고 계산적으로 열거할 수 있는 세트를 찾고 있었다.1944년에 그런 세트를 구성할 수 없었기 때문에, 그는 대신 그가 소개한 다양한 환원성을 위해 유사한 문제들에 대해 작업했다.이러한 환원성은 그 이후 많은 연구의 대상이 되었고, 그들 사이의 많은 관계가 알려져 있다.

경계 환원성

위의 각각의 강한 환원성의 경계 형태를 정의할 수 있다.이 중 가장 유명한 것은 경계 진리표 감소지만 경계된 튜링, 경계 약한 진리표 등이 있다.이 첫 번째 세 가지는 가장 흔한 것이고 그들은 질의 횟수에 기초한다.$예$를 들어, Turing $시스템{\displaystyle }$ M ${\displaystyle B}$에 상대적인 Turing 시스템$$M {\$displaystyle M}$ $계산{\displaystyle }$A {\$displaystyle A}$이($가{\displaystyle }$) 최대 $n{\displaystyle }${\$displaystyle$ $N$$}$개의$$ 목록, 쿼리$$ B ${\displaystystyle$ $B$$}$의 목록을 계산하는 경우에만$$ $집합$이 B ${\\daystytable$로 축소 $가능함$이러한 숫자에 따라 가능한 모든 Oracle 응답에 대해 종료한다. $n{\displaystyle }$ ${\displaystyle n}$ 값은 $x{\displaystyle }$ ${\displaystyle x}$과(와) 항상 독립적이다$.$경계 약진표와 경계 튜링 감소의 차이는 첫 번째 경우에는 최대 $n{\displaystyle }$ ${\displaystyle n}$개의$$ 쿼리를 동시에 수행해야 하고 두 번째 경우에는 쿼리를 차례로 할 수 있다는 것이다.이러한 이유로 $A{\displaystyle }$ ${\디스플레이$ 스타일 $A}$이(가) $B{\displaystyle }$ ${\displaystyle$ B$}($으)로 제한되지만 약한$$ 진실은 $B{\displaystyle }$ ${\displaystyle$ B$}($으)로 축소되지 않는 경우가 있다$.$

컴퓨팅 복잡성의 강력한 감소

위에 열거된 강력한 감소는 의사결정 절차에 의해 Oracle 정보에 접근할 수 있는 방법을 제한하지만, 달리 이용 가능한 계산 리소스를 제한하지는 않는다.따라서 집합 $A{\displaystyle }$ ${\displaystyle A}$을(를) 디커블할 수 없는 경우, $A{\displaystyle }$ ${\displaystyle A}$이(가) 다항식 시간 또는 지수 시간 디커블이 아니더라도$$ 위에 나열된 강력한 축소 가능성 관계에서$$ A ${\$displaystystyle $A$$}$을(를) $세트{\displaystyle }$ B ${\displaystystytime$ B$}$으로 축소할 수 있다$$.이는 이론적 계산가능성에 관심이 있는 계산가능성 이론의 연구에서는 받아들일 수 있지만, 특정 무증상 자원 한계에서 세트가 결정될 수 있는 계산 복잡성 이론에는 타당하지 않다.

계산 복잡성 이론에서 가장 일반적인 환원성은 다항식 시간 환원성이다. 집합 A는 모든 $n{\displaystyle }$ ${\displaystyle$ n$\},$ $n{\displaystyle }$ ${\displaystyle$ n$}$에 대해 $f$인 경우에만$$ $A{\displaystyle }$${\displaystyle \{\backslash \mathrm{displaystyle}}$ $A}$에 있는$$ 다항식 시간 함수가 있는 경우$$ $집합{\displaystyle }$ B ${\displaystystyle B}$으로 환원할 수 있다.${\displaystyle f(n)}$은(는) $B{\displaystyle }$ ${\displaystyle B}$에 있다$$$.$ 이 축소성은 본질적으로 다원 축소성의 자원 경계 버전이다.다른 자원 경계 환원성은 다른 자원 한계가 관심 있는 계산 복잡성 이론의 다른 맥락에서 사용된다.

튜링 환원성보다 약한 감소량

튜링 환원성이 가장 일반적으로 효과적인 환원성이지만 환원성 관계가 약하게 연구된다.이러한 환원성은 산술 또는 집합 이론에 대한 집합의 상대적 정의 가능성과 관련이 있다.여기에는 다음이 포함된다.

• 산술적 환원성:$B{\displaystyle }$ {\$displaystyle B}$에 대한 추가 술어가 있는 Peano 산술의 표준 모델에서 $A{\displaystyle }$ ${\displaystyle A}$을(를) 정의할 수 있는$$ 경우$$ 세트 $B{\displaystyle }$ ${\displaystyle$ B$}$에서 산술적으로 A를$$ 산술적으로 나타내며$,$ $마찬가지$로 포스트의 정리에 따르면 $A$는 B ${\displaystyty B}$에서만 산술적으로 나타난다.${\displaystyle A}$은(는) $B{\displaystyle {}^{(n)}}$ ${\$$displaystyle$ B$^{(n)}},$ $일부{\displaystyle }$ 자연 숫자 $n{\displaystyle }$ ${\displaystyle B$$}$의 튜링 점프$($$n{\displaystyle }$ {\$displaystyle$ B$})$로 축소할 수 있다$$$.$산술적 계층 구조는 산술적 환원성을 더 세분화한다.
• 초산술적 환원성:A set ${\displaystyle A}$ is hyperarithmetical in a set ${\displaystyle B}$ if ${\displaystyle A}$ is ${\displaystyle \Delta _{1}^{1}}$ definable (see analytical hierarchy) over the standard model of Peano arithmetic with a predicate for ${\displaystyle B}$. Equivalently, ${\displaystyle A$$}$ is hyperarithmetical in ${\displaystyle B}$ if and only if ${\displaystyle A}$ is Turing reducible to ${\displaystyle B^{(\alpha )}}$, the ${\displaystyle a}$th Turing jump of ${\displaystyle B}$, for some ${\displaystyle B}$-recursive ordinal ${\displaystyle a}$.
• 상대 구성 가능성:$A{\displaystyle }$ ${\displaystyle A}$이(가) $L{\displaystyle }$( ${\displaystyle B}$) ${\displaystyle L(B)}$이고$,$ $B{\displaystyle }${\$displaystyle B}$과(와) 모든 서수를 포함하는 ZFC 집합 이론의 최소 전이 모델인 경우$$, $세트{\displaystyle }$ A$${\$displaystystyle$ $A}$은 세트 $}$에서 비교적 구성 가능하다$$.

참조

• K. Ambos-Spies와 P.2006년 Fejer."불굴의 천국"게시되지 않은 사전 인쇄.
• P. Odifreddi, 1989.고전적 재귀 이론, 노스홀랜드. ISBN0-444-87295-7
• P. Odifreddi, 1999.고전적 재귀 이론, 제2권, 제2권, 제2권, 제3권, 제3권, 제3권.ISBN 0-444-50205-X
• E. Post, 1944, "긍정적인 정수와 그 결정 문제들의 반복적으로 열거", 미국수학협회의 게시판, 제50권, 페이지 284~316쪽.
• 1967년 H. 로저스 주니어재귀함수와 유효계산성 이론, 1987년 2판, MIT 프레스.ISBN 0-262-68052-1(페이퍼백), ISBN 0-07-053522-1
• G. 색스, 1990년높은 재귀 이론, 스프링거-버락.ISBN 3-540-19305-7