평균적 복잡도와 다섯 세계 — P ≠ NP 너머의 물음들
P ≠ NP 는 최악의 경우에 관한 명제이고, 암호에는 평균적으로 어려운 문제와 일방향 함수가 필요하다. Impagliazzo 는 이 가정들 가운데 어디까지가 참이냐에 따라 가능한 세계를 Algorithmica·Heuristica·Pessiland·Minicrypt·Cryptomania 다섯으로 나누었다.
화면·그림·수식 전수 점검(2026-10-07)으로 내용을 확인했습니다. 증명이 옳다는 뜻은 아닙니다.
P ≠ NP 는 최악의 경우에 관한 명제이고, 암호에는 평균적으로 어려운 문제와 일방향 함수가 필요하다. 이 글은 평균적 복잡도의 기본 개념과, Impagliazzo 가 가능한 세계를 다섯으로 나눈 지도를 소개한다.
최악의 경우만으로는 모자란다
P ≠ NP 는 최악의 경우에 관한 명제다. 어떤 알고리즘도 모든 입력을 빨리 풀지는 못한다는 뜻일 뿐, 대부분의 입력이 어렵다는 뜻은 아니다. 그런데 암호에는 「대부분의 입력」이 어려워야 한다. Aaronson 의 말대로, 해독하기 어려운 메시지가 존재한다는 이유로 암호를 광고한다면 웃음거리가 될 것이다.
평균적 복잡도(average-case complexity)가 이 물음을 다룬다. Levin 은 1986년 논문에서 문제 L 과 입력 분포 D 의 쌍 (L, D) 를 대상으로 삼아 「평균적으로 쉽다」의 정의와 환원을 주고, NP-완전성에 대응하는 완전 문제가 있음을 보였다. Impagliazzo 와 Levin 은 이 완전성을 효율적으로 표본을 뽑을 수 있는 모든 분포로 넓혔다.
최악과 평균이 같은 문제도 있기는 하다. 이산 로그 문제는 입력의 일부에서만 통하는 다항 시간 알고리즘이 있어도 모든 입력에서 통하는 알고리즘이 나온다. 그러나 NP-완전 문제에 대해서는 수십 년의 연구에도 그런 동치가 증명된 적이 없다.
암호 쪽의 핵심 개념은 일방향 함수(one-way function)다.
계산은 다항 시간에 되지만, 무작위 입력의 함숫값에서 원상을 찾는 일은 어떤 다항 시간 알고리즘도 무시할 수 없는 확률로 해내지 못하는 함수다.
일방향 함수가 있다는 것은 「풀이를 아는 채로 어려운 문제를 만들어 낼 수 있다」는 것과 같다. 유사난수 생성기, 비밀 키 암호, 전자 서명이 일방향 함수에서 만들어진다.
이 가정들 사이에는 다음 함의가 알려져 있고, 역방향은 모두 미해결이다.
알려진 함의 · 역방향은 미해결 공개 키 암호가 존재한다 ⇒ 일방향 함수가 존재한다 ⇒ NP 에 평균적으로 어려운 문제가 있다 ⇒ P ≠ NP
Impagliazzo 의 다섯 세계
Impagliazzo 는 1995년 글에서 이 사슬이 어디서 끊기느냐에 따라 우리가 살고 있을 수 있는 세계를 다섯으로 나누고 이름을 붙였다.
| 세계 | 성립하는 것 | 어떤 세계인가 |
|---|---|---|
| Algorithmica | P = NP, 또는 NP ⊆ BPP 처럼 그에 준하는 것 | 답을 검사할 수 있는 문제는 모두 자동으로 풀린다. 암호는 불가능하다. |
| Heuristica | NP 문제가 최악의 경우에는 어렵지만, 표본을 뽑을 수 있는 모든 분포에서 평균적으로는 쉽다 | 어려운 입력이 있기는 한데, 그것을 찾아내는 일이 어렵다. |
| Pessiland | 평균적으로 어려운 NP 문제는 있지만 일방향 함수는 없다 | 그가 「모든 세계 가운데 최악」이라 부른 곳. 어려운 문제는 많은데 암호에는 쓸 수 없다. |
| Minicrypt | 일방향 함수는 있지만 공개 키 암호는 불가능하다 | 비밀 키 암호, 서명, 유사난수는 가능하다. |
| Cryptomania | 공개 키 암호가 가능하다 | 미리 만난 적 없는 두 사람이 공개된 통신로만으로 비밀을 나눌 수 있다. 그가 현실에 가장 가깝다고 본 세계다. |
P vs NP 와의 관계
- P ≠ NP 의 증명은 Algorithmica 를 지울 뿐이다. 암호의 안전성은 그보다 강한 명제들에 걸려 있다.
- 세계 사이의 벽을 허물기 어려운 까닭도 일부 알려져 있다. 「P ≠ NP 이면 NP 에 평균적으로 어려운 문제가 있다」를 환원으로 증명하려 할 때, 질의를 미리 정해 두는 비적응적 블랙박스 환원으로는 다항 계층이 무너지지 않는 한 불가능하다(Feigenbaum·Fortnow, Bogdanov·Trevisan).
- 최근의 진전은 메타복잡도에서 왔다. Hirahara(2018)는 블랙박스가 아닌 환원으로 Heuristica 를 배제하려는 연구 계획을 내놓았다. Liu 와 Pass(2020)는 일방향 함수의 존재, 곧 Minicrypt 의 문턱을 시간 제한 콜모고로프 복잡도의 평균적 어려움으로 특징지었다.
- 자연 증명 장벽과의 긴장. 충분히 강한 유사난수 생성기가 있다면 자연 증명으로는 일반 회로에 대한 하한을 얻을 수 없다. 암호가 튼튼한 세계일수록 P ≠ NP 를 「자연스럽게」 증명하기는 어려운 셈이다.
출처
- R. Impagliazzo, "A Personal View of Average-Case Complexity", Proc. 10th Structure in Complexity Theory Conference, 134–147 (1995). 공개 사본에서 초록과 다섯 세계를 다룬 절 전체를 확인. 서지는 DOI 등록 정보로 확인.
- L. A. Levin, "Average Case Complete Problems", SIAM J. Comput. 15(1), 285–286 (1986). 서지는 DOI 등록 정보로, 내용은 Bogdanov·Trevisan 2006 §1.2.2, §3 으로 확인.
- R. Impagliazzo, L. A. Levin, "No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random", FOCS 1990, 812–821. 서지는 DOI 등록 정보로, 내용은 Bogdanov·Trevisan 2006 §1.1.5 로 확인.
- A. Bogdanov, L. Trevisan, "Average-Case Complexity", Found. Trends Theor. Comput. Sci. 2(1), 1–106 (2006). arXiv 공개본의 초록, §1.1, §1.2 를 확인.
- J. Feigenbaum, L. Fortnow, "Random-Self-Reducibility of Complete Sets", SIAM J. Comput. 22(5), 994–1005 (1993). 서지는 DOI 등록 정보로, 내용은 Bogdanov·Trevisan 2006 §1.1.6 으로 확인.
- A. Bogdanov, L. Trevisan, "On Worst-Case to Average-Case Reductions for NP Problems", SIAM J. Comput. 36(4), 1119–1159 (2006). 서지는 DOI 등록 정보로, 내용은 Bogdanov·Trevisan 2006 §1.1.6 으로 확인.
- J. Håstad, R. Impagliazzo, L. A. Levin, M. Luby, "A Pseudorandom Generator from any One-way Function", SIAM J. Comput. 28(4), 1364–1396 (1999). 서지는 DOI 등록 정보로, 내용은 Aaronson 2017 §5.3.1 과 Liu·Pass 2020 서론으로 확인.
- R. Impagliazzo, S. Rudich, "Limits on the Provable Consequences of One-way Permutations", STOC 1989, 44–61. 서지는 DOI 등록 정보로 확인. Impagliazzo 1995 는 「[IR] 이 상대화된 Minicrypt 를 준다」고 적는데, 그 참고문헌에는 [IR] 표지가 이 논문과 「준비 중」 원고 둘에 붙어 있다. 여기서는 출간된 이 논문을 적었다.
- T. Baker, J. Gill, R. Solovay, "Relativizations of the P =? NP Question", SIAM J. Comput. 4(4), 431–442 (1975). 서지는 DOI 등록 정보로, 상대화된 Algorithmica 라는 서술은 Impagliazzo 1995 로 확인.
- S. Hirahara, "Non-Black-Box Worst-Case to Average-Case Reductions within NP", FOCS 2018, 247–258. ECCC TR18-138 의 초록과 §1.1(다섯 세계와 함의의 사슬)을 확인.
- Y. Liu, R. Pass, "On One-way Functions and Kolmogorov Complexity", FOCS 2020, 1243–1254. arXiv 공개본의 초록과 서론을 확인.
- A. A. Razborov, S. Rudich, "Natural Proofs", J. Comput. System Sci. 55(1), 24–35 (1997). 저자 공개본의 정리 4.1 을 확인.
- S. Aaronson, "P =? NP", 저자 공개본(2017). §5.3, §5.3.1 을 확인.
출처·이용 조건: 직접 작성
참고문헌 13
- 개관원문 확인A personal view of average-case complexityRussell Impagliazzo · 1995Proceedings of Structure in Complexity Theory, Tenth Annual IEEE Conference (1995), 134–147쪽
평균적 복잡도 연구를 정리하면서 「다섯 세계」라는 분류를 내놓은 글이다. P 대 NP 의 답과 암호의 가능성에 따라 세상이 어떻게 달라지는지를 다섯 가지 세계로 나눠 설명한다. 문제의 답이 현실에서 무슨 뜻인지 알고 싶은 독자에게 권한다. 주소는 저자가 올린 PostScript 파일이라 전용 보기 프로그램이 필요하다.
확인:공개 사본(PDF)에서 초록과 다섯 세계를 다룬 절 전체를 읽음. 서지는 DOI 등록 기록으로 확인. - 접근서지만 확인Average Case Complete ProblemsL. A. Levin · 1986SIAM Journal on Computing 15(1), 285–286쪽 (1986)
문제와 입력 분포의 쌍을 대상으로 「평균적으로 쉽다」의 정의와 환원을 주고 완전 문제가 있음을 보인, 평균적 복잡도 이론의 출발점이다. 두 쪽짜리 논문이다. 2-3 의 평균적 복잡도 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Bogdanov–Trevisan 개관(2006) §1.2.2·§3 으로 확인. - 부분 결과서지만 확인No Better Ways to Generate Hard NP Instances than Picking Uniformly at RandomR. Impagliazzo, L. A. Levin · 1990FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 812–821쪽
Levin 의 평균적 경우 완전성을, 효율적으로 표본을 뽑을 수 있는 모든 분포로 넓힌 논문이다. 2-3 의 평균적 복잡도 글이 평균적 복잡도 이론의 기초로 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Bogdanov–Trevisan 개관(2006) §1.1.5 로 확인. - 개관원문 확인Average-Case ComplexityA. Bogdanov, L. Trevisan · 2006Foundations and Trends in Theoretical Computer Science 2(1), 1–106쪽 (2006) · arXiv:cs/0606037 (2021년 개정판)
평균적 복잡도 이론을 정리한 100여 쪽의 개관이다. Levin 의 완전성 이론과, 최악의 경우를 평균적 경우로 옮기는 환원의 한계를 다룬다. 2-3 의 평균적 복잡도 글이 여러 고전 논문의 내용을 이 개관으로 확인했다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본(2021년 개정판)의 초록과 §1.1·§1.2 를 읽음. - 부분 결과서지만 확인Random-Self-Reducibility of Complete SetsJ. Feigenbaum, L. Fortnow · 1993SIAM Journal on Computing 22(5), 994–1005쪽 (1993)
완전 문제의 무작위 자기 환원 가능성을 다뤄, 최악의 경우를 평균적 경우로 옮기는 비적응적 환원의 한계를 보인 논문이다. Bogdanov–Trevisan(2006)의 결과와 함께, 2-3 의 평균적 복잡도 글이 「세계 사이의 벽을 허물기 어려운 까닭」으로 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Bogdanov–Trevisan 개관(2006) §1.1.6 으로 확인. - 부분 결과서지만 확인On Worst-Case to Average-Case Reductions for NP ProblemsA. Bogdanov, L. Trevisan · 2006SIAM Journal on Computing 36(4), 1119–1159쪽 (2006) · 학회 발표 FOCS 2003, 308–317쪽
NP 문제의 최악의 경우 난해성을 평균적 난해성으로 옮기는 비적응적 환원이, 다항 위계가 무너지지 않는 한 불가능함을 보인 논문이다. Feigenbaum–Fortnow 의 결과를 잇는다. 2-3 의 평균적 복잡도 글이 「세계 사이의 벽을 허물기 어려운 까닭」으로 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Bogdanov–Trevisan 개관(2006) §1.1.6 으로 확인. - 부분 결과서지만 확인A Pseudorandom Generator from any One-way FunctionJ. Håstad, R. Impagliazzo, L. A. Levin, M. Luby · 1999SIAM Journal on Computing 28(4), 1364–1396쪽 (1999)
일방향 함수가 하나라도 있으면 유사난수 생성기를 만들 수 있음을 보인 논문이다. 일방향 함수에서 유사난수 생성기와 비밀 키 암호가 나온다는 서술의 근거로, 2-3 의 평균적 복잡도 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로, 내용은 Aaronson 2017 §5.3.1 과 Liu–Pass 2020 서론으로 확인. - 부분 결과서지만 확인Limits on the Provable Consequences of One-way PermutationsR. Impagliazzo, S. Rudich · 1989STOC 1989 (Proceedings of the 21st Annual ACM Symposium on Theory of Computing), 44–61쪽
일방향 치환만으로 증명할 수 있는 귀결에 한계가 있음을 보인 논문이다. Impagliazzo 는 1995년 글에서 이 결과가 「상대화된 Minicrypt」, 곧 일방향 함수는 있지만 공개 키 암호는 불가능한 오라클 세계를 준다고 적는다. 2-3 의 평균적 복잡도 글이 인용한다.
확인:원문은 확인하지 못함. 서지는 DOI 등록 기록으로 확인했고, 인용 관계는 Impagliazzo 1995 의 서술을 따름. - 장벽서지만 확인Relativizations of the P =? NP QuestionTheodore Baker, John Gill, Robert Solovay · 1975SIAM Journal on Computing 4(4), 431–442쪽 (1975)
P = NP 가 되는 오라클과 P ≠ NP 가 되는 오라클이 모두 있음을 보인, 상대화 장벽의 원전이다. 대각선 논법처럼 상대화되는 기법만으로는 P 대 NP 를 어느 쪽으로도 풀 수 없다는 첫째 장벽이 이 논문에서 나온다. 2-2 를 읽고 원문을 확인하려는 독자에게 권한다. SIAM 페이지로 연결되며 본문 열람에는 구독이 필요할 수 있다.
확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 정리 3.9 와 Aaronson 2017 정리 43 으로 확인. - 부분 결과원문 확인Non-black-box worst-case to average-case reductions within NPShuichi Hirahara · 2018FOCS 2018 (59th Annual IEEE Symposium on Foundations of Computer Science), 247–258쪽 · ECCC TR18-138 (2018)
NP 안의 문제에 대해, 블랙박스 방식의 한계를 넘는 「최악의 경우에서 평균적 경우로」의 환산을 처음 제시한 논문이다. 시간 제한을 둔 콜모고로프 복잡도와 최소 회로 크기를 근사하는 문제가 평균적으로 쉽다면 최악의 경우에도 쉽다는 것을 보인다. 메타 복잡도 접근의 대표 성과로, 평균적 복잡도와 다섯 세계를 공부하는 전문 독자에게 권한다. ECCC 공개본으로 연결한다.
확인:ECCC 공개본(TR18-138)의 초록과 서론(§1.1)을 읽음. - 부분 결과원문 확인On One-way Functions and Kolmogorov ComplexityY. Liu, R. Pass · 2020FOCS 2020 (61st Annual IEEE Symposium on Foundations of Computer Science), 1243–1254쪽 · arXiv:2009.11514
일방향 함수의 존재와 시간 제한 콜모고로프 복잡도의 평균적 어려움이 동치임을 증명한 논문이다. 암호의 기초 가정이 잘 연구된 계산 문제 하나의 어려움으로 특징지어진 첫 사례다. 2-1 의 연표와 2-3 의 접근 지도·메타복잡도·평균적 복잡도 글이 인용한다. arXiv 공개본으로 연결한다.
확인:arXiv 공개본의 초록과 서론을 읽음. - 장벽원문 확인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 등록 기록으로 확인. - 개관원문 확인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년 판)을 열어 인용한 절들을 읽음.
하위 정보 0
이 자료에 대한 질의 · 보완 · 반론 · 관련 자료 · 메모를 글이나 파일로 더합니다.
아직 없습니다.