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

메타복잡도 — 어려움을 판정하는 일은 얼마나 어려운가

최소 회로 크기 문제(MCSP)와 시간 제한 콜모고로프 복잡도는 「함수나 문자열의 복잡도를 구하는 문제」다. 이 문제들의 복잡도를 묻는 메타복잡도는 자연 증명, 최악과 평균의 관계, 일방향 함수의 존재를 한데 잇는 고리로 다시 주목받고 있다.

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

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

메타복잡도는 「함수나 문자열의 복잡도를 구하는 문제」의 복잡도를 묻는다. 이 글은 대표 문제인 최소 회로 크기 문제(MCSP)와 시간 제한 콜모고로프 복잡도를 소개하고, 이 물음이 자연 증명, 최악과 평균의 관계, 일방향 함수의 존재를 한데 잇는 고리로 다시 주목받는 까닭을 정리한다.

복잡도를 묻는 문제의 복잡도

복잡도 이론은 문제가 얼마나 어려운지를 묻는다. 메타복잡도(meta-complexity)는 한 단계 위에서 묻는다. 문제가 얼마나 어려운지를 알아내는 일은 얼마나 어려운가? 대표 문제가 둘 있다.

최소 회로 크기 문제(Minimum Circuit Size Problem, MCSP)
n 변수 불 함수의 진리표(길이 2ⁿ)와 수 s 가 주어질 때, 그 함수를 계산하는 크기 s 이하의 회로가 있는가? 회로를 추측해 검사하면 되므로 NP 에 속한다.
콜모고로프 복잡도(Kolmogorov complexity)
문자열 x 를 출력하는 가장 짧은 프로그램의 길이 K(x) 다. K 는 계산할 수 없는 함수라서, 프로그램의 실행 시간을 t 로 묶은 Kt(x) 를 쓴다. t 가 다항식이면 「Kt(x) 가 k 이하인가」는 NP 문제다.

작은 회로는 큰 진리표의 짧은 설명이므로 둘은 가까운 사이다.

Allender 는 이 분야의 물음을 이렇게 풀어 쓴다. 복잡도 이론가들은 어떤 함수가 계산하기 어렵다는 것을 증명하기가 유난히 어렵다고 푸념한다. 정말 그런가? 이 물음을 정확한 수학 문제로 만든 것이 MCSP 의 복잡도다.

오래된 문제, 정해지지 않은 지위

MCSP 는 새 문제가 아니다. Sipser 에 따르면 1950년대 소련의 Yablonski 는 전수 탐색(러시아어로 perebor)을 논하면서 주어진 함수의 가장 작은 회로를 만드는 문제에 주목했다. Levin 의 1973년 논문도 불 함수의 최소화를 전수 탐색 문제의 첫 예로 든다.

그런데 MCSP 가 P 에 속하는지도, NP-완전인지도 아직 모른다. Kabanets 와 Cai(2000)는 양쪽이 다 어려운 까닭을 짚었다.

MCSP 가 P 에 속한다면

MCSP 가 P 에 속한다면 뜻밖의 귀결이 따른다. 예컨대 암호학적으로 안전한 유사난수 생성기가 존재할 수 없다.

MCSP 가 NP-완전임을 증명하면

MCSP 가 NP-완전임을 (일정한 꼴의 환원으로) 증명하면 지수 시간 클래스 E 에 대한 강한 회로 하한이 따라 나온다. 지금의 기법으로는 닿지 않는 결과다.

왜 다시 주목받는가

가운데에 MCSP 와 시간 제한 콜모고로프 복잡도가 있고, 다섯 갈래로 이어진다. 자연 증명(자연 성질은 MCSP 를 약하게 푸는 알고리즘, 2016년 학습 알고리즘), 최악에서 평균으로(Hirahara 2018), 암호의 기초(Liu·Pass 2020 일방향 함수와의 동치), NP-난해성으로 한 걸음(Hirahara 2022 부분 함수판 MCSP), 하한의 증폭(Oliveira·Santhanam 2018).
MCSP 류의 문제가 잇는 다섯 갈래 — 이 글이 다루는 결과만 그렸다.

자연 증명과 같은 뿌리. 자연 증명의 「자연 성질」은 진리표를 받아 어려운 함수를 무시할 수 없는 비율로 가려내는 효율적 알고리즘이다. MCSP 를 약하게 푸는 알고리즘인 셈이다. 그래서 회로 하한의 장벽과 MCSP 의 어려움은 같은 현상의 두 얼굴이다. Carmosino·Impagliazzo·Kabanets·Kolokolova(2016)는 이 연결을 뒤집어, 회로 클래스에 대한 자연 증명이 있으면 그 클래스를 배우는 학습 알고리즘이 나옴을 보였다.

최악의 경우에서 평균적 경우로. Hirahara(2018)는 시간 제한 콜모고로프 복잡도를 구하는 문제에 대해, 평균적 경우에 쉬우면 최악의 경우에도 근사적으로 쉽다는 환원을 주었다. 이전의 불가능성 결과들은 환원이 알고리즘을 블랙박스로만 쓸 때에 관한 것이었고, 이 환원은 블랙박스가 아니어서 그 장애를 비켜 간다. 그는 이 문제나 MCSP 의 근사판이 NP-난해임을 보이면 NP 의 최악의 경우 난해성과 평균적 난해성이 같아진다는 연구 계획을 내놓았다.

암호의 기초. Liu 와 Pass(2020)는 일방향 함수(one-way function)가 존재한다는 것과 Kt 가 평균적으로 「약하게 어렵다」는 것이 동치임을 증명했다. 여기서 t 는 (1+ε)n 이상인 임의의 다항식이다. 비밀 키 암호의 핵심 요소들의 존재가 잘 연구된 자연스러운 계산 문제 하나의 어려움으로 특징지어진 첫 사례다.

NP-난해성으로 한 걸음. Hirahara(2022)는 함숫값의 일부만 주어지는 부분 함수판 MCSP 가 무작위 다항 시간 환원 아래 NP-난해임을 증명했다. 같은 논문은 효율적인 프로그램을 학습하는 문제의 NP-난해성도 보였는데, 이 결과는 상대화하는 증명으로는 얻을 수 없음이 알려져 있다.

하한의 증폭. Oliveira 와 Santhanam(2018)은 MCSP 류 문제에 대한 「간신히 비자명한」 하한이 훨씬 강한 하한을 함의하는 현상을 찾아 강도 증폭(hardness magnification)이라 불렀다. 예컨대 어떤 매개변수의 MCSP 를 선형 크기 공식으로는 평균적으로 오류 없이 풀 수 없음을 보이면, NP 가 다항 크기 공식을 갖지 않는다는 결론이 나온다.

이런 흐름을 모아 Simons 연구소는 2023년 1월부터 5월까지 메타복잡도 연구 프로그램을 열었다.

아직 모르는 것

  • MCSP 는 NP-난해인가. Simons 프로그램이 풀고자 한 문제 목록의 맨 앞에 있다. 2025년 FOCS 에는 「잘 연구된 가정」 아래에서 MCSP 의 NP-난해성을 다루는 Hirahara 와 Ilango 의 논문이 실린 것으로 서지에 올라 있다. 가정 없는 증명은 알려져 있지 않다.
  • 일방향 함수의 존재를 NP 의 최악의 경우 난해성에서 끌어낼 수 있는가.

출처

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

참고문헌 11

  • 접근서지만 확인
    Circuit minimization problemValentine Kabanets, Jin-Yi Cai · 2000STOC 2000 (Proceedings of the 32nd Annual ACM Symposium on Theory of Computing), 73–79쪽 · ECCC TR99-045 (1999)

    최소 회로 크기 문제(MCSP)가 왜 P 에 속한다고도 NP-완전이라고도 증명하기 어려운지를 밝힌 논문이다. 이 문제가 쉽다고 가정하면 놀라운 귀결들이 따라 나오고, NP-완전임을 증명하면 그것만으로 강한 회로 하한이 나온다는 것을 보인다. 메타 복잡도 접근의 출발점을 찾는 독자에게 권한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR99-045 의 초록까지 확인. 본문을 읽었다는 기록은 없고, 귀결에 관한 서술은 Aaronson 2017 §6.2.5 의 각주와 Allender 2020 §4 로 확인.
    원문 주소 (eccc.weizmann.ac.il)
  • 개관원문 확인
    The New Complexity Landscape around Circuit MinimizationE. Allender · 2020Language and Automata Theory and Applications (LATA 2020), Lecture Notes in Computer Science, Springer, 3–16쪽

    최소 회로 크기 문제(MCSP)를 둘러싼 메타복잡도 연구의 최근 흐름을 정리한 개관이다. 「어떤 함수가 어렵다는 것을 증명하기가 왜 어려운가」라는 물음을 MCSP 의 복잡도 문제로 풀어 쓴다. 2-3 의 메타복잡도 글이 분야 소개와 MCSP 의 NP-완전성 증명이 어려운 까닭을 이 글에 기대어 적었다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 §2–§4 를 읽음.
    원문 주소 (people.cs.rutgers.edu)
  • 부분 결과원문 확인
    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)을 읽음.
    원문 주소 (eccc.weizmann.ac.il)
  • 부분 결과원문 확인
    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 공개본의 초록과 서론을 읽음.
    원문 주소 (arxiv.org)arXiv 2009.11514
  • 부분 결과서지만 확인
    NP-Hardness of Learning Programs and Partial MCSPS. Hirahara · 2022FOCS 2022 (63rd Annual IEEE Symposium on Foundations of Computer Science), 968–979쪽 · ECCC TR22-119 (2022)

    부분 함수판 최소 회로 크기 문제가 무작위 환원 아래 NP-난해임을 증명한 논문이다. MCSP 의 NP-난해성 문제로 한 걸음 다가선 결과다. 같은 논문은 효율적인 프로그램을 학습하는 문제의 NP-난해성도 보인다. 2-1 의 연표와 2-3 의 메타복잡도 글이 인용한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR22-119 공개본의 초록까지 확인. 본문을 읽었다는 기록이 분명하지 않아 서지 확인으로 둠.
    원문 주소 (eccc.weizmann.ac.il)
  • 부분 결과서지만 확인
    Hardness Magnification for Natural ProblemsI. C. Oliveira, R. Santhanam · 2018FOCS 2018 (59th Annual IEEE Symposium on Foundations of Computer Science), 65–76쪽 · ECCC TR18-139 (2018)

    MCSP 류 문제에 대한 간신히 비자명한 하한이 훨씬 강한 하한을 함의하는 「강도 증폭」 현상을 제시한 논문이다. 2-3 의 메타복잡도 글이 인용한다. ECCC 공개본으로 연결한다.

    확인:ECCC TR18-139 의 초록까지 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (eccc.weizmann.ac.il)
  • 부분 결과서지만 확인
    Learning Algorithms from Natural ProofsM. L. Carmosino, R. Impagliazzo, V. Kabanets, A. Kolokolova · 2016CCC 2016 (31st Conference on Computational Complexity), LIPIcs 50, 10:1–10:24쪽

    회로 클래스에 대한 자연 증명이 있으면 그 클래스를 배우는 학습 알고리즘이 나옴을 보인 논문이다. 자연 증명과 최소 회로 크기 문제의 연결을 뒤집어 쓴 결과로, 2-3 의 메타복잡도 글이 인용한다. 학회 논문집(LIPIcs) 페이지로 연결된다.

    확인:학회 논문집 페이지의 초록까지 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (drops.dagstuhl.de)
  • 부분 결과서지만 확인
    NP-hardness of the Minimum Circuit Size Problem from Well-Studied AssumptionsS. Hirahara, R. Ilango · 2025FOCS 2025 (66th Annual IEEE Symposium on Foundations of Computer Science), 1648–1664쪽

    「잘 연구된 가정」 아래에서 최소 회로 크기 문제의 NP-난해성을 다루는 FOCS 2025 논문이다. 본문을 열지 못해, 2-3 의 메타복잡도 글은 제목이 말하는 범위까지만 적었다. 가정 없는 증명은 알려져 있지 않다.

    확인:본문은 열지 못함. DOI 등록 기록으로 서지만 확인했고, 글에는 제목이 말하는 범위까지만 적음.
    원문 주소 (doi.org)DOI 10.1109/focs63196.2025.00087
  • 보조 자료원문 확인
    Meta-Complexity (연구 프로그램, 2023년 1월 10일–5월 12일)Simons Institute for the Theory of Computing · 2023Simons Institute 프로그램 소개 페이지

    Simons 연구소가 2023년 1월부터 5월까지 연 메타복잡도 연구 프로그램의 소개 페이지다. 「MCSP 는 NP-난해인가」가 이 프로그램이 풀고자 한 문제 목록의 맨 앞에 있다. 2-3 의 메타복잡도 글이 분야가 주목받는 근거로 인용한다.

    확인:프로그램 소개 페이지를 직접 열어 읽음.
    원문 주소 (simons.berkeley.edu)
  • 개관원문 확인
    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 등록 기록으로 확인.
    원문 주소 (doi.org)DOI 10.1145/129712.129771
  • 개관원문 확인
    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

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

아직 없습니다.