HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-4 알려진 부분 결과

PARITY ∉ AC⁰ — 얕은 회로는 홀짝도 세지 못한다

층수가 상수이고 크기가 다항식인 회로(AC⁰)는 입력에 든 1 의 개수가 홀수인지 계산하지 못한다. Furst–Saxe–Sipser 와 Ajtai 가 처음 보였고 Håstad 의 전환 보조정리가 거의 최적의 하한을 주었다. Razborov 와 Smolensky 는 이를 나머지 게이트가 달린 회로로 넓혔다.

  • 중급
  • 관리자
  • 조회 0
  • AI 도움
검토 완료 내용을 확인했습니다. 증명이 옳다는 뜻이 아닙니다.

화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.

층수가 상수이고 크기가 다항식인 회로(AC⁰)는 입력에 든 1 의 개수가 홀수인지조차 계산하지 못한다. 이 글은 그 정확한 진술과 무작위 제한을 쓴 증명의 생각, Razborov–Smolensky 의 확장, 그리고 이 방법이 어디서 멈추는지를 본다.

정확한 진술

AC⁰ 는 다음 조건을 채우는 회로들의 모임으로 계산되는 언어의 클래스다. 입력 길이 n 마다 회로가 하나씩 있다. 게이트는 AND, OR, NOT 이며 AND 와 OR 는 입력을 몇 개든 받을 수 있다. 게이트 수는 n 의 다항식 이하이고, 입력에서 출력까지의 층수인 깊이(depth)는 n 과 상관없는 상수다.

PARITY 는 n 비트 입력에 든 1 의 개수가 홀수이면 1, 짝수이면 0 을 내는 함수다.

정리 증명됨

PARITY ∉ AC⁰.

Furst–Saxe–Sipser, Ajtai

정량적으로는 Håstad 의 결과가 표준이다. 깊이 d 인 회로가 PARITY 를 계산하려면 게이트가 2^(Ω(n^(1/(d−1)))) 개 있어야 한다. 깊이 d, 크기 n·2^(n^(1/(d−1))) 인 회로가 실제로 있으므로 거의 최적이다.

두 칸으로 된 회로 그림. 왼쪽은 깊이가 상수인 보기 회로로, 맨 아래 입력 x₁ 부터 x₈ 위에 OR 게이트 넷, 그 위에 AND 게이트 셋, 맨 위에 출력 OR 게이트 하나가 있고 게이트마다 입력을 여러 개 받는다. 오른쪽은 같은 회로에 무작위 제한을 건 모습이다. x₃ 과 x₈ 만 변수로 남고 나머지는 0 또는 1 로 고정된다. 1 이 들어온 OR 게이트는 상수 1, 0 이 모두 들어온 OR 게이트는 상수 0, 0 이 들어온 AND 게이트는 상수 0 이 되고, 회로 전체의 값은 x₃ 하나에만 의존하게 된다. 반면 PARITY 는 x₃ 과 x₈ 두 변수의 PARITY 의 부정으로 남는다.
왼쪽: 깊이가 상수인 보기 회로. 오른쪽: 같은 회로에서 x₃ 과 x₈ 만 남기고 나머지 변수를 고정한 모습. 회로는 변수 하나에만 의존하게 무너지지만 PARITY 는 남은 두 변수에 모두 의존한다. 게이트 몇 개만 그린 보기다.

뜻

PARITY 는 입력을 한 번 훑으며 비트 하나만 기억하면 풀린다. P 안에서도 아주 쉬운 문제다. 그런데 「층수가 고정된 회로」, 곧 단계 수가 상수인 병렬 계산으로 풀려고 하면 게이트가 지수적으로 필요해진다. 이 정리는 어떤 가정에도 기대지 않는 무조건적인 하한이다. Aaronson 은 AC⁰ 를 이해한 것을 1980년대 복잡도 이론의 큰 성과로 꼽는다.

증명의 핵심 생각 — 무작위 제한과 전환 보조정리

핵심 도구는 무작위 제한(random restriction)이다. 입력 변수 대부분을 골라 0 이나 1 로 무작위로 고정하고, 나머지 몇 개만 변수로 남겨 둔다.

  1. 입력을 많이 받는 AND 게이트는 0 이 하나만 들어와도 상수 0 이 된다. OR 게이트는 1 하나면 상수 1 이 된다. 그래서 무작위 제한을 걸면 큰 게이트는 높은 확률로 상수가 되어 사라진다.
  2. Håstad 의 전환 보조정리(switching lemma)는 이를 날카롭게 다듬은 것이다. 「작은 OR 들의 AND」인 깊이 2 회로에 무작위 제한을 걸면, 그 결과를 아주 높은 확률로 「작은 AND 들의 OR」로 바꿔 쓸 수 있다.
  3. 맨 아래 두 층의 AND 와 OR 를 이렇게 맞바꾸면 바로 위층과 같은 종류의 게이트가 이웃하게 되어 한 층으로 합쳐진다. 깊이가 1 줄어든다. 이것을 되풀이하면 회로는 남은 변수 몇 개에만 의존하는 아주 단순한 것으로 무너진다.
  4. 반면 PARITY 는 변수를 얼마나 고정하든 남은 변수들의 PARITY 이거나 그 부정이다. 결코 단순해지지 않는다. 그러므로 작은 회로는 PARITY 를 계산할 수 없다.

내력을 보면 무작위 제한이라는 생각은 Furst, Saxe, Sipser 가 들여왔다(학회 발표 1981년, 학술지 1984년). Ajtai 는 독립적으로 같은 결론에 이르렀다(논문은 1983년). 두 결과의 하한은 다항식을 조금 넘는 정도였는데, Yao 가 1985년에 지수 크기로 끌어올렸고 Håstad 가 1986년에 위의 거의 최적인 값을 얻었다. Håstad 는 이 일로 1994년 괴델상을 받았다.

Razborov–Smolensky 의 확장

AC⁰ 가 PARITY 를 못 한다면 PARITY 를 게이트로 그냥 주면 어떨까. AC⁰[m] 은 AC⁰ 회로에 MOD-m 게이트, 곧 입력에 든 1 의 개수가 m 의 배수인지 알려 주는 게이트를 더한 클래스다.

Razborov–Smolensky 증명됨

p 와 q 가 서로 다른 소수이면, 1 의 개수가 q 의 배수인지 묻는 함수는 AC⁰[p] 에 속하지 않는다. 깊이 d 인 회로에는 2^(Ω(n^(1/(2d)))) 개의 게이트가 필요하다. 다수결 함수도 AC⁰[p] 에 속하지 않는다.

Razborov, Smolensky, 1987

Razborov 는 MOD-2 게이트를 허용한 회로가 다수결을 계산하려면 지수 크기가 든다는 것을 보였고, Smolensky 가 일반 소수로 넓혔다. 증명 방법은 다항식 방법(polynomial method)이라 불린다. 이런 회로가 계산하는 함수는 원소가 p 개인 유한체 위의 차수 낮은 다항식으로 잘 근사된다. 그런데 q 에 대한 나머지 함수는 그런 다항식으로 근사되지 않는다.

P 대 NP 까지의 거리

이 결과들이 가르는 것은 AC⁰ 나 AC⁰[p] 와 P 다. 필요한 것은 NP 와 일반 다항 크기 회로(P/poly)를 가르는 일이다. 그 사이에는 AC⁰, AC⁰[p], ACC⁰, TC⁰, NC¹, P/poly 로 올라가는 사다리가 있고, 위의 두 방법은 둘째 칸에서 멈췄다.

오른쪽으로 갈수록 높아지는 여섯 칸 계단 그림. 칸은 왼쪽부터 AC⁰, AC⁰[p], ACC⁰, TC⁰, NC¹, P/poly 다. 첫 칸 아래에는 PARITY ∉ AC⁰ 와 무작위 제한, 둘째 칸 아래에는 q 에 대한 나머지와 다수결이 AC⁰[p] 에 속하지 않는다는 것과 다항식 방법이 적혀 있다. 둘째 칸과 셋째 칸 사이에 점선이 있고 두 방법은 둘째 칸에서 멈췄다고 적혀 있다. 맨 오른쪽 P/poly 칸 위에는 목표: NP 와 P/poly 를 가르기라고 적혀 있다.
AC⁰ 에서 P/poly 로 올라가는 회로 클래스의 사다리. 무작위 제한과 다항식 방법은 둘째 칸에서 멈췄다.

왜 멈췄는지에도 설명이 있다. Razborov 와 Rudich 는 무작위 제한이나 다항식 방법 같은 증명이 공통으로 지닌 성질을 「자연 증명(natural proofs)」이라 이름 붙였다. 그리고 유사난수 함수를 계산할 만큼 센 회로 클래스를 상대로는, 널리 믿는 암호학적 가정이 참인 한 그런 증명이 있을 수 없음을 보였다. AC⁰ 에서 통한 방법을 P/poly 까지 그대로 밀고 갈 수는 없다는 뜻이다.

출처

출처·이용 조건: 직접 작성

참고문헌 12

  • 개관원문 확인
    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년 판)을 열어 인용한 절들을 읽음.
    원문 주소 (www.scottaaronson.com)
  • 교과서원문 확인
    Computational Complexity: A Modern ApproachSanjeev Arora, Boaz Barak · 2009Cambridge University Press, 2009

    계산 복잡도 이론의 표준 교재로, 학부 고학년에서 대학원 입문 수준이다. P·NP 의 정의부터 회로 하한, 대화형 증명, PCP 정리, 탈무작위화, 자연 증명까지 이 서비스의 개념 대부분을 엄밀하게 다룬다. 정의와 증명을 제대로 공부하려는 독자에게 권한다. 연결한 것은 저자들이 운영하는 책 누리집으로, 초고와 정오표가 있다.

    확인:출판본이 아니라 저자 공개 초고(2007년 1월판)의 해당 장·절을 읽음.
    원문 주소 (theory.cs.princeton.edu)
  • 부분 결과원문 확인
    Computational limitations of small-depth circuitsJ. Håstad · 1987MIT 박사학위 논문 (제목·연도는 영어 위키백과 「Switching lemma」 문서의 참고문헌 표기를 따름)

    상수 깊이 회로의 한계를 다룬 Håstad 의 MIT 박사학위 논문이다. 1장이 Furst–Saxe–Sipser·Ajtai·Yao 의 하한과 그 내력, 전환 보조정리, 깊이 k 하한과 맞먹는 상한을 정리한다. 2-4 의 PARITY ∉ AC⁰ 글이 열지 못한 원 논문들 대신 이 공개본으로 내용을 확인했다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 1장을 읽음.
    원문 주소 (www.csc.kth.se)
  • 부분 결과원문 확인
    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 를 읽음.
    원문 주소 (people.csail.mit.edu)
  • 부분 결과서지만 확인
    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 로 확인.
    원문 주소 (www.mathnet.ru)
  • 장벽원문 확인
    Natural proofsAlexander A. Razborov, Steven Rudich · 1997Journal of Computer and System Sciences 55(1), 24–35쪽 (1997) · 학회 발표 STOC 1994 (Proceedings of the 26th Annual ACM Symposium on Theory of Computing), 204–213쪽

    알려진 회로 하한 증명들의 공통된 꼴을 「자연 증명」으로 정식화하고 그 한계를 보인 논문이다. 어려움에 관한 가정(강한 유사난수 생성기의 존재)이 참이라면 자연 증명으로는 일반 회로에 대한 초다항 하한을 증명할 수 없다는 둘째 장벽의 원전이다. 회로 하한 연구가 왜 막혔는지 이해하려는 독자에게 권한다. 게시자(Elsevier) 페이지로 연결된다.

    확인:저자 공개본을 열어 §2(정의), §3.1, §4(정리 4.1·4.3)를 읽음. 연결한 게시자 주소의 서지는 DOI 등록 기록으로 확인.
    원문 주소 (doi.org)DOI 10.1006/jcss.1997.1494
  • 보조 자료원문 확인
    Gödel PrizeWikipedia contributors · 2026영어 위키백과 (2026-10-05 확인)

    괴델상을 다룬 영어 위키백과 문서다. 2-4 의 PARITY ∉ AC⁰ 글이 Håstad 의 1994년 수상을 확인하는 보조 자료로 썼다.

    확인:위키백과 문서를 직접 열어 해당 서술을 확인(2차 자료).
    원문 주소 (en.wikipedia.org)
  • 부분 결과서지만 확인
    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장으로 확인.
    원문 주소 (link.springer.com)
  • 부분 결과서지만 확인
    Σ¹₁-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 로 확인.
    원문 주소 (doi.org)DOI 10.1016/0168-0072(83)90038-6
  • 부분 결과서지만 확인
    Separating the Polynomial-Time Hierarchy by OraclesA. C.-C. Yao · 1985FOCS 1985 (26th Annual Symposium on Foundations of Computer Science), 1–10쪽

    Furst–Saxe–Sipser 와 Ajtai 의 패리티 하한을 지수 크기로 끌어올린 논문이다. Håstad 가 이듬해 이를 거의 최적의 하한으로 다듬었다. 2-1 의 연표와 2-4 의 PARITY ∉ AC⁰ 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Håstad 학위 논문 1장과 Williams 2014 서론으로 확인.
    원문 주소 (doi.org)DOI 10.1109/sfcs.1985.49
  • 부분 결과서지만 확인
    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장으로 확인.
    원문 주소 (www.csc.kth.se)
  • 부분 결과서지만 확인
    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 로 확인.
    원문 주소 (doi.org)DOI 10.1145/28395.28404

하위 정보 0

이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.

아직 없습니다.