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

한눈에 보는 부분 결과 — 확실히 증명된 것들

P 대 NP 문제는 풀리지 않았지만, 문제를 조금 약하게 바꾼 여러 명제는 엄밀히 증명되어 있다. 대표 결과를 표 하나에 모으고, 각각이 P 대 NP 에서 얼마나 떨어져 있는지 짚는다.

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

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

P 대 NP 문제는 풀리지 않았지만, 문제를 조금 약하게 바꾼 여러 명제는 엄밀히 증명되어 있다. 이 글은 대표 결과를 표 하나에 모으고, 각각이 P 대 NP 에서 얼마나 떨어져 있는지 짚는다.

「못 풀었다」와 「아는 것이 없다」는 다르다

P 대 NP 문제는 지금도 풀리지 않았다. Clay 수학연구소의 밀레니엄 문제 페이지에도 「Unsolved」로 적혀 있다(2026년 10월 확인). 그렇다고 손에 쥔 것이 없지는 않다. 연구자들은 문제를 조금 약하게 바꾼 명제를 하나씩 증명해 왔다. 이 절에서는 그것을 부분 결과라고 부른다. 약하게 바꾸는 길은 크게 셋이다.

  • 견주는 두 쪽의 차이를 크게 벌린다. P 와 NP 대신 P 와 EXP(지수 시간)를 견준다.
  • 계산 장치를 약하게 잡는다. 일반 논리 회로 대신 층수가 고정된 회로나 NOT 게이트가 없는 회로를 상대로 하한(lower bound), 곧 「적어도 이만큼은 든다」를 증명한다.
  • 「증명을 확인한다」는 말의 뜻을 넓힌다. 증명자와 묻고 답하며 확인하거나, 증명의 몇 군데만 읽고 확인한다.

표로 보는 대표 결과

학회 발표와 학술지 게재가 다른 해이면 둘 다 적었다.

대표 부분 결과
결과연도한 줄 뜻
시간 위계 정리 (Hartmanis–Stearns)1965시간을 충분히 더 주면 풀 수 있는 문제가 반드시 늘어난다. 따름 결과로 P ≠ EXP
비결정적 시간 위계 정리 (Cook)1972 · 1973비결정적 기계에서도 같다. 따름 결과로 NP ≠ NEXP
PARITY ∉ AC⁰ (Furst–Saxe–Sipser, Ajtai, Yao, Håstad)1981~1986층수가 고정되고 크기가 다항식인 회로는 1 의 개수가 홀수인지조차 계산하지 못한다
단조 회로 하한 (Razborov)1985AND 와 OR 만 쓰는 회로로 클릭 문제를 풀려면 다항식보다 빨리 커지는 크기가 든다
Razborov–Smolensky1987AC⁰ 에 「소수 p 로 나눈 나머지」 게이트를 더해도, 다른 소수 q 에 대한 나머지나 다수결은 계산하지 못한다
IP = PSPACE (Lund–Fortnow–Karloff–Nisan, Shamir)1990 · 1992묻고 답하며 확인할 수 있는 문제는 정확히 다항 공간으로 풀리는 문제다
PCP 정리 (Arora–Safra, Arora–Lund–Motwani–Sudan–Szegedy)1992 · 1998NP 문제의 증거는 상수 개의 자리만 읽어도 검사할 수 있는 꼴로 다시 쓸 수 있다
MAX-3SAT 의 7/8 문턱 (Håstad)1997 · 2001충족 가능한 3SAT 식에서 절의 7/8 보다 조금이라도 많은 비율을 늘 충족시키는 다항 시간 알고리즘이 있으면 P = NP 다
NEXP ⊄ ACC⁰ (Williams)2011 · 2014비결정적 지수 시간에는 다항 크기 ACC⁰ 회로로 풀 수 없는 문제가 있다
NQP ⊄ ACC⁰ (Murray–Williams)2018위 결과의 왼쪽을 비결정적 준다항 시간까지 끌어내렸다

표에 나오는 이름들

EXP, NEXP
지수 시간에 결정적으로, 또는 비결정적으로 풀리는 문제의 클래스다. NQP 는 NP 와 NEXP 사이에 있는 비결정적 준다항 시간의 클래스다. 준다항 시간이란 n 을 log n 의 거듭제곱만큼 거듭제곱한 시간이다.
PSPACE
다항식 크기의 기억 공간으로 풀리는 문제의 클래스다.
AC⁰
AND·OR·NOT 게이트로 된 회로 가운데 층수가 상수이고 크기가 다항식인 것으로 계산되는 문제의 클래스다. 게이트 하나가 받는 입력 수에는 제한이 없다. ACC⁰ 는 여기에 「1 의 개수를 m 으로 나눈 나머지」를 보는 게이트를 더한 것이다.
단조 회로(monotone circuit)
NOT 없이 AND 와 OR 만 쓰는 회로다.
IP
대화형 증명으로 확인할 수 있는 문제의 클래스다. PCP 는 확률적으로 검사할 수 있는 증명(probabilistically checkable proof)의 머리글자다.

세 갈래로 읽기

  • 대각선 논법 갈래: 두 위계 정리. 같은 종류의 자원을 양으로 가르는 데는 강하다. 그러나 증명이 상대화(relativization)하기 때문에 P 와 NP 사이는 가르지 못한다.
  • 회로 하한 갈래: PARITY, 단조 회로, Razborov–Smolensky. 약한 회로에서는 눈부신 성과를 냈지만, 더 센 회로로 올라가는 길은 자연 증명(natural proofs) 장벽에 막혀 있다.
  • 산술화 갈래: IP = PSPACE 와 PCP 정리. 상대화 장벽을 실제로 넘은 결과들이다. 다만 이 기법에도 대수화(algebrization)라는 장벽이 있다.
세 갈래와 장벽을 그린 도식. 맨 위에 목표인 P 대 NP 가 있다. 왼쪽 대각선 논법 갈래(시간 위계 정리, 비결정적 시간 위계 정리)는 상대화 장벽에 막혀 있다. 가운데 회로 하한 갈래(PARITY ∉ AC⁰, 단조 회로 하한, Razborov–Smolensky)는 자연 증명 장벽에 막혀 있다. 오른쪽 산술화 갈래(IP = PSPACE, PCP 정리)는 상대화 장벽을 넘었지만 그 위의 대수화 장벽을 만난다. 맨 아래에 Williams 의 결과가 세 갈래의 도구를 엮어 세 장벽을 모두 피해 갔다고 적혀 있다.
세 갈래의 부분 결과와 각 갈래가 만나는 장벽. 산술화 갈래만 상대화 장벽을 넘었고, 그 위에 대수화 장벽이 있다.

Williams 의 결과는 세 갈래의 도구를 한 증명 안에 엮어 세 장벽을 모두 피해 간 드문 예다.

P 대 NP 까지 남은 거리

회로 쪽에서 P ≠ NP 를 보이려면 「NP 의 어떤 문제는 다항 크기의 일반 회로로 풀 수 없다」를 증명하면 된다. 지금 증명된 것은 왼쪽이 NP 보다 훨씬 큰 NEXP·NQP 이고, 오른쪽이 일반 회로보다 훨씬 약한 ACC⁰ 인 경우다. 일반 회로를 상대로는 NP 의 어떤 문제에 대해서도 입력 길이에 비례하는 수준을 넘는 하한이 알려져 있지 않다(Aaronson 의 2017년 개관 기준).

그래도 부분 결과는 두 가지를 알려 준다. 어떤 기법이 어디까지 통하고 왜 거기서 멈추는지, 그리고 계산의 세계가 한 덩어리로 뭉개지지 않고 층을 이루고 있다는 사실이다. 이어지는 글에서 하나씩 살핀다.

출처

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

참고문헌 15

  • 보조 자료원문 확인
    P vs NPClay Mathematics Institute · 2026Clay Mathematics Institute 웹 페이지 (2026-10-05 확인)

    Clay 수학연구소의 P 대 NP 문제 소개 페이지다. 기숙사 배정의 예로 문제를 설명하고, Cook 과 Levin 이 1971년에 독립적으로 문제를 정식화했다고 적으며, 문제의 상태를 「Unsolved」로 표시한다. 공식 문제 기술 PDF 로 가는 링크가 이 페이지에 있다.

    확인:2026-10-05 에 페이지를 직접 열어 읽음(상태 표기 「Unsolved」 확인).
    원문 주소 (www.claymath.org)
  • 개관원문 확인
    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)
  • 원전원문 확인
    On the computational complexity of algorithmsJuris Hartmanis, Richard E. Stearns · 1965Transactions of the American Mathematical Society 117 (1965), 285–306쪽

    계산에 드는 시간으로 문제를 분류하는 틀을 세우고 시간 위계 정리를 증명한 논문이다. 「계산 복잡도」라는 분야가 여기서 시작되었다. 대각선 논법으로 복잡도 종류를 가르는 방법의 뿌리를 보려는 독자에게 권한다. 미국수학회 누리집에 PDF 가 올라 있다.

    확인:미국수학회 누리집의 공개 PDF 를 열어 정리 6·정리 9 와 그 증명 요약을 읽음.
    원문 주소 (www.ams.org)
  • 부분 결과서지만 확인
    A hierarchy for nondeterministic time complexityStephen A. Cook · 1973Journal of Computer and System Sciences 7(4), 343–353쪽 (1973) · 학회 발표 STOC 1972, 187–192쪽

    비결정적 시간에도 위계 정리가 성립함을 처음 증명한 논문이다. 따름 결과로 NP ≠ NEXP 가 나온다. 2-4 의 부분 결과 개관과 시간 위계 정리 글이 인용한다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 3장과 영어 위키백과 「Time hierarchy theorem」 문서로 확인.
    원문 주소 (doi.org)DOI 10.1016/s0022-0000(73)80028-5
  • 부분 결과서지만 확인
    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)
  • 부분 결과원문 확인
    Lower bounds on the monotone complexity of some Boolean functionsAlexander A. Razborov · 1985Doklady Akademii Nauk SSSR 281(4), 798–801쪽 (1985, 러시아어) · 영문 번역 Soviet Mathematics Doklady 31, 354–357쪽 (1985)

    NOT 을 쓰지 않는 단조 회로로는 클릭 문제를 다항 크기에 풀 수 없음을 증명한 논문이다. NP-완전 문제에 대한 초다항 회로 하한을 (단조 회로라는 제한 아래) 처음 얻어 큰 기대를 모았다. 다만 이 방법은 일반 회로로 넓혀지지 않았다. 연결한 것은 저자가 올린 영문 번역본이며, 러시아어 원문의 서지는 Math-Net.Ru(mathnet.ru/eng/dan9192)에 있다.

    확인:저자 누리집의 영문 번역본을 열어 정리 2·정리 3 과 그 설명을 읽음. 러시아어 원문의 서지는 Math-Net.Ru 로 확인.
    원문 주소 (people.cs.uchicago.edu)
  • 부분 결과서지만 확인
    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
  • 부분 결과원문 확인
    Algebraic methods for interactive proof systemsCarsten Lund, Lance Fortnow, Howard Karloff, Noam Nisan · 1992Journal of the ACM 39(4), 859–868쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 2–10쪽

    대화형 증명을 짓는 대수적 기법(산술화)을 도입해 다항 위계의 모든 문제가 대화형 증명을 가짐을 보인 논문이다. IP = PSPACE 와 PCP 정리로 이어지는 흐름의 출발점이다. 산술화가 어떻게 상대화 장벽을 넘는지 원문으로 보려는 독자에게 권한다. 공저자 Fortnow 의 누리집에 있는 공개본으로 연결한다.

    확인:저자 공개본을 열어 초록과 서론을 읽음.
    원문 주소 (lance.fortnow.com)
  • 부분 결과서지만 확인
    IP = PSPACEAdi Shamir · 1992Journal of the ACM 39(4), 869–877쪽 (1992) · 학회 발표 FOCS 1990 (31st Annual Symposium on Foundations of Computer Science), 11–15쪽

    대화형 증명으로 증명할 수 있는 문제의 모임이 정확히 PSPACE 임을 보인 논문이다. 상대화되지 않는 증명의 대표 사례다. 같은 호에 나란히 실린 lfkn-1992 의 기법 위에 서 있으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Aaronson 2017 §6.3.1 과 Arora–Barak 공개 초고 8장의 역사 주석으로 확인.
    원문 주소 (doi.org)DOI 10.1145/146585.146609
  • 부분 결과서지만 확인
    Probabilistic checking of proofs: a new characterization of NPSanjeev Arora, Shmuel Safra · 1998Journal of the ACM 45(1), 70–122쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 2–13쪽

    NP 를 「무작위로 일부만 들춰 보는 증명」으로 새로 규정해 PCP 정리의 앞 절반을 놓은 논문이다. almss-1998 이 이 결과를 고쳐 읽는 비트 수를 상수로 줄였으므로 두 편을 함께 본다. ACM 디지털 도서관으로 연결된다.

    확인:게시자 누리집이 자동 접속을 막아 원문을 열지 못함. 서지는 Crossref 의 DOI 등록 기록으로, 내용은 Arora–Barak 공개 초고 18장으로 확인.
    원문 주소 (doi.org)DOI 10.1145/273865.273901
  • 부분 결과원문 확인
    Proof verification and the hardness of approximation problemsSanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy · 1998Journal of the ACM 45(3), 501–555쪽 (1998) · 학회 발표 FOCS 1992 (33rd Annual Symposium on Foundations of Computer Science), 14–23쪽

    NP 의 증명을 상수 개의 비트만 읽고 확률적으로 검증할 수 있음을 보여 PCP 정리를 완성한 논문이다. 그 귀결로, MAX-3SAT 같은 문제는 P ≠ NP 인 한 최적값에 얼마든지 가깝게 근사하는 다항 시간 방법을 가질 수 없음을 보인다. 근사 불가능성 이론의 원전을 찾는 독자에게 권한다. 공저자 Sudan 의 누리집에 있는 학술지판 공개본으로 연결한다.

    확인:저자 공개본(학술지판)을 열어 초록을 읽음. 정리의 내용은 Arora–Barak 공개 초고 18장으로 확인.
    원문 주소 (people.csail.mit.edu)
  • 부분 결과원문 확인
    Some optimal inapproximability resultsJ. Håstad · 2001Journal of the ACM 48(4), 798–859쪽 (2001) · 학회 발표 STOC 1997, 1–10쪽

    MAX-3SAT 을 비롯한 여러 문제에 대해 더는 좁힐 수 없는 근사 불가능성 문턱을 증명한 논문이다. 충족 가능한 3SAT 식에서 절의 7/8 보다 조금이라도 많은 비율을 늘 충족시키는 다항 시간 알고리즘이 있으면 P = NP 임을 보인다. 2-4 의 부분 결과 개관과 PCP 정리 글이 인용한다. 저자 누리집의 공개본으로 연결한다.

    확인:저자 공개본을 열어 초록을 읽음.
    원문 주소 (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)
  • 부분 결과원문 확인
    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)

하위 정보 0

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

아직 없습니다.