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

NEXP ⊄ ACC⁰ — 빠른 알고리즘이 하한을 낳는다

Ryan Williams 는 비결정적 지수 시간(NEXP)에 다항 크기 ACC⁰ 회로로 풀 수 없는 문제가 있음을 증명했다. 회로의 충족 가능성을 전수 조사보다 조금 빨리 푸는 알고리즘에서 하한을 끌어내는 방법이며, Murray–Williams 가 이를 비결정적 준다항 시간으로 끌어내렸다. 이 정리가 말하는 것과 말하지 않는 것을 구별한다.

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

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

Ryan Williams 는 비결정적 지수 시간(NEXP)에 다항 크기 ACC⁰ 회로로 풀 수 없는 문제가 있음을 증명했다. 이 글은 그 진술과 「빠른 알고리즘에서 하한을 끌어내는」 증명의 얼개, 후속 결과를 보고, 이 정리가 말하는 것과 말하지 않는 것을 구별한다.

정확한 진술

ACC⁰ 는 AND, OR, NOT 과 MOD-m 게이트로 이루어지고, 깊이가 상수이며 크기가 다항식인 회로들로 계산되는 언어의 클래스다. MOD-m 게이트는 입력에 든 1 의 개수를 m 으로 나눈 나머지가 0 인지 알려 주며, m 은 1 보다 큰 임의의 상수다. 게이트가 받는 입력 수에는 제한이 없다. Williams 의 논문은 위첨자 없이 ACC 라고 쓴다. 회로는 비균일(non-uniform)하다. 입력 길이마다 서로 아무 관계 없는 회로를 써도 된다는 뜻이다.

정리 1.1 증명됨

NTIME[2ⁿ] 에는 다항 크기의 비균일 ACC 회로를 갖지 않는 언어가 있다.

NTIME[2ⁿ] 은 NEXP 의 일부이므로 NEXP ⊄ ACC⁰ 가 따라 나온다. 논문에는 둘째 정리도 있다.

정리 1.2 증명됨

모든 d 와 m 에 대해 δ > 0 이 있어서, E^NP 의 어떤 언어는 깊이 d, 크기 2^(n^δ) 인 MOD-m 게이트 ACC 회로를 갖지 않는다.

E^NP 는 NP 오라클을 쓰며 2^(O(n)) 시간에 도는 결정적 기계로 판정되는 언어의 클래스다. 이 결과는 2011년 학회(CCC)에서 발표되었고 2014년 Journal of the ACM 에 실렸다.

이 정리가 말하는 것과 말하지 않는 것

말하는 것

말하는 것은 이것이다. 아주 큰 클래스 NEXP 안에, 아주 약한 회로인 ACC⁰ 로는 다항 크기에 계산할 수 없는 문제가 적어도 하나 있다.

말하지 않는 것

말하지 않는 것은 다음과 같다.

  • NP ⊄ ACC⁰ 를 말하지 않는다. NP 의 문제가 ACC⁰ 로 풀리지 않는다는 것은 여전히 증명되지 않았다.
  • NEXP ⊄ P/poly 도 말하지 않는다. NEXP 에 다항 크기 일반 회로가 없다는 것은 미해결이다.
  • ACC⁰ 보다 한 칸 위인 문턱 회로 클래스 TC⁰ 에 대해서도, Aaronson 의 2017년 개관 시점에 NEXP ⊄ TC⁰ 는 미해결이었다.
가로 세 칸, 세로 세 줄의 표 그림. 줄은 위에서부터 NEXP, NQP, NP 이고 칸은 왼쪽부터 ACC⁰, TC⁰, P/poly 다. 각 자리는 「그 줄의 클래스에는 그 칸의 회로로 풀 수 없는 문제가 있다」는 명제를 뜻한다. NEXP–ACC⁰ 자리는 증명됨(Williams, 2011 학회·2014 학술지), NQP–ACC⁰ 자리는 증명됨(Murray–Williams, 2018)으로 진하게 칠해져 있다. NP–ACC⁰, NEXP–TC⁰(2017 개관 시점), NEXP–P/poly 자리는 미해결이라고 적혀 있다. 맨 아래 오른쪽 NP–P/poly 자리는 목표로 표시되어 있다. 나머지 자리는 비어 있다.
「왼쪽 클래스 ⊄ 오른쪽 회로」 꼴의 명제들. 증명된 자리는 왼쪽 위에 몰려 있고, 목표인 NP ⊄ P/poly 는 맨 오른쪽 아래에 있다. 이 글에 나오지 않는 자리는 비워 두었다.

그런데도 큰 사건이었던 까닭은 그 전의 형편에 있다. 1987년의 Razborov–Smolensky 결과 뒤로, 나머지를 세는 수 m 이 6 같은 합성수이면 손쓸 방법이 없었다. Williams 의 초록에 따르면 EXP^NP 가 MOD-6 게이트만으로 된 깊이 3 의 다항 크기 회로를 갖는지조차 알려져 있지 않았다.

증명의 핵심 생각

증명은 「ACC 회로를 조금 빨리 다루는 알고리즘이 있으면 ACC 회로에 대한 하한이 나온다」는 연결 위에 서 있다.

  1. 알고리즘. 입력이 n 개이고 깊이가 d 인 ACC 회로가 주어졌을 때, 그 회로를 1 로 만드는 입력이 있는지를 2^(n − Ω(n^δ)) 시간에 판정한다(δ 는 d 에 따라 정해지는 양수). 2ⁿ 가지를 다 해 보는 것보다 조금 빠를 뿐이다. ACC 회로를 「차수 낮은 다항식에 함수 하나를 씌운 꼴」로 바꿔 쓸 수 있다는 1990년대의 구조 정리와, 빠른 직사각 행렬 곱셈 또는 동적 계획법이 재료다.
  2. 가정. NTIME[2ⁿ] 의 모든 언어가 다항 크기 ACC 회로를 갖는다고 하자.
  3. 압축. 그 가정 아래에서는 지수적으로 긴 3SAT 식의 충족 대입도 작은 ACC 회로 하나로 적을 수 있다. 비결정적 기계는 그 회로를 추측한 다음 1번의 알고리즘으로 맞는지 확인한다.
  4. 모순. 그러면 NTIME[2ⁿ] 의 모든 언어가 그보다 조금 짧은 비결정적 시간에 판정된다. 이는 비결정적 시간 위계 정리에 어긋난다.

Aaronson 은 이런 방식을 「아이러니한 복잡도 이론」이라 부른다. 무언가를 빨리 하는 알고리즘이 다른 무언가를 빨리 할 수 없다는 증명의 재료가 되기 때문이다. 그의 설명에 따르면 이 증명은 대각선 논법, 다항식 방법, 대화형 증명에서 나온 결과를 한데 묶으며, 상대화·대수화·자연 증명의 세 장벽에 걸리지 않는다. 자연 증명에 대해서는 단서가 붙는다. ACC⁰ 가 유사난수 함수를 계산할 만큼 센지 아직 모르므로, 애초에 넘어야 할 장벽이 거기 있는지부터 분명하지 않다.

후속 결과

  • Murray 와 Williams(2018)는 왼쪽 클래스를 크게 낮췄다. NQP 를 비결정적 준다항 시간 NTIME[n^(log^(O(1)) n)] 이라 할 때, 모든 고정된 k 에 대해 NQP 는 크기 n^(log^k n) 인 ACC∘THR 회로를 갖지 않는다. ACC∘THR 은 ACC 회로의 맨 아래층에 문턱 게이트를 허용한 것이다. 열쇠는 NP 와 NQP 에 대한 새로운 「쉬운 증거 보조정리(easy witness lemma)」다.
  • 이 방법으로 얻은 하한은 본래 「무한히 많은 입력 길이에서」 성립하는 꼴이었다. Chen, Lyu, Williams(2020)는 그런 하한 여럿을 「충분히 큰 모든 입력 길이에서」 성립하는 꼴로 고치는 길을 보였다. 그 결과로 E^NP 에는 충분히 큰 모든 길이에서 ACC⁰ 회로로 정답을 근사하는 것조차 어려운 함수가 있다.

P 대 NP 까지의 거리

목표인 NP ⊄ P/poly 와 나란히 놓으면 양쪽이 다 멀다. 왼쪽은 NEXP 에서 NQP 까지 내려왔지만 NP 에는 닿지 못했다. 오른쪽은 ACC⁰ 에 머물러 있다.

다만 나아갈 방향은 분명해졌다. 증명에서 ACC 의 성질이 쓰이는 곳은 1번의 알고리즘 한 군데뿐이다. 그래서 더 센 회로 클래스의 충족 가능성 문제를 전수 조사보다 조금만 빨리, 이를테면 충분히 큰 k 에 대해 2ⁿ/n^k 시간에 풀 수 있으면 그 클래스에 대한 NEXP 하한이 따라 나온다. 일반 회로에 대해 그런 알고리즘이 있다면 NEXP ⊄ P/poly 가 된다. Aaronson 은 이 결과가 1960년대식 위계 정리 하나를 적용하기까지 얼마나 많은 일을 해낼 수 있는지 보여 주었다고 평가한다.

출처

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

참고문헌 4

  • 부분 결과원문 확인
    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)
  • 부분 결과서지만 확인
    Almost-everywhere circuit lower bounds from non-trivial derandomizationL. Chen, X. Lyu, R. Williams · 2020FOCS 2020 (61st IEEE Annual Symposium on Foundations of Computer Science) · ECCC TR20-150 (2020)

    「무한히 많은 입력 길이에서」 성립하던 회로 하한 여럿을 「충분히 큰 모든 입력 길이에서」 성립하는 꼴로 고치는 길을 보인 논문이다. 2-4 의 NEXP ⊄ ACC⁰ 글이 후속 결과로 인용한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR20-150 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (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

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

아직 없습니다.