진실테이블감소
Truth-table reduction계산가능성 이론에서 진리표 감소는 자연수 집합에서 다른 숫자로 감소하는 것이다.[clarification needed]'툴'로서 튜링 감소에 비해 약한데, 세트 간 튜링 감소가 모두 진리표 감소에 의해 수행되는 것은 아니지만, 진리표 감소가 모두 튜링 감소에 의해 수행될 수 있기 때문이다.동일한 이유로 튜링 환원성보다 더 강한 환원성이 있다고 하며, 이는 튜링 환원성을 의미하기 때문이다.약한 진실-표적 감소는 진실-표적 감소에 대한 제약조건을 약화시키고, 더 약한 동등성 분류를 제공하기 때문에 그렇게 명명된 관련 감소형이다. 따라서 "약한 진실-표적 감소"는 사실 진실-표적 감소보다 더 강력할 수 있고, 그렇지 않은 감소를 수행할 수 있다.진실 표로 볼 수 있는
세트 B에서 세트 A로 튜링 감소는 계산하는 동안 A의 다양한 요소의 멤버쉽에 관한 질문을 함으로써 B의 단일 요소의 멤버쉽을 계산한다. 그것은 이전의 질문에 대한 대답을 바탕으로 어떤 질문을 하는지를 적응적으로 결정할 수 있다.이와는 대조적으로 진실-표적 감소 또는 약한 진실-표적 감소는 모든 (결국 많은) 신탁 질의를 동시에 제시해야 한다.진실-표 감소에서, 감소는 또한 부울함수(진실표)를 주는데, 이 부울함수(진실표)는 질의에 대한 답을 줄 때, 감소의 최종 답을 산출한다.약한 진실-표 감소에서, 감소는 주어진 답변에 의존할 수 있지만 오라클의 추가 질문을 하지 않는 추가 계산을 위한 기초로 오라클 해답을 사용한다.
동등하게, 약한 진리표 감소는 감소의 사용이 계산 가능한 함수에 의해 제한되는 튜링 감소다.이러한 이유로, 그것들은 약한 진실-표(wtt) 감소라기보다는 경계-투어링(bT) 감소라고 부르기도 한다.
특성.
모든 진리 테이블 감소가 튜링 감소가므로 A가 진리 테이블 감소가 B(A tt≤ B)로 가능하다면 A도 또한 Turing 감소가 가능하다(A ≤T B).또한 1-1 축소 가능성, 다수 1 축소 가능성 및 약한 진리 표 축소성을 고려할 때,
- ,
또는 다시 말하면, 1-1 환원성은 다수의 1 환원성을 내포하고, 이는 진리-표 환원성을 내포하고, 이는 다시 약한 진리-표 환원성을 내포하고, 이는 튜링 환원성을 내포한다.
또한, A는 에 대한 전체 기능을 통해 Turing이 B로 환원될 경우 진실로 환원할 수 있다전방 방향은 사소한 것이며 반대 방향의 경우 }이가) 총 계산 가능한 기능이라고 가정한다.A(n) 계산용 진실 테이블을 작성하려면 길이 m σ( 의 모든 이진 문자열 }}에 대해 숫자 m을 검색하십시오.\이후Γ{\displaystyle \Gamma}모든 도로에서 2<해 총어야 한다 그러한 mKőnig의 부명제에 의해;는 분명히 존재한다 ω{\displaystyle 2^{<>\omega}}. 감안할 때 그러한 m그것은 단순한 문제를 독특한 truth-table는 Γ σ(n){\displaystyle \Gamma ^{\sigma}(n)}인가될 때에 σ{\displaystyle \si.gma 진리표 환원성이 약해 전진방향이 실패함.
참조
- 1967년 H. 로저스 주니어재귀함수와 유효계산성 이론, 1987년 2판, MIT 프레스. ISBN0-262-68052-1(페이퍼백), ISBN0-07-053522-1
