오라클 머신

블랙박스 시스템
블랙박스 시스템
시스템
	블랙박스 · 오라클 머신
방법 및 기술
	블랙박스 테스트 · 블랙박싱
관련 기법
	피드 포워드 · 난독화 · 패턴인식 · 화이트 박스 · 화이트 박스 테스트 · 시스템 식별
기초
	선행 정보 · 제어 시스템 · 오픈 시스템 · 운영연구 · 열역학계
	v; t;

복잡성 이론과 계산 가능성 이론에서, 오라클 기계는 의사결정 문제를 연구하기 위해 사용되는 추상적인 기계다. 오라클이라 불리는 블랙박스가 달린 튜링 기계로 시각화할 수 있어 한 번의 조작으로 특정 문제를 해결할 수 있다. 그 문제는 어떠한 복잡성 등급도 될 수 있다. 심지어 정지 문제와 같이 불해독할 수 없는 문제들도 사용될 수 있다.

오라클레스

오라클 머신은 오라클에 연결된 튜링 머신으로 구상될 수 있다. 이러한 맥락에서 신탁은 어떤 문제를 해결할 수 있는 개체로, 예를 들어 의사결정 문제나 기능 문제일 수 있다. 이 문제는 계산할 필요가 없다; 신탁은 튜링 기계나 컴퓨터 프로그램으로 가정되지 않는다. 오라클은 단순히 주어진 연산 문제의 모든 예에 대해 솔루션을 생산할 수 있는 "블랙박스"일 뿐이다.

의사결정 문제는 자연수(또는 문자열)의 집합 A로 표현된다. 문제의 예로는 임의의 자연수(또는 문자열)가 있다. 숫자(문자열)가 세트에 있으면 "YES"이고, 그렇지 않으면 "NO"이다.
함수 문제는 자연수(또는 문자열)에서 자연수(또는 문자열)까지 함수 f로 표현된다. 문제의 예는 f에 대한 입력 x이다. 해결책은 f(x) 값이다.

오라클 머신은 튜링 머신의 모든 통상적인 작동을 수행할 수 있으며, 또한 오라클을 쿼리하여 해당 오라클의 계산적 문제의 모든 인스턴스에 대한 해결책을 얻을 수도 있다. 예를 들어, 문제가 자연수 A의 집합에 대한 의사결정 문제라면, 오라클 기계는 자연수를 공급하고, 오라클은 그 숫자가 A의 요소인지 여부를 명시하는 "예" 또는 "아니오"로 응답한다.

정의들

아래에 설명된 바와 같이 오라클 Turing 기계에 대한 많은 동등한 정의가 있다. 여기에 제시된 것은 판 멜케벡(2000:43)에서 나온 것이다.

튜링 기계와 같은 오라클 기계에는 다음이 포함된다.

작업 테이프: 시작 또는 끝이 없는 셀 시퀀스. 각 셀에는 B(공백용) 또는 테이프 알파벳의 기호가 포함될 수 있음.
읽기/쓰기 헤드(작업 테이프의 단일 셀에 위치하며, 거기에서 데이터를 읽고, 새 데이터를 쓰고, 테이프를 따라 위치를 증가 또는 감소시킬 수 있음)
제어 메커니즘은 제한된 수의 상태 중 하나에 있을 수 있으며, 현재 상태와 읽고 있는 데이터에 따라 다른 동작(데이터 읽기, 데이터 쓰기, 제어 메커니즘 이동 및 상태 변경)을 수행한다.

오라클 머신은 이러한 구성 요소 외에도 다음을 포함한다.

업무용 테이프와는 별개의 반무한 테이프인 오라클 테이프 오라클 테이프의 알파벳은 워크 테이프의 알파벳과 다를 수 있다.
읽기/쓰기 헤드와 마찬가지로 오라클 테이프 읽기 및 쓰기 기호를 따라 왼쪽 또는 오른쪽으로 이동할 수 있는 오라클 헤드
AQH 상태와 RESSUPTION 상태라는 두 개의 특수 상태.

때때로 오라클 머신은 ASCH 상태로 들어갈 수 있다. 이 경우 다음 동작이 단일 계산 단계에서 수행된다.

오라클 테이프의 내용은 오라클 컴퓨팅 문제의 한 예로 간주된다.
오라클을 참조하고 오라클 테이프의 내용을 문제의 해당 인스턴스에 대한 솔루션으로 교체한다.
오라클 헤드는 오라클 테이프의 첫 번째 사각형으로 이동한다.
오라클 머신의 상태가 응답으로 변경됨.

따라서 ASC 상태로 변경하는 효과는 오라클 테이프에 기록된 문제 인스턴스에 대한 솔루션을 한 번에 받는 것이다.

대체 정의

위에 제시된 정의에는 많은 대체 정의가 있다. 이들 중 상당수는 오라클이 의사결정 문제를 해결하는 경우에 특화되어 있다. 이 경우:

일부 정의는 오라클 테이프에 답을 쓰는 대신 ASC 상태 외에 YES와 NO라는 두 개의 특수 상태를 가진다. 오라클과 상담할 때 오라클 테이프의 내용이 오라클 세트에 있으면 다음 상태가 YES로, 오라클 세트에 없으면 NO로 선택한다(Adachi 1990:111).
일부 정의는 별도의 오라클 테이프를 지지한다. 오라클 상태를 입력하면 테이프 기호가 지정된다. 오라클은 이 테이프 기호가 작업 테이프에 나타나는 횟수로 쿼리된다. 이 숫자가 오라클 집합에 있으면 다음 상태는 YES 상태, 그렇지 않으면 NO 상태(Rogers 1967:129)이다.
또 다른 대체 정의는 오라클 테이프를 읽기 전용으로 만들고 ASC 및 Response 상태를 완전히 제거한다. 기계를 시작하기 전에 Oracle 테이프에 기호 0과 1을 사용하여 Oracle 세트의 표시기 기능을 기록한다. 그러면 기계는 오라클 테이프의 정확한 사각형으로 스캔하여 그곳에 있는 값을 읽음으로써 오라클을 쿼리할 수 있다(Soare 1987:47, Rogers 1967:130).

이러한 정의는 Turing 계산성의 관점에서 동등하다. 함수는 이러한 정의들 중 하나에서 Oracle로 계산되는 경우, 이 모든 정의에 따라 주어진 Oracle에서 Oracle로 계산된다. 그러나 계산 복잡성의 관점에서 정의는 동등하지 않다. 판 멜케벡의 것과 같은 정의는 일반적으로 자체 알파벳을 가지고 있을 수 있는 오라클 테이프를 사용하는 것이 필요하다.

오라클 시스템의 복잡성 클래스

언어 L에 대한 Oracle로 클래스 A의 알고리즘으로 해결할 수 있는 의사결정 문제의 복잡성 클래스를 A라고^L 한다. 예를 들어, P는^SAT 부울 만족도 문제에 대한 신탁이 있는 결정론적 튜링 기계에 의해 다항 시간 내에 해결 가능한 문제의 등급이다. 표기법^B A는 다음과 같은 정의를 사용하여 일련의 언어 B(또는 복잡도 클래스 B)로 확장될 수 있다.

A^{B}=\빅컵 _{L\in B}A^{L

일부 클래스 B에 대해 언어 L이 완료되면, A의 기계가 클래스 B의 완전성 정의에 사용되는 감소를 실행할 수 있다는 전제하에^L A=A^B. 특히 SAT는 다항 시간 단축에 관한 NP-완전이기 때문에 P^SAT=P^NP. 단, A = DLOGTIME이면 A가^SAT A와^NP 같지 않을 수 있다(위의 A $A^{B}$ $A^{B}$ ${\$ A $^{B}$ 의 정의는 완전히 표준이 아니다). 시간 및 공간 계층 구조의 증명과 같은 일부 맥락에서 클래스 $A$ ${\displaystyle$ A $}$ 을(를) 정의하는 추상 시스템이 하나의 언어에 대해 하나의 $A$ 오라클에만 액세스할 수 있다고 가정하는 것이 더 유용하다. 이 맥락에서 복잡도 $클래스$ B ${\displaystyle A$ $^{B$ $}$ 가 $A$ ${\displaystyle$ A $}$ 에서 사용할 수 있는 감소와 관련하여 완전한 문제가 없는 $B$ 경우 A $A^{B}$ ${\$ A}}을(를) 정의하지 않는다 $A^{B}$ . $A$

NP ⊆ P로^NP 이해되지만 NP^NP, P^NP, NP, P가 동일하냐는 문제는 기껏해야 잠정적인 것으로 남아 있다. 그것은 그들이 다르다고 믿어지고, 이것은 다항식 계층의 정의로 이어진다.

Oracle 기계는 Oracle A에 대한 P와^A NP의^A 관계를 고려하여 복잡도 등급 P와 NP의 관계를 조사하는 데 유용하다. 특히 P^A=NP와^A P^B andNP^B(베이커, 길, 솔로베이 1975년)가 존재하는 것으로 나타났다. 상대화(즉, 신탁의 추가에 영향을 받지 않음)하는 증명 기법이 P = NP 질문에 대답하지 않기 때문에 P = NP 질문이 양방향 모두 상대화한다는 사실은 이 질문에 대한 대답이 어렵다는 증거로 받아들여진다. 대부분의 입증 기법은 상대화한다.

모든 가능한 웅변(무한 집합) 중에서 임의로 신탁을 선택하는 경우를 생각할 수 있다. 이 사례에서^A 확률 1, P^A (NP(Bennett and Gill 1981). 질문이 거의 모든 웅변에서 진실일 때, 그것은 임의의 신탁에서 진실이라고 한다. 이러한 용어 선택은 임의의 웅변은 확률 0 또는 1의 문구를 지지한다는 사실에 의해 정당화된다. (이는 Kolmogorov의 제로 원 법칙에서 따온 것이다.) 이는 P≠NP라는 문장이 임의의 신탁에 대해서는 사실일 수 있으나 일반 튜링 기계에 대해서는 거짓일 수 있으므로, 예를 들어 임의의 신탁 A에 대해서는 IP^A≠PSPACE가^A 거짓이지만 IP = PSPACE(Chang et al., 1994)라는 약한 증거일 뿐이다.

오라클스 및 중지 문제

정지 문제에 대한 신탁을 가진 기계는 특정 튜링 기계가 특정 입력에 대해 정지할지 여부를 결정할 수 있지만 일반적으로 자기 자신과 동등한 기계가 정지할지는 결정할 수 없다. 이것은 기계들의 계층을 형성하는데, 각각은 더 강력한 중단 오라클과 더 어려운 중단 문제를 가지고 있다. 이 기계의 계층 구조는 산술적 계층 구조를 정의하는 데 사용될 수 있다(Börger 1989).

암호화에 대한 응용 프로그램

암호학에서는 해시함수가 사용되는 암호 프로토콜의 보안을 위한 인수를 하기 위해 오라클을 사용한다. 프로토콜에 대한 보안 감소는 해시함수 대신에 임의의 오라클이 각 쿼리에 대해 무작위적으로나 일관적으로 응답하는 경우에 주어진다. 해시함수처럼, 공격자를 포함한 모든 당사자가 오라클을 이용할 수 있다고 가정한다. 그러한 증거는 공격자가 보안 감소의 핵심에서 어려운 문제를 해결하지 않는 한, 프로토콜의 파괴를 위해 해시함수의 어떤 흥미로운 속성을 이용해야 한다는 것을 보여준다; 그들은 해시함수를 블랙박스(즉, 랜덤 오라클)로 취급할 수 없다.

참고 항목

참조

아케오 아다치, 연산 이론의 기초, 옴샤, 1990.
T. P. 베이커, J. 길, R. 솔로베이. P =? NP 질문의 상대화. SIAM 컴퓨팅 저널 4(4): 431-442(1975)
C. H. 베넷, J. 길. 랜덤 오라클 A에 대해 P^A != NP^A != 확률^A 1. SIAM 컴퓨팅 저널, 10(1): 96-113(1981)
에곤 뵈거. "컴퓨팅 능력, 복잡성, 논리" 노스홀랜드, 1989년
리처드 창, 베니 초르, 오드 골드리히, 쥬리스 하트마니스, 요한 헤스타드, 데스 란잔, 판카즈 로하트기. 랜덤 오라클 가설은 거짓이다. 컴퓨터 및 시스템 과학 저널, 제49권, 제1권 24~39호 1994년 8월. ISSN 0022-0000. http://citeseer.ist.psu.edu/282397.html
마틴 데이비스 편집장: 1965년 뉴욕 래번 프레스, 1965년 불해독성 제안, 불해독성 문제 및 계산 가능한 기능에 대한 불해독성 기본 논문. 튜링의 논문은 이 권에 있다. 논문에는 괴델, 처치, 로서, 클레인, 포스트 등이 있다.
크리스토스 파파디미트리오우 계산 복잡성. 애디슨 웨슬리, 1994년 제14.3절: 오라클레스, 페이지 339–343.
Hartley Rogers, Jr. McGraw-Hill, 1967년, 재귀적 기능과 유효 계산성 이론.
마이클 시퍼. 계산 이론 소개. PWS 출판, 1997. ISBN 0-534-94728-X. 9.2: 상대화, 페이지 318–321.
로버트 1세 소어, 반복적으로 열거할 수 있는 세트와 도, 수학 논리에서의 관점, 스프링거, 1987.
앨런 튜링, 서수, 프로크에 기초한 논리 체계 런던 수학. Socc, 45, 1939년
Dieter van Melkebeek, Computer Complexity의 Randomness and Completence, Computer Science 1950, Springer, 2000.

Search