HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 2. P vs NP의 현재까지의 증명 노력들
  3. 2-3 주요 접근

알고리즘에서 하한으로 — Williams 의 방법

회로의 만족 가능성을 전수 탐색보다 조금만 빨리 푸는 알고리즘이 있으면 회로 하한이 따라 나온다. Williams 는 이 연결로 NEXP ⊄ ACC⁰ 를 증명했고, Murray 와 Williams 는 그것을 비결정적 준다항 시간 NQP 까지 내렸다.

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

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

회로의 만족 가능성을 전수 탐색보다 조금만 빨리 푸는 알고리즘이 있으면 회로 하한이 따라 나온다. 이 글은 Williams 가 이 연결로 NEXP ⊄ ACC⁰ 를 증명한 뼈대와, 그 뒤 NQP 까지 내려온 결과, 그리고 이 방법의 한계를 정리한다.

뒤집힌 관계

알고리즘을 찾는 일과 알고리즘이 없음을 보이는 일은 정반대로 보인다. Ryan Williams 는 2010년에 둘을 잇는 정리를 발표했다.

증명된 정리 다항 크기 회로의 만족 가능성 문제를 전수 탐색보다 조금만 빨리 푸는 알고리즘이 있으면 NEXP ⊄ P/poly 다.

Williams 2013

입력이 n 개인 회로에 대해 전수 탐색은 2ⁿ 가지를 다 해 본다. 요구되는 개선은 작다. 2ⁿ 을 n 의 어떤 초다항 함수로 나눈 시간이면 된다. 더 다듬은 형태(Williams, Santhanam·Williams)에서는 회로가 만족 불가능한 경우와 입력의 4분의 1 이상이 회로를 만족시키는 경우를 가려내기만 해도 된다. 이 둘은 무작위 표본으로는 쉽게 가려지므로, 표준적인 탈무작위화 가설 아래에서는 그런 결정적 알고리즘이 존재한다. 하한 증명에 필요한 것이 「있으리라 믿어지는 알고리즘」인 셈이다.

이 연결은 회로의 종류별로도 성립한다. ACC⁰ 나 TC⁰ 같은 클래스의 회로에 대해 만족 가능성을 그만큼 빨리 풀면, NEXP 가 그 클래스의 다항 크기 회로를 갖지 않는다는 결론이 나온다.

NEXP ⊄ ACC⁰ 증명의 뼈대

2011년 Williams 는 이 계획을 ACC⁰ 에서 실제로 완수했다. ACC⁰ 는 깊이가 상수인 다항 크기 회로에 임의의 상수 m 에 대한 MOD-m 게이트를 허용한 클래스다. 증명은 귀류법이다.

  1. NTIME(2ⁿ) 의 문제가 모두 다항 크기 ACC⁰ 회로를 가진다고 가정한다.
  2. Cook–Levin 정리의 정밀한 판으로, NTIME(2ⁿ) 계산을 「작은 회로가 그 진리표로 적어 주는 지수 크기의 3SAT 식」이 만족 가능한가라는 문제로 바꾼다.
  3. 쉬운 증거 보조정리(easy witness lemma; Impagliazzo·Kabanets·Wigderson)를 쓴다. NEXP ⊆ P/poly 이면 그런 식을 만족시키는 값의 배정도 작은 회로로 적을 수 있다.
  4. 새 알고리즘을 만든다. 깊이 d 인 ACC⁰ 회로의 만족 가능성을 2n − Ω(nδ) 시간에 푼다(δ > 0 은 d 에 따라 정해진다). ACC⁰ 의 함수가 차수 낮은 다항식의 값에 대한 함수로 표현된다는 1990년대의 구조 정리에, 빠른 행렬 곱 또는 동적 계획법을 더한다.
  5. 3 과 4 를 엮으면 「증거를 적은 작은 회로를 추측하고, 그것이 정말 증거인지를 2ⁿ 보다 조금 빨리 검사」할 수 있다. 그러면 NTIME(2ⁿ) 의 모든 문제가 NTIME(2ⁿ/nk) 에 풀리는데, 이는 비결정적 시간 계층 정리에 어긋난다.
귀류법의 흐름. 맨 위의 가정(NTIME(2ⁿ) 의 문제가 모두 다항 크기 ACC⁰ 회로를 가진다)에서, Cook–Levin 정리의 정밀한 판, 쉬운 증거 보조정리, ACC⁰ 회로의 만족 가능성을 빨리 푸는 새 알고리즘 세 재료가 모여 「증거를 적은 작은 회로를 추측하고 조금 빨리 검사」하는 단계가 된다. 그러면 NTIME(2ⁿ) 이 NTIME(2ⁿ/n^k) 에 들어가 비결정적 시간 계층 정리에 어긋나므로, 가정이 틀렸고 NEXP 는 다항 크기 ACC⁰ 회로를 갖지 않는다.
알고리즘에서 하한으로 — 빠른 만족 가능성 알고리즘이 귀류법의 열쇠가 된다.

얻은 결과는 둘이다(2011년 학회 발표, 2014년 학술지 게재).

증명된 정리 NEXP 는 다항 크기 ACC⁰ 회로를 갖지 않는다. 준다항 크기까지 조금 강화된다.

증명된 정리 ENP, 곧 NP 오라클을 쓰는 2O(n) 시간은 2no(1) 크기의 ACC⁰ 회로를 갖지 않는다.

Williams 2014

그 전에는 EXPNP 가 MOD-6 게이트만으로 된 깊이 3 의 다항 크기 회로를 갖는지조차 알려져 있지 않았다.

왜 NP 가 아니라 NEXP 일까. 이 논증은 「어떤 클래스가 작은 회로를 가진다」는 가정으로 그 클래스의 계층 정리를 어기는 구조다. 그러려면 그 작은 회로를 같은 클래스 안에서 손에 넣어야 한다. NEXP 는 비결정성으로 회로를 통째로 추측할 수 있지만, 더 작은 클래스에서는 이 대목이 막힌다. 병목은 쉬운 증거 보조정리가 지수 시간 클래스에서만 증명되어 있었다는 데 있었다.

그 뒤: 더 작은 클래스, 더 강한 하한

  • Murray·Williams (2018). 쉬운 증거 보조정리를 NP 와 NQP 로 내렸다. NQP 는 비결정적 준다항 시간 NTIME[nlogO(1) n] 이다. 그 결과 모든 k 에 대해 NQP 는 크기 nlogk n 인 ACC⁰∘THR 회로, 곧 맨 아래층에 임계값 게이트를 둔 ACC⁰ 회로를 갖지 않는다.
  • Chen (2019), Chen·Ren (2020). 최악의 경우 하한을 평균적 경우 하한으로 강화했다. Chen 은 NQP 안에, 다항 크기 ACC⁰ 회로로는 입력의 1/2 + 1/logc n 이상의 비율에서 맞힐 수 없는 언어가 있음을 보였다. Chen 과 Ren 은 그 비율을 1/2 + 2−loga n 으로 낮췄다.

장벽, 그리고 한계

Aaronson 은 이 증명이 알려진 세 장벽을 모두 넘는다고 평가한다. ACC⁰ 회로의 구조를 파고드는 알고리즘을 쓰므로 상대화도 대수화도 하지 않는다. 대각선 논법(시간 계층 정리)에 기대므로, ACC⁰ 에 자연 증명 장벽이 있다 해도 거기에 걸리지 않는다. 뜻밖의 알고리즘이 하한을 낳는 이런 흐름을 그는 「아이러니한 복잡도 이론(ironic complexity theory)」이라 부른다.

한계도 분명하다.

출처

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

참고문헌 8

  • 접근원문 확인
    Improving Exhaustive Search Implies Superpolynomial Lower BoundsR. Williams · 2013SIAM Journal on Computing 42(3), 1218–1244쪽 (2013) · 학회 발표 STOC 2010, 231–240쪽

    회로의 만족 가능성을 전수 탐색보다 조금만 빨리 푸는 알고리즘이 있으면 NEXP ⊄ P/poly 가 따라 나옴을 보인 논문이다. 「알고리즘에서 하한으로」라는 접근의 출발점이며, 이 연결을 ACC⁰ 에서 실제로 완수한 것이 williams-2014 다. 2-3 의 「알고리즘에서 하한으로」 글이 인용한다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 초록을 읽음. 정리의 다듬은 형태는 Aaronson 2017 정리 69 로 확인.
    원문 주소 (people.csail.mit.edu)
  • 부분 결과원문 확인
    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)
  • 부분 결과원문 확인
    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 공개본으로 연결한다.

    확인:저자 공개본을 열어 초록과 서론을 읽음.
    원문 주소 (eccc.weizmann.ac.il)
  • 부분 결과서지만 확인
    In Search of an Easy Witness: Exponential Time vs. Probabilistic Polynomial TimeR. Impagliazzo, V. Kabanets, A. Wigderson · 2002Journal of Computer and System Sciences 65(4), 672–694쪽 (2002) · 학회 발표 IEEE Conference on Computational Complexity 2001, 2–12쪽

    NEXP 가 다항 크기 회로를 가진다면 NEXP 문제의 증거도 작은 회로로 적을 수 있다는 「쉬운 증거 보조정리」의 원전이다. Williams 의 NEXP ⊄ ACC⁰ 증명이 이 보조정리를 쓴다. 2-3 의 「알고리즘에서 하한으로」 글이 인용한다.

    확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Murray–Williams 2018 서론과 Aaronson 2017 §6.4.2 로 확인.
    원문 주소 (doi.org)DOI 10.1016/s0022-0000(02)00024-7
  • 부분 결과서지만 확인
    On Uniformity and Circuit Lower BoundsR. Santhanam, R. Williams · 2014Computational Complexity 23(2), 177–205쪽 (2014)

    「알고리즘에서 하한으로」의 연결을 더 약한 알고리즘만으로도 성립하는 꼴로 다듬은 결과가 실린 논문이다. 회로가 만족 불가능한 경우와 입력의 상당 부분이 회로를 만족시키는 경우를 가려내기만 해도 회로 하한이 나온다는 형태로, 2-3 의 「알고리즘에서 하한으로」 글이 인용한다.

    확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 정리 69 로 확인.
    원문 주소 (doi.org)DOI 10.1007/s00037-014-0087-y
  • 부분 결과서지만 확인
    Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC CircuitsL. Chen · 2019FOCS 2019 (60th Annual IEEE Symposium on Foundations of Computer Science), 1281–1304쪽 · ECCC TR19-031 (2019)

    NQP 안에 다항 크기 ACC⁰ 회로로는 평균적으로도 맞히기 어려운 언어가 있음을 보인 논문이다. Murray–Williams 의 최악의 경우 하한을 평균적 경우 하한으로 강화했다. 2-3 의 「알고리즘에서 하한으로」 글이 후속 결과로 인용한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR19-031 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (eccc.weizmann.ac.il)
  • 부분 결과서지만 확인
    Strong Average-Case Circuit Lower Bounds from Non-trivial DerandomizationL. Chen, H. Ren · 2020STOC 2020 (Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing), 1327–1334쪽 · ECCC TR20-010 (2020)

    Chen(2019)의 평균적 경우 ACC⁰ 하한을 더 강한 수치로 개선한 논문이다. 다항 크기 ACC⁰ 회로가 NQP 의 언어를 맞힐 수 있는 입력 비율의 상한을 1/2 에 더 가깝게 낮췄다. 2-3 의 「알고리즘에서 하한으로」 글이 인용한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR20-010 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (eccc.weizmann.ac.il)
  • 개관원문 확인
    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)

하위 정보 0

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

아직 없습니다.