ACC0
ACC0
ACC라고도 불리는 ACC는0 이론 컴퓨터 과학 분야인 회로 복잡성에 정의된 계산 모델과 문제의 한 종류다.클래스는 일정 깊이 "대체 회로"의 클래스 AC를0 카운트할 수 있는 기능으로 증가시킴으로써 정의된다. 약어 ACC는 "카운터가 있는 AC"[1]를 의미한다.구체적으로, 모듈로를 고정 정수로 계산하는 관문을 포함하여 무한 팬인 게이트의 다항식 크기의 일정한 깊이 회로로 해결할 수 있다면, 문제는 ACC에0 속한다.ACC는0 어떤 해결 가능한 단면체의 계산에 해당한다.이 수업은 이론 컴퓨터 과학에서 매우 잘 연구되고 있는데, 이는 대수적 연결성, 그리고 소위 회로 하한이라고 불리는 계산 불가능성이 증명될 수 있는 가장 큰 콘크리트 컴퓨터 모델들 중 하나이기 때문이다.
정의들
비공식적으로, ACC는0 일정한 깊이와 다항식 크기의 부울 회로에 의해 실현된 연산 클래스를 모델링한다. 여기서 회로 게이트에는 어떤 고정된 상수로 참 입력 수를 계산하는 "모듈식 카운팅 게이트"가 포함된다.
만약 그것이 회로 C1, C2,..., Cnn의 모든 회로의 깊이 일정한 경우, Cn의 크기는 다항 함수와 입력 필요한 가족 계산할 더욱 공식적으로, 언어 AC0[m]고, 그 회로는 그들이 연계하여 사용하고 괴리 컴퓨팅 무한한 팬 인 다음의 문:AND게이트와 OR게이트를 사용하여 해당한다.inputs; 단일 입력의 부정을 계산하는 관문과 입력 1s의 수가 m의 배수인 경우 1을 계산하는 무제한 팬인 MOD-m 관문을 계산한다.언어는 ACC에0 속하면 ACC에0 속한다.
일부 텍스트에서 ACC는i ACC가 가장 낮은 레벨에서 ACC가0 있는 회로 클래스의 계층 구조를 말하며, ACC의i 회로는 깊이 O(logni)와 다항식 크기를 갖는다.[1]
등급 ACC는0 모노이드에 대한 불균일 결정론적 유한 자동자(NUDFA)의 계산 측면에서도 정의될 수 있다.이 틀에서 입력은 고정된 모노이드로부터의 요소로 해석되며, 입력 요소의 생산물이 주어진 모노이드 요소 리스트에 속할 경우 입력은 받아들여진다.ACC0 클래스는 하위 그룹으로서 확인할 수 없는 그룹을 포함하지 않는 모노이드에 대해 NUDFA에 의해 수락된 언어군이다.[2]
계산력
ACC0 등급은 AC를0 포함한다.단일 MOD-2 게이트가 패리티 함수를 계산하기 때문에 이 포함은 엄격하며, AC에서는0 계산이 불가능한 것으로 알려져 있다.보다 일반적으로 MODm 함수는 m이 p의 힘이 아니면 prime p에 대해 AC0[p]로 계산할 수 없다.[3]
ACC0 등급은 TC에0 포함되어 있다.ACC는0 입력의 과반수 기능을 계산할 수 없을 것으로 추측되지만(즉, TC에0 포함이 엄격하다) 2018년 7월 현재 미해결 상태로 남아 있다.
ACC의0 모든 문제는 깊이 2의 회로로 해결할 수 있으며, 입력에 다변량 팬인 AND 게이트가 있고, 단일 게이트 컴퓨팅 대칭 함수에 연결된다.[4]이러한 회로를 SYM 회로라고+ 한다.그 증거는 토다의 정리 증명 사상을 따른다.
윌리엄스(2011년)는 ACC가0 NEXPTIME을 포함하지 않는다는 것을 증명한다. 그 증명에는 시간 계층 정리, IP = PSPACE, 디랜도메이션, SYM+ 회로를 통한 ACC의0 표현 등 복잡성 이론에 많은 결과가 사용된다.[5]머레이&윌리엄스(2018)는 이 경계를 개선하고 ACC가0 NQP(nondeterministic Quasipolynormal time)를 포함하지 않는다는 것을 증명한다.
LOGTIME-uniform ACC0 회로는 영구적인 계산이 불가능한 것으로 알려져 있어 복잡도 등급 PP가 LOGTIME-uniform ACC에0 포함되어 있지 않음을 의미한다.[6]
메모들
- ^ a b 볼머(1999), 페이지 126
- ^ 테리엔(1981), 바링턴&테리엔(1988)
- ^ 라즈보로프(1987), 스몰렌스키(1987)
- ^ 베이겔&타루이 (1994년)
- ^ 아로라의 부록 바락 교과서
- ^ 앨렌더 & 고어(1994)
참조
- Allender, Eric (1996), "Circuit complexity before the dawn of the new millennium", 16th Conference on Foundations of Software Technology and Theoretical Computer Science,Hyderabad, India, December 18–20, 1996 (PDF), Lecture Notes in Computer Science, vol. 1180, Springer, pp. 1–18, doi:10.1007/3-540-62034-6_33
- Allender, Eric; Gore, Vivec (1994), "A uniform circuit lower bound for the permanent" (PDF), SIAM Journal on Computing, 23 (5): 1026–1049, doi:10.1137/S0097539792233907
- Barrington, D.A. (1989), "Bounded-width polynomial-size branching programs recognize exactly those languages in NC1" (PDF), Journal of Computer and System Sciences, 38 (1): 150–164, doi:10.1016/0022-0000(89)90037-8.
- Barrington, David A. Mix (1992), "Some problems involving Razborov-Smolensky polynomials", in Paterson, M.S. (ed.), Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990., London Mathematical Society Lecture Notes Series, vol. 169, pp. 109–128, ISBN 0-521-40826-1, Zbl 0769.68041.
- Barrington, D.A.; Thérien, D. (1988), "Finite monoids and the fine structure of NC1", Journal of the ACM, 35 (4): 941–952, doi:10.1145/48014.63138
- Beigel, Richard; Tarui, Jun (1994), "On ACC", Computational Complexity, 4 (4): 350–366, doi:10.1007/BF01263423.
- Clote, Peter; Kranakis, Evangelos (2002), Boolean functions and computation models, Texts in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, ISBN 3-540-59436-1, Zbl 1016.94046
- Razborov, A. A. (1987), "Lower bounds for the size of circuits of bounded depth with basis {⊕,∨}", Math. Notes of the Academy of Science of the USSR, 41 (4): 333–338.
- Smolensky, R. (1987), "Algebraic methods in the theory of lower bounds for Boolean circuit complexity", Proc. 19th ACM Symposium on Theory of Computing, pp. 77–82, doi:10.1145/28395.28404.
- Murray, Cody D.; Williams, Ryan (2018), "Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP", Proc. 50th ACM Symposium on Theory of Computing, pp. 890–901, doi:10.1145/3188745.3188910, hdl:1721.1/130542
- Thérien, D. (1981), "Classification of finite monoids: The language approach", Theoretical Computer Science, 14 (2): 195–208, doi:10.1016/0304-3975(81)90057-8.
- Vollmer, Heribert (1999), Introduction to Circuit Complexity, Berlin: Springer, ISBN 3-540-64310-9.
- Williams, Ryan (2011), "Non-uniform ACC Circuit Lower Bounds" (PDF), IEEE Conference on Computational Complexity: 115–125, doi:10.1109/CCC.2011.36, ISBN 978-1-4577-0179-5.