oracles가있는 회로 vs. oracles가있는 Turing 기계 질문 일지 모르지만 어디에서 볼 것인지는 분명하지

간단히 말해서 : 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 을 사용하도록 제한합니다 .

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



답변

관련 회로에 대한 가장 좋은 참고 자료는 Chris Wilson의 논문 “Relativized NC” http://www.springerlink.com/content/u727654246wu8662/

두 번째 조건 (O_n의 하향 폐쇄)은 P ^ O와 oracle O를 사용하는 균일 한 폴리 사이즈 회로 간의 동등성을 얻기 위해 필요하지 않습니다. 또한 세 번째 조건을 버려야합니다. 회로의 크기는 액세스를 방해합니다. 회로 크기보다 m 더 큰 경우 O_m.