HYPSVC.com
서비스 커뮤니티
  1. P vs NP 문제 풀기
  2. 1. P vs NP 문제는 무엇인가?
  3. 1-1 학술 자료

형식 정의 — 튜링 기계, 다항 시간, P 와 NP

P 대 NP 문제를 수학 명제로 만드는 정의를 차례로 적는다. 결정 문제와 언어, 결정적 튜링 기계와 시간, P, 두 가지로 정의되는 NP, coNP, 그리고 P ⊆ NP ⊆ PSPACE ⊆ EXP.

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

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

P 대 NP 문제를 수학 명제로 만드는 정의를 차례로 적는다. 결정 문제와 언어, 결정적 튜링 기계와 시간, P, 두 가지로 정의되는 NP, coNP, 그리고 P ⊆ NP ⊆ PSPACE ⊆ EXP 까지다.

왜 형식 정의가 필요한가

「답을 빨리 확인할 수 있으면 빨리 찾을 수도 있는가」라는 말만으로는 아무것도 증명할 수 없다. 「문제」, 「알고리즘」, 「빨리」가 수학적 대상이 되어야 한다. 아래 정의는 Cook 의 공식 문제 기술과 Arora–Barak 교과서가 쓰는 표준 정의이며, 표현은 조금씩 달라도 같은 클래스를 가리킨다.

결정 문제와 언어

알파벳 · 문자열 · 언어
기호가 둘 이상인 유한 집합 Σ 를 알파벳이라 하고, Σ 의 기호를 유한 개 늘어놓은 문자열 전체를 Σ* 로 적는다. 언어(language)는 Σ* 의 부분집합이다.

결정 문제(decision problem)는 답이 「예」 또는 「아니오」인 문제다. 입력을 문자열로 부호화하면 결정 문제는 「답이 예인 입력의 집합」, 곧 언어 하나와 같아진다. 예를 들어 SAT 는 참으로 만들 수 있는 논리식의 부호를 모은 언어다.

입력의 크기 n 은 문자열의 길이다.

결정적 튜링 기계와 실행 시간

튜링 기계(Turing machine)는 유한 개의 상태를 가진 제어부, 칸으로 나뉜 무한한 테이프, 한 칸씩 움직이며 읽고 쓰는 헤드로 이루어진다. 전이 함수 δ 는 「지금 상태와 읽은 기호」에 대해 「다음 상태, 쓸 기호, 헤드를 옮길 방향」을 정한다. 다음 동작이 언제나 하나로 정해지는 기계를 결정적(deterministic)이라 한다.

받아들임
기계 M 이 입력 w 에서 수락 상태로 멈추면 M 이 w 를 받아들인다고 한다. M 이 받아들이는 문자열의 집합이 L(M) 이다.
실행 시간
tM(w) 는 w 에서 M 이 밟는 단계 수, TM(n) 은 길이 n 인 모든 입력에 걸친 tM(w) 의 최댓값이다. 평균이 아니라 최악의 경우를 잰다.
다항 시간
어떤 상수 k 가 있어 모든 n 에서 TM(n) ≤ nk + k 이면 M 은 다항 시간(polynomial time)에 돈다고 한다.

P

P = { L : 다항 시간에 도는 어떤 튜링 기계 M 에 대해 L = L(M) }

테이프가 하나뿐인 기계로 정의해도 잃는 것이 없다. Hartmanis 와 Stearns 는 1965년 논문에서 여러 테이프 기계가 T(n) 단계에 하는 일을 한 테이프 기계가 T(n)² 단계에 할 수 있음을 보였고, Cook 도 임의 접근 메모리를 가진 모델까지 제곱이나 세제곱의 시간으로 흉내 낼 수 있다고 적는다. 다항식을 제곱해도 다항식이므로 P 는 모델에 따라 달라지지 않는다.

다항식이 경계로 쓰이는 까닭도 여기에 있다. 다항식은 더하고 곱하고 합성해도 다항식이어서, 효율적인 절차를 이어 붙인 것이 다시 효율적이게 된다.

P 에 속하는 예로 Cook 은 정수 연산, 선형 계획법, 그래프의 최단 경로와 이분 매칭을 든다. 소수 판정도 2004년 논문으로 P 에 속함이 증명되었다.

NP — 같은 클래스의 두 정의

검증자로 본 정의. 언어 L 이 NP 에 속한다는 것은, 다항식 p 와 다항 시간 기계 V(검증자, verifier)가 있어서 모든 x 에 대해 다음이 성립한다는 뜻이다.

x ∈ L ⇔ 길이가 p(|x|) 이하인 어떤 문자열 u 에 대해 V 가 (x, u) 를 받아들인다

u 를 증거(certificate)라 한다.

SAT 에서는 식을 참으로 만드는 대입이 증거다. 정의는 비대칭이다. x ∈ L 일 때만 짧은 증거가 있으면 되고, x ∉ L 임을 보이는 증거는 요구하지 않는다.

비결정적 기계로 본 정의. 비결정적(nondeterministic) 튜링 기계는 한 상황에서 고를 수 있는 다음 동작이 둘 이상이다. 선택을 어떻게 하느냐에 따라 계산 경로가 갈리며, 수락으로 끝나는 경로가 하나라도 있으면 입력을 받아들인다고 한다. NP 는 다항 시간 비결정적 기계가 받아들이는 언어의 클래스이고, 이름 NP(nondeterministic polynomial time)도 여기서 왔다.

두 정의는 같은 클래스를 준다. 비결정적 기계가 수락할 때 고른 선택의 열을 적으면 그것이 증거가 되고, 거꾸로 검증자가 있으면 비결정적 기계가 증거 u 를 한 기호씩 골라 쓴 다음 V 를 돌리면 된다.

왼쪽: 입력 x 와 증거 u 가 다항 시간 검증자 V 로 들어가 받아들여진다. 오른쪽: 비결정적 기계의 계산 경로가 시작점에서 나무처럼 갈라지고, 여러 끝 가운데 하나만 수락이다. 수락으로 끝나는 경로에서 고른 선택의 열이 증거다.
NP 의 두 정의. 수락으로 끝나는 경로에서 고른 선택의 열을 적으면 검증자에게 줄 증거가 된다.

P ⊆ NP 는 정의에서 바로 나온다. 증거를 보지 않고도 판정하는 기계는 그대로 검증자다.

coNP

coNP 는 여집합이 NP 에 속하는 언어의 클래스다.

「아니오」 쪽에 짧은 증거가 있는 문제들이며, 모든 대입에서 참인 식(항진식)의 집합 TAUT 가 대표적이다. 항진식이 아님은 거짓으로 만드는 대입 하나로 확인된다.

P ⊆ NP ∩ coNP 이다. P = NP 이면 NP = coNP 이므로, NP ≠ coNP 를 보이면 P ≠ NP 도 따라 나온다. NP = coNP 인지 역시 풀리지 않았다.

더 큰 클래스와 포함 관계

PSPACE 는 다항식 크기의 기억 공간으로, EXP 는 2nc 꼴의 시간으로 판정되는 언어의 클래스다.

P ⊆ NP ⊆ PSPACE ⊆ EXP

  • NP ⊆ PSPACE: 가능한 증거를 하나씩 써서 검사하고 지우면 같은 공간을 다시 쓸 수 있다.
  • PSPACE ⊆ EXP: 다항 공간만 쓰는 기계가 놓일 수 있는 상황의 수는 지수 개를 넘지 않는다.
  • P ≠ EXP: 증명된 사실이다. 시간을 충분히 더 주면 풀 수 있는 문제가 실제로 늘어난다는 시간 위계 정리(time hierarchy theorem)에서 나오며, 이 정리는 Hartmanis 와 Stearns 의 1965년 논문에서 비롯되었다.
왼쪽: 바깥부터 EXP, PSPACE, NP, P 가 차례로 안에 든 타원 그림. 증명된 것은 P ≠ EXP 이고, 세 포함 가운데 어느 것이 진부분집합인지는 증명되지 않았다. 오른쪽: NP 와 coNP 두 원이 겹치고 그 겹친 곳 안에 P 가 있다. NP = coNP 인지도 풀리지 않았다.
포함 관계만 나타낸 그림이다. 영역을 따로 그렸다고 해서 두 클래스가 다르다는 뜻은 아니다.

양 끝이 다르므로 세 포함 관계 가운데 적어도 하나는 진부분집합이다. 그러나 어느 것이 그런지는 하나도 증명되지 않았다. P ≠ NP 는 그 가운데 첫 자리에 대한 추측이다.

출처

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

참고문헌 5

  • 원전원문 확인
    The P versus NP ProblemStephen Cook · 2000Clay Mathematics Institute, Millennium Prize Problems 공식 문제 기술 (12쪽 PDF · 문서에 날짜 표기 없음 · Cook 의 홈페이지 출판 목록에 따르면 2000년 4월 작성·11월 개정 원고 · 밀레니엄 상 문제는 2000년 5월 24일 발표 · 현재 공개본은 2004년 문헌까지 인용하므로 그 뒤에 손본 판)

    Clay 수학연구소가 밀레니엄 상 문제로 내건 P 대 NP 문제의 공식 문제 기술이다. 문제의 정확한 진술, 역사와 중요성, 추측과 그것을 증명하려는 시도, 부록의 튜링 기계 정의로 이루어진 12쪽짜리 글이다. 「정확히 무엇을 증명해야 하는가」를 확인하려는 독자라면 누구나 가장 먼저 읽을 글이다.

    확인:공식 PDF 12쪽 전체를 내려받아 읽고, 인용한 다섯 문장을 원문과 글자 단위로 대조함.
    원문 주소 (www.claymath.org)
  • 교과서원문 확인
    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)
  • 개관원문 확인
    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)
  • 부분 결과서지만 확인
    PRIMES is in PManindra Agrawal, Neeraj Kayal, Nitin Saxena · 2004Annals of Mathematics 160(2), 781–793쪽 (2004) · 예비 논문 공개 2002년

    주어진 수가 소수인지를 무작위도 미증명 가설도 쓰지 않고 다항 시간에 판정하는 알고리즘을 제시한 논문이다. 「소수 판별은 P 에 속하는가」라는 오랜 물음을 13쪽으로 해결했다. 어렵다고 여겨지던 문제에 뜻밖의 알고리즘이 나올 수 있음을 보여 주는 사례다. 학술지 누리집에서 PDF 를 받을 수 있다.

    확인:학술지 누리집의 논문 페이지와 DOI 등록 기록으로 서지를 확인. 본문을 읽었다는 기록은 없음.
    원문 주소 (annals.math.princeton.edu)

하위 정보 0

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

아직 없습니다.