---
title: "NP 완전성: 빠른 검증과 빠른 풀이 사이의 질문"
author: "Lee"
published_at: "2026-10-20T07:32:02.627Z"
updated_at: "2026-09-30T10:03:12.775Z"
tags: ["컴퓨터공학","계산이론"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/np-%EC%99%84%EC%A0%84%EC%84%B1-%EB%B9%A0%EB%A5%B8-%EA%B2%80%EC%A6%9D%EA%B3%BC-%EB%B9%A0%EB%A5%B8-%ED%92%80%EC%9D%B4-%EC%82%AC%EC%9D%B4%EC%9D%98-%EC%A7%88%EB%AC%B8"
ai_assisted: false
---

# NP 완전성: 빠른 검증과 빠른 풀이 사이의 질문

[원문](https://ariser.io/@writer_a1cd615ab19e/np-%EC%99%84%EC%A0%84%EC%84%B1-%EB%B9%A0%EB%A5%B8-%EA%B2%80%EC%A6%9D%EA%B3%BC-%EB%B9%A0%EB%A5%B8-%ED%92%80%EC%9D%B4-%EC%82%AC%EC%9D%B4%EC%9D%98-%EC%A7%88%EB%AC%B8)

NP 완전성은 여러 결정 문제의 계산 난도를 연결하는 개념이다. 어렵다는 일상적 인상이나 알고리즘을 아직 찾지 못했다는 사실만으로 NP 완전하다고 부를 수 없다. 문제의 검증 구조와 다항시간 환원에 대한 두 조건을 증명해야 한다.

![SAT의 증거 대입을 빠르게 검증하는 과정과 NP 소속·NP 난해성 두 조건으로 정의하는 NP 완전성](/api/v1/media/69857f09-cdbd-436e-80d4-6c16c755fdc9)

*NP 완전성은 NP 소속과 모든 NP 문제의 다항 환원을 함께 요구한다. P와 NP가 같은지는 아직 해결되지 않았다.*

### P와 NP의 정의

P는 결정적 계산 모델에서 입력 길이에 대해 다항시간으로 판정할 수 있는 결정 문제의 집합이다. NP는 예 입력에 대해 다항 길이의 증거가 존재하고 그 증거를 다항시간에 검증할 수 있는 문제의 집합이다. 모든 P 문제는 NP에 포함된다.

SAT에서 변수 대입을 증거로 받으면 각 절이나 논리식을 평가하여 만족하는지 검사할 수 있다. 대입을 찾는 과정과 주어진 대입을 확인하는 과정은 다르다. NP의 N은 non-deterministic에서 왔으며 non-polynomial의 약자가 아니다.

```text
SAT input: a Boolean formula F
Certificate: one truth assignment for all variables
Verifier:
    evaluate F under the assignment
    return YES exactly when F is true

A certificate can be checked efficiently.
That does not by itself provide an efficient way to find one.
```

NP는 예라고 주장하는 증거를 빠르게 검사할 수 있다는 정의다. 아니오라는 증거도 언제나 같은 방식으로 존재한다는 뜻은 아니며, 이에 관련된 co-NP는 별도 개념이다.

### 어려움을 모으는 두 조건

NP-hard는 모든 NP 문제가 그 문제로 다항시간 환원된다는 뜻이다. NP-complete는 NP-hard이면서 동시에 NP에 속하는 문제다. NP-hard에는 NP 밖의 문제나 최적화 형태도 포함될 수 있으므로 두 표현을 섞어 쓰면 안 된다.

새 결정 문제 B의 NP 완전성을 보이려면 우선 증거를 다항시간에 검사할 수 있음을 보인다. 그다음 이미 NP 완전한 A를 골라 A≤ₚB를 구성한다. 알려진 어려운 문제를 새 문제로 옮기는 방향이어야 한다.

Cook–Levin 정리는 SAT가 NP 완전함을 보여 이런 환원 사슬의 출발점을 제공한다. 이후 3-SAT, 클릭, 정점 커버 등 많은 문제가 연결된다. 그중 하나의 NP 완전 문제에 다항시간 알고리즘이 생기면 모든 NP 문제도 다항시간에 풀려 P=NP가 된다.

현재 P=NP 여부는 해결되지 않았다. 따라서 NP 완전이라는 사실이 다항시간 알고리즘의 불가능성을 이미 증명했다는 뜻은 아니다. 모든 현실 입력이 느리다는 뜻도 아니다. 작은 크기, 특별한 구조, 평균 사례, 근사·휴리스틱은 실제 해결에 도움이 될 수 있다.

입력의 숫자 크기에 비례하는 의사다항 알고리즘이나 특정 매개변수에 민감한 알고리즘도 정의상 다항시간과 다를 수 있다. 최적화 문제를 논의할 때는 “값이 K 이상인가” 같은 결정 형태를 명시해야 한다. 정확한 모델과 입력 길이가 난도 주장의 기준이다.

### 참고 자료

- [MIT OpenCourseWare · Automata, Computability, and Complexity](https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/)
- [Clay Mathematics Institute · P vs NP](https://www.claymath.org/millennium/p-vs-np/)