간단히 말해서 : oracles가있는 Turing 기계와 oracles가있는 균일 한 회로 제품군 간의 대응 관계는 무엇입니까? 주어진 오라클 튜링 머신에 대해 동일한 계산 모델을 얻기 위해 후자는 어떻게 정의됩니까?

이것은 기본적인 질문 일지 모르지만 어디에서 볼 것인지는 분명하지 않으며, 나는 나의 기초가 양질의 박격포를 사용하고 있는지 확인하는 것을 좋아하는 사람입니다. 표준 참조가 있으면 알려주십시오. (Papadimitriou의 책은 예를 들어, oracles가있는 회로를 전혀 설명하지 않는 것 같습니다.)

나의 작업 가설은 이것이다 : 오라클에 접근 할 수있는 균일 한 회로 패밀리 (예 : NP- 완전 문제 해결을 위해)는 다음과 같이 정의된다 :

• 하나는  각각의 회로 크기 n에 대해 하나 의 “오라클 게이트”O _n 의 무한 패밀리를 정의하며 , 각각은  일정한 상수 c에 대해 함수 f _n  : {0,1} ^cn → {0,1}을 계산합니다 .

• f를 함수 _N 오라클 게이트 O 의해 계산 _N 다음 의미에서 “균일”이어야 : 상관 없음 <N과 X  ∈ {0,1} ^N , 우리는 F가 필요 _없음을 ( X ) = F _N (0 ^{℃ ( N-n)}  x  ) — 즉, 오라클 게이트는 입력의 일관되고 확장 가능한 “인코딩”을 사용해야합니다.

• 하나는 균일 한 회로 패밀리를 정의하는데, 여기서 오라클 게이트는 회로에 허용 된 동작 중 하나이며, 입력 크기 n에 대한 회로가 게이트 O _n 을 사용하도록 제한합니다 .

위의 선택 중 일부는 일반성을 잃지 않고 임의로 수정 될 수 있다고 생각합니다. 내가 관심있는 것은 서신에 대한 참조 또는 표준 설명을 얻기 위해 위의 설명을 수정하는 방법에 대한 설명입니다.

답변