회로 하한 — 제한된 회로에서의 성공, 일반 회로에서의 정체
P ⊆ P/poly 이므로 NP 문제에 초다항 크기의 회로가 필요함을 보이면 P ≠ NP 다. AC⁰·AC⁰[p]·단조 회로에서는 강한 하한이 증명되었지만, 제한이 없는 회로에 대해 알려진 하한은 3.1n 수준에 머물러 있다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
P ⊆ P/poly 이므로 NP 문제에 초다항 크기의 회로가 필요함을 보이면 P ≠ NP 다. 이 글은 AC⁰·AC⁰[p]·단조 회로에서 증명된 강한 하한과, 제한이 없는 회로에서 3.1n 수준에 머문 하한을 차례로 살펴본다.
왜 회로인가
다항 시간 알고리즘은 다항 크기 회로로 바꿀 수 있으므로 P ⊆ P/poly 다. 따라서
증명된 함의 NP 의 어떤 문제가 다항 크기 회로로 풀리지 않음, 곧 NP ⊄ P/poly 를 보이면 P ≠ NP 가 따라 나온다.
회로는 정의가 단순해서 조합론으로 분석하기 좋다는 것이 이 길의 매력이다. 다만 NP ⊄ P/poly 는 P ≠ NP 보다 강한 명제다. 둘을 잇는 가장 가까운 결과는 Karp–Lipton 정리로, NP ⊆ P/poly 라면 다항 계층이 둘째 단계로 무너진다.
출발점은 Shannon 의 1949년 계수 논법이다. n 변수 불 함수는 거의 모두 Ω(2ⁿ/n) 개의 게이트가 필요하다. 그러나 이 논법은 그런 함수를 하나도 구체적으로 주지 않는다. 회로 복잡도의 과제는 구체적인 함수에 대해 하한을 증명하는 것이다.
제한된 회로에서의 성공
1980년대의 전략은 회로에 제한을 걸어 하한을 얻고, 그 제한을 조금씩 푸는 것이었다.
| 회로 | 제한 | 알려진 하한 |
|---|---|---|
| AC⁰ | 깊이는 상수, 크기는 다항식, 게이트의 입력 수는 무제한 | 패리티 ∉ AC⁰ (Furst·Saxe·Sipser, Ajtai). 깊이 d 인 회로는 2Ω(n1/(d−1)) 개의 게이트가 필요 (Håstad) |
| AC⁰[p] | AC⁰ 에 「1 의 개수가 소수 p 의 배수인가」를 세는 MOD-p 게이트 추가 | 서로 다른 소수 p, q 에 대해 MOD-q ∉ AC⁰[p]. 다수결 ∉ AC⁰[p] (Razborov, Smolensky) |
| ACC⁰ | AC⁰ 에 임의의 상수 m 에 대한 MOD-m 게이트 추가 | NEXP ⊄ ACC⁰ (Williams, 2011 발표), NQP ⊄ ACC⁰ (Murray·Williams, 2018) |
| 단조 회로 | NOT 게이트 없음 | 클릭에 nΩ(log n) (Razborov, 1985), 곧 지수 하한으로 개선 (Alon·Boppana, 1987) |
중심 기법은 둘이다.
- 무작위 제한법(random restriction)
- 입력 대부분을 무작위로 고정하면 얕은 회로는 몇 개의 입력에만 의존하는 회로로 쪼그라들지만, 패리티는 남은 변수에 대해 여전히 패리티라는 점을 쓴다.
- 다항식 방법(polynomial method)
- AC⁰[p] 회로가 유한체 위의 차수 낮은 다항식으로 근사된다는 점을 쓴다.
단조 회로의 결과는 한때 큰 기대를 낳았다. 클릭은 NP-완전이므로, 단조 함수를 계산하는 일반 회로를 크기를 크게 늘리지 않고 단조 회로로 바꿀 수 있다면 P ≠ NP 다. 그러나 Razborov 자신이 P 에 속하는 완전 매칭 문제도 단조 회로로는 초다항 크기가 필요함을 보였고, Tardos 가 그 격차를 지수로 키웠다. NOT 게이트를 허용하느냐가 지수적인 차이를 만든다.
일반 회로에서의 정체
제한이 없는 회로로 오면 사정이 전혀 다르다. 구체적인 함수에 대해 알려진 하한은 선형 수준이다.
- 2입력 게이트를 모두 허용하는 회로: 3n − o(n) (N. Blum, 1984), (3 + 1/86)n − o(n) (Find·Golovnev·Hirsch·Kulikov, 2016), 3.1n − o(n) (Li·Yang, 2022).
- XOR 류의 게이트를 뺀 회로: 5n − o(n) (Iwama·Morizumi, 2002).
Blum 의 기록은 30년 넘게 깨지지 않았고, 그 뒤에도 상수가 3 에서 3.1 로 움직였을 뿐이다. Li 와 Yang 의 초록은 크기 10n 인 회로로 계산되지 않는 구체적인 함수가 있는지조차 모른다고 적는다.
상수 깊이 쪽의 경계도 뚜렷하다. m 이 소수의 거듭제곱이 아니면 다항식 방법이 통하지 않는다. 그래서 다수결 함수가 MOD-6 게이트를 쓰는 상수 깊이 다항 크기 회로로 계산되는지조차 모른다. 임계값 게이트를 쓰는 상수 깊이 회로 TC⁰ 에 대해서는 NEXP ⊄ TC⁰ 도 미해결이다.
회로의 사다리를 그리면 AC⁰ ⊆ AC⁰[p] ⊆ ACC⁰ ⊆ TC⁰ ⊆ NC¹ ⊆ P/poly 다(NC¹ 은 깊이가 O(log n) 인 다항 크기 회로다). 구체적이고 단순한 함수에 대한 초다항 하한은 AC⁰[p] 까지만 닿았고, ACC⁰ 에서는 NEXP 나 NQP 처럼 큰 클래스의 함수에 대해서만 얻었다. 게이트의 출력을 한 번씩만 쓰는 공식(formula)으로 좁히면 n3−o(1) 크기의 하한(Håstad)이 있지만, 회로로 오면 선형을 넘지 못한다.
![회로의 사다리 AC⁰ ⊆ AC⁰[p] ⊆ ACC⁰ ⊆ TC⁰ ⊆ NC¹ ⊆ P/poly. 구체적이고 단순한 함수에 대한 초다항 하한은 AC⁰ 과 AC⁰[p] 까지 닿았고, ACC⁰ 에서는 NEXP·NQP 같은 큰 클래스에 대해서만 얻었다. TC⁰ 에서는 NEXP ⊄ TC⁰ 도 미해결이고, 제한 없는 회로(P/poly)에서 구체적인 함수의 하한은 3.1n − o(n) 수준이다.](/_content/HypsvcCom.Svc.PvsNp.Ui/seed-img/2a/circuit-lower-bounds-2.svg)
왜 멈췄나
Aaronson 은 자연 증명 장벽이 진전이 멈춘 자리를 거의 정확히 설명한다고 본다. 위의 조합적 기법들은 무작위 함수에도 그대로 통하는 성질에 기대는데, 인수분해 같은 문제가 어렵다면 TC⁰ 만 되어도 유사난수 함수를 계산할 수 있다. 그러면 그런 논증은 TC⁰ 이상에서는 통할 수 없다. 2011년 이후의 ACC⁰ 하한은 조합적 분석만이 아니라 알고리즘 설계와 대각선 논법을 엮어 얻은 것으로, 「알고리즘에서 하한으로」 글에서 다룬다.
출처
서지 사항은 DOI 등록 정보·Math-Net.Ru·ECCC 기록으로 확인했고, 1980년대 결과의 내용은 Sipser 1992 §3.5–3.7 과 Aaronson 2017 §5.2, §6.1.1, §6.2.2–6.2.5 로 확인했다.
- M. Sipser, "The History and Status of the P versus NP Question", STOC 1992, 603–618.
- S. Aaronson, "P =? NP", 저자 공개본(2017).
- C. E. Shannon, "The Synthesis of Two-Terminal Switching Circuits", Bell System Tech. J. 28(1), 59–98 (1949).
- R. M. Karp, R. J. Lipton, "Some Connections between Nonuniform and Uniform Complexity Classes", STOC 1980, 302–309.
- M. Furst, J. B. Saxe, M. Sipser, "Parity, Circuits, and the Polynomial-Time Hierarchy", Math. Systems Theory 17(1), 13–27 (1984); FOCS 1981.
- M. Ajtai, "Σ¹₁-Formulae on Finite Structures", Ann. Pure Appl. Logic 24(1), 1–48 (1983).
- J. Håstad, "Almost Optimal Lower Bounds for Small Depth Circuits", STOC 1986, 6–20.
- A. A. Razborov, "Lower Bounds on the Monotone Complexity of Some Boolean Functions", Dokl. Akad. Nauk SSSR 281(4), 798–801 (1985).
- N. Alon, R. B. Boppana, "The Monotone Circuit Complexity of Boolean Functions", Combinatorica 7(1), 1–22 (1987).
- É. Tardos, "The Gap between Monotone and Non-Monotone Circuit Complexity Is Exponential", Combinatorica 8(1), 141–142 (1988).
- A. A. Razborov, "Lower Bounds on the Size of Bounded Depth Circuits over a Complete Basis with Logical Addition", Mat. Zametki 41(4), 598–607 (1987).
- R. Smolensky, "Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity", STOC 1987, 77–82.
- N. Blum, "A Boolean Function Requiring 3n Network Size", Theoret. Comput. Sci. 28(3), 337–345. 내용은 Sipser 1992 §3.5 와 Li·Yang 2022 로 확인.
- K. Iwama, H. Morizumi, "An Explicit Lower Bound of 5n − o(n) for Boolean Circuits", MFCS 2002, 353–364. 내용은 Li·Yang 2022 서론과 Williams 2014 서론으로 확인.
- M. G. Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov, "A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function", FOCS 2016, 89–98. ECCC TR15-166 의 초록을 확인.
- J. Li, T. Yang, "3.1n − o(n) Circuit Lower Bounds for Explicit Functions", STOC 2022, 1180–1193. ECCC TR21-023 의 초록과 서론을 확인.
- R. Williams, "Nonuniform ACC Circuit Lower Bounds", J. ACM 61(1), 1–32 (2014). 저자 공개본의 초록과 서론을 확인.
- C. Murray, R. Williams, "Circuit Lower Bounds for Nondeterministic Quasi-Polytime", STOC 2018, 890–901. 저자 공개본의 초록을 확인.
출처·이용 조건: 직접 작성
참고문헌 18
- 개관원문 확인The history and status of the P versus NP questionMichael Sipser · 1992STOC 1992 (Proceedings of the 24th Annual ACM Symposium on Theory of Computing), 603–618쪽
P 대 NP 문제의 뿌리와 1992년까지의 연구 상황을 정리한 개관 논문이다. 문제의 의의와 역사, 대각선 논법과 회로 복잡도(얕은 회로·단조 회로)로 이어진 시도들을 차례로 설명한다. 부록에는 괴델이 폰 노이만에게 보낸 편지 전문의 영문 번역이 실려 있다. 30여 년 전 글이지만 큰 그림을 잡으려는 입문·중급 독자에게 여전히 좋다. ACM 디지털 도서관으로 연결된다.
확인:공개 사본으로 본문과 부록(괴델 편지의 영문 번역 포함)을 읽음. 연결한 ACM 디지털 도서관 주소의 서지는 DOI 등록 기록으로 확인. - 개관원문 확인P =? NPScott Aaronson · 2017ECCC TR17-004 (2017년 1월 8일 공개) · 책 Open Problems in Mathematics (John Forbes Nash Jr., Michael Th. Rassias 엮음, Springer, 2016), 1–122쪽에 실린 글
P 대 NP 문제의 의미와 알려진 결과, 장벽, 접근 전반을 120여 쪽에 정리한 개관이다. 수학·과학·공학 배경의 넓은 독자를 겨냥해, 왜 P ≠ NP 라고 믿는지, 왜 증명이 어려운지, 지난 반세기에 무엇이 진전되었는지를 저자의 관점과 함께 설명한다. 상대화·자연 증명·대수화 장벽과 GCT 까지 다루므로, 이 서비스의 2부를 한 편으로 깊이 읽고 싶은 독자에게 가장 먼저 권한다.
확인:저자 공개본(2017년 판)을 열어 인용한 절들을 읽음. - 부분 결과서지만 확인The Synthesis of Two-Terminal Switching CircuitsC. E. Shannon · 1949Bell System Technical Journal 28(1), 59–98쪽 (1949)
거의 모든 불 함수에 큰 회로가 필요함을 계수 논법으로 보인 논문이다. n 변수 불 함수는 거의 모두 Ω(2ⁿ/n) 개의 게이트가 필요하다는 결과로, 회로 복잡도의 출발점이다. 다만 그런 함수를 구체적으로 하나도 주지 않는다. 2-3 의 회로 하한 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Sipser 1992 와 Aaronson 2017 로 확인. - 부분 결과서지만 확인Some Connections between Nonuniform and Uniform Complexity ClassesRichard M. Karp, Richard J. Lipton · 1980STOC 1980 (Proceedings of the 12th Annual ACM Symposium on Theory of Computing), 302–309쪽
NP 가 다항 크기 회로를 가진다면 다항 위계가 둘째 층으로 무너짐을 보인 논문이다. NP ⊄ P/poly 와 P ≠ NP 를 잇는 가장 가까운 결과(Karp–Lipton 정리)의 원전이다. 1-1 의 「여러 얼굴」 글과 2-3 의 회로 하한 글이 인용한다.
확인:논문 본문은 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 정리의 진술은 Aaronson 2017 정리 26 과 Arora–Barak 공개 초고 정리 6.13 으로 확인. - 부분 결과서지만 확인Parity, circuits, and the polynomial-time hierarchyMerrick Furst, James B. Saxe, Michael Sipser · 1984Mathematical Systems Theory 17(1), 13–27쪽 (1984) · 학회 발표 FOCS 1981 (22nd Annual Symposium on Foundations of Computer Science), 260–270쪽
깊이가 상수인 회로로는 패리티 함수를 다항 크기에 계산할 수 없음을 보인 논문이다. 제한된 회로 모형에서 구체적인 함수의 하한을 얻은 초기 대표 결과이며, 회로 하한과 다항 위계의 오라클 분리 사이의 연결도 다룬다. 회로 복잡도 접근이 어디서 출발했는지 보려는 독자에게 권한다.
확인:원문은 열지 못함. 서지는 게시자 페이지와 Crossref 의 DOI 등록 기록으로, 내용은 Sipser 1992·Aaronson 2017·Håstad 학위 논문 1장으로 확인. - 부분 결과서지만 확인Σ¹₁-Formulae on Finite StructuresM. Ajtai · 1983Annals of Pure and Applied Logic 24(1), 1–48쪽 (1983)
Furst–Saxe–Sipser 와 독립적으로, 상수 깊이·다항 크기 회로가 패리티를 계산하지 못한다는 결론에 이른 논문이다. PARITY ∉ AC⁰ 의 두 원전 가운데 하나다. 2-1 의 연표, 2-3 의 회로 하한 글, 2-4 의 PARITY ∉ AC⁰ 글이 인용한다. 게시자(Elsevier) 페이지로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Håstad 학위 논문 1장과 Aaronson 2017 로 확인. - 부분 결과서지만 확인Almost optimal lower bounds for small depth circuitsJohan Håstad · 1986STOC 1986 (Proceedings of the 18th Annual ACM Symposium on Theory of Computing), 6–20쪽 · 확장판 Randomness and Computation (Advances in Computing Research 5, S. Micali 엮음, JAI Press, 1989), 143–170쪽
상수 깊이 회로가 패리티를 계산하려면 지수에 가까운 크기가 필요함을 보인 논문이다. 무작위로 변수 일부를 고정하면 「작은 OR 들의 AND」를 「작은 AND 들의 OR」로 바꿀 수 있다는 핵심 보조정리(전환 보조정리)가 여기서 나온다. 깊이 k 에서는 다항 크기로 되지만 깊이 k−1 에서는 지수 크기가 필요한 함수가 있음도 보인다. 회로 하한 기법을 직접 배우려는 독자에게 권한다.
확인:저자 공개본 주소를 열어 제목·저자·실린 곳을 확인했으나 본문을 읽었다는 기록은 없음. 내용은 Håstad 학위 논문 1장, Aaronson 2017, Arora–Barak 공개 초고 13장으로 확인. - 부분 결과원문 확인Lower bounds on the monotone complexity of some Boolean functionsAlexander A. Razborov · 1985Doklady Akademii Nauk SSSR 281(4), 798–801쪽 (1985, 러시아어) · 영문 번역 Soviet Mathematics Doklady 31, 354–357쪽 (1985)
NOT 을 쓰지 않는 단조 회로로는 클릭 문제를 다항 크기에 풀 수 없음을 증명한 논문이다. NP-완전 문제에 대한 초다항 회로 하한을 (단조 회로라는 제한 아래) 처음 얻어 큰 기대를 모았다. 다만 이 방법은 일반 회로로 넓혀지지 않았다. 연결한 것은 저자가 올린 영문 번역본이며, 러시아어 원문의 서지는 Math-Net.Ru(mathnet.ru/eng/dan9192)에 있다.
확인:저자 누리집의 영문 번역본을 열어 정리 2·정리 3 과 그 설명을 읽음. 러시아어 원문의 서지는 Math-Net.Ru 로 확인. - 부분 결과서지만 확인The Monotone Circuit Complexity of Boolean FunctionsN. Alon, R. B. Boppana · 1987Combinatorica 7(1), 1–22쪽 (1987)
Razborov 의 단조 회로 하한을 지수 크기로 끌어올린 논문이다. 클릭 문제를 푸는 단조 회로의 크기 하한을 다항식을 넘는 수준에서 지수 수준으로 강화했다. 2-3 의 회로 하한 글과 2-4 의 단조 회로 하한 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.2.2 와 Arora–Barak 공개 초고 13장으로 확인. - 부분 결과서지만 확인The Gap between Monotone and Non-Monotone Circuit Complexity Is ExponentialÉ. Tardos · 1988Combinatorica 8(1), 141–142쪽 (1988)
단조 회로와 일반 회로의 크기 차이가 지수적일 수 있음을 보인 두 쪽짜리 논문이다. 단조 회로 하한이 문제의 어려움이 아니라 단조 회로의 약함을 말해 줄 수 있음을 보여 준다. 2-3 의 회로 하한 글과 2-4 의 단조 회로 하한 글이 인용한다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.2.2 와 Arora–Barak 공개 초고 13장으로 확인. - 부분 결과서지만 확인Lower bounds on the size of bounded depth circuits over a complete basis with logical additionA. A. Razborov · 1987Matematicheskie Zametki 41(4), 598–607쪽 (1987, 러시아어) · 영문 번역 Mathematical Notes of the Academy of Sciences of the USSR 41(4), 333–338쪽 (https://doi.org/10.1007/BF01137685)
MOD-2 게이트를 허용한 상수 깊이 회로가 다수결을 계산하려면 지수 크기가 듦을 보인 논문이다. 회로를 차수 낮은 다항식으로 근사하는 다항식 방법의 출발점으로, Smolensky 가 이를 일반 소수로 넓혔다. 2-1 의 연표, 2-3 의 회로 하한 글, 2-4 의 PARITY ∉ AC⁰ 글이 인용한다. 연결한 Math-Net.Ru 페이지에 러시아어 원문의 서지가 있다.
확인:Math-Net.Ru 의 서지 페이지와 영문 번역의 DOI 등록 기록으로 서지를 확인. 내용은 Williams 2014 서론과 Aaronson 2017 로 확인. - 부분 결과서지만 확인Algebraic methods in the theory of lower bounds for Boolean circuit complexityRoman Smolensky · 1987STOC 1987 (Proceedings of the 19th Annual ACM Symposium on Theory of Computing), 77–82쪽
나머지 세기(MOD p) 게이트를 더한 상수 깊이 회로에 대해 대수적 방법으로 하한을 증명한 논문이다. 회로를 낮은 차수의 다항식으로 근사하는 방법(라즈보로프–스몰렌스키 방법)의 대표 논문으로, ACC⁰ 하한 문제의 배경을 이해하는 데 필요하다. 회로 복잡도를 공부하는 독자에게 권한다. ACM 디지털 도서관으로 연결된다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Williams 2014 서론과 Aaronson 2017 §6.2.4 로 확인. - 부분 결과서지만 확인A Boolean Function Requiring 3n Network SizeN. Blum · 1984Theoretical Computer Science 28(3), 337–345쪽 (DOI 등록 정보의 간행 연도는 1983, 인용 관행은 1984)
구체적인 불 함수에 대해 3n − o(n) 크기의 일반 회로 하한을 증명한 논문이다. 제한 없는 회로에 대한 하한이 선형 수준에 머물러 있음을 보여 주는 기록으로, 30년 넘게 깨지지 않았다. 2-3 의 회로 하한 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Sipser 1992 §3.5 와 Li–Yang 2022 로 확인. - 부분 결과서지만 확인An Explicit Lower Bound of 5n − o(n) for Boolean CircuitsK. Iwama, H. Morizumi · 2002Mathematical Foundations of Computer Science 2002, Lecture Notes in Computer Science, Springer, 353–364쪽
XOR 류의 게이트를 뺀 회로에 대해 5n − o(n) 크기의 하한을 증명한 논문이다. 일반 회로 하한이 선형 수준에 머물러 있음을 보여 주는 기록의 하나로, 2-3 의 회로 하한 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Li–Yang 2022 서론과 Williams 2014 서론으로 확인. - 부분 결과서지만 확인A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit FunctionM. G. Find, A. Golovnev, E. A. Hirsch, A. S. Kulikov · 2016FOCS 2016 (57th Annual IEEE Symposium on Foundations of Computer Science), 89–98쪽 · ECCC TR15-166 (2015)
구체적인 함수에 대한 일반 회로 하한을 (3 + 1/86)n − o(n) 으로 올린 논문이다. Blum 의 3n 기록을 30여 년 만에 넘어섰지만 여전히 선형 수준이다. 2-3 의 회로 하한 글이 인용한다. ECCC 공개본으로 연결한다.
확인:ECCC TR15-166 의 초록까지 확인. 본문을 읽었다는 기록은 없음. - 부분 결과원문 확인3.1n − o(n) Circuit Lower Bounds for Explicit FunctionsJ. Li, T. Yang · 2022STOC 2022 (Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing), 1180–1193쪽 · ECCC TR21-023 (2021)
구체적인 함수에 대한 일반 회로 하한을 3.1n − o(n) 으로 올린 논문이다. 2-3 의 글들이 일반 회로 하한의 현황으로 드는 값이며, 하한이 여전히 선형 수준임을 보여 준다. 초록은 크기 10n 인 회로로 계산되지 않는 구체적인 함수가 있는지조차 모른다고 적는다. ECCC 공개본으로 연결한다.
확인:ECCC TR21-023 공개본의 초록과 서론을 읽음. - 부분 결과원문 확인Nonuniform ACC Circuit Lower BoundsRyan Williams · 2014Journal of the ACM 61(1), 1–32쪽 (2014) · 학회 발표 CCC 2011 (26th Annual IEEE Conference on Computational Complexity), 115–125쪽
NEXP 의 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. 회로의 충족 가능성을 전수 조사보다 조금이라도 빨리 푸는 알고리즘을 만들면 회로 하한이 따라 나온다는 연결을 써서, 알고리즘 설계로 하한을 증명했다. 알려진 장벽들을 피한 드문 사례로 꼽힌다. 저자 누리집의 공개본으로 연결한다.
확인:저자 공개본(2012-07-31 판)을 열어 초록, 서론, 정리 1.1·1.2 를 읽음. - 부분 결과원문 확인Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQPCody Murray, Ryan Williams · 2018STOC 2018 (Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing), 890–901쪽 · 학술지판 SIAM Journal on Computing 49(5) (2020) · ECCC TR17-188 (2017)
비결정적 준다항 시간에 풀리는 문제 가운데 다항 크기 ACC⁰ 회로로는 풀 수 없는 것이 있음을 증명한 논문이다. williams-2014 의 NEXP 를 훨씬 작은 종류로 낮춰, NP 에 대한 하한 쪽으로 한 걸음 다가선 결과다. ACC⁰ 하한이 지금 어디까지 왔는지 확인하려는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:저자 공개본을 열어 초록과 서론을 읽음.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.