NP (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

NP는 다항 시간 내에 비결정적 튜링 기계로 풀 수 있거나, 다항 시간 내에 결정적 튜링 기계로 검증 가능한 결정 문제의 집합을 의미한다. NP는 P, co-NP, PSPACE, EXPTIME 등 다양한 복잡도 클래스와 관계를 가지며, NP-완전 문제와 NP-난해 문제도 포함한다. NP는 합집합, 교집합, 연결, 클레이니 스타, 역 연산에 대해 닫혀 있으며, P ≠ NP 문제는 컴퓨터 과학의 주요 미해결 문제 중 하나이다.

더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

NP (복잡도)
개요
분류	계산 복잡도 이론
복잡도 종류	문제의 복잡도 종류
풀이	비결정적 튜링 기계
시간 복잡도	다항 시간
결정 문제	예
NP-완전 문제	SAT 외판원 문제
정의
개요	NP는 '비결정적 다항 시간(Nondeterministic Polynomial time)'의 약자이다. NP는 어떤 문제에 대한 해답이 주어졌을 때, 그 해답이 올바른 것인지 다항 시간 내에 확인할 수 있는 문제들의 집합이다. 다시 말해, 어떤 문제의 '예'에 대한 증거가 주어졌을 때, 그 증거가 다항 시간 안에 검증될 수 있다면 그 문제는 NP에 속한다.
예시	예를 들어, 외판원 문제는 NP에 속한다. 어떤 경로가 주어졌을 때, 그 경로의 길이가 특정 값 이하인지 다항 시간 안에 확인할 수 있기 때문이다.
P와의 관계	모든 P 문제는 NP 문제이기도 하다. 왜냐하면 P 문제에 대한 해답은 다항 시간 안에 찾을 수 있을 뿐만 아니라, 다항 시간 안에 그 해답이 올바른지 확인할 수도 있기 때문이다. 하지만 NP에 속하는 모든 문제가 P에 속하는지는 아직 알려지지 않았다. 이것이 바로 유명한 P-NP 문제이다.
Co-NP	Co-NP는 NP 문제의 여집합에 대한 복잡도 클래스이다. 어떤 문제의 '아니오'에 대한 증거가 다항 시간 안에 검증될 수 있다면 그 문제는 Co-NP에 속한다.
같이 보기
관련 항목	P-NP 문제 NP-완전 NP-난해 계산 복잡도 이론

2. 정의

'''NP'''는 '''계산 복잡도 이론'''에서 중요한 복잡도 종류 중 하나로, 비결정적 다항 시간(Non-deterministic Polynomial time^eng)의 약자이다. NP는 두 가지 동등한 방식으로 정의될 수 있다.

첫 번째 정의는 비결정적 튜링 기계(NTM)를 이용하는 것이다. NP는 비결정적 튜링 기계가 다항 시간 안에 풀 수 있는 결정 문제들의 집합이다. 이를 수학적으로 표현하면 다음과 같다.^[13]

: $\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k)$

여기서 $\mathsf{NTIME}(n^k)$ 는 비결정적 튜링 기계가 $O(n^k)$ 시간 안에 해결할 수 있는 결정 문제의 집합을 나타낸다.

두 번째 정의는 '검증'의 개념을 이용한다. 어떤 결정 문제에 대해 답이 "예"일 경우, 그 답이 옳다는 것을 보여주는 '증거'(certificate 또는 witness)가 존재하고, 이 증거가 정말 맞는지를 결정적 튜링 기계를 이용하여 다항 시간 안에 효율적으로 확인할 수 있다면 그 문제는 NP에 속한다. 즉, NP는 답을 찾는 과정은 어려울 수 있어도, 제시된 답(증거)이 맞는지 검증하는 과정은 쉬운 문제들의 모임이라고 할 수 있다.

예를 들어, 자연수의 소인수분해와 관련된 결정 문제(가령, "주어진 수 N에게 p보다 작은 소인수가 있는가?")는 NP에 속한다. 소인수를 직접 찾는 것은 어려울 수 있지만, 만약 어떤 수가 소인수라고 제시되면(증거), 그것이 정말 N의 약수인지 확인하는 것은 다항 시간 안에 비교적 쉽게 할 수 있기 때문이다.

이 두 가지 정의, 즉 비결정적 튜링 기계로 다항 시간 안에 풀 수 있다는 것과 결정적 튜링 기계로 다항 시간 안에 검증할 수 있다는 것은 서로 동치인 것으로 알려져 있다.

2. 1. 검증자 기반 정의

NP에 속하는 문제는 그 답을 찾는 것은 어려울 수 있지만, 일단 답의 후보(증거)가 주어졌을 때 그것이 정말 정답인지를 다항 시간 안에 효율적으로 확인할 수 있는 결정 문제들의 집합으로 이해할 수 있다. 이를 검증자 기반 정의라고 한다.

예를 들어, 자연수의 소인수분해에 대한 결정문제는 NP에 속한다. 가령, 100자리 숫자에 대한 소인수분해는 매우 오래 걸릴 수 있지만, 그 소인수분해의 결과를 알고 있다면 해당 숫자를 단순히 곱하는 것으로도 소인수분해가 잘 이루어졌는지 확인할 수 있기 때문에 다항 시간 안에 검증이 가능하다.

NP는 결정적 튜링 기계를 검증기로 사용하여 정의할 수 있다. 언어 ''L''이 NP에 속한다는 것은 다음 조건을 만족하는 다항식 ''p''와 결정적 튜링 기계 ''M''이 존재함을 의미한다.^[13]

''L''에 속하는 모든 ''x''에 대해, 어떤 증거 문자열 $w \in \{0, 1\}^{p(|x|)}$ 가 존재하여, ''M''(''x'', ''w'') = 1 (즉, "참" 또는 "수락")이다. 이 증거 문자열 ''w''를 증인(witness) 또는 증명(certificate)이라고 한다.
''L''에 속하지 않는 모든 ''x''에 대해, 길이 $p(|x|)$ 이하의 모든 증거 문자열 ''w''에 대해 ''M''(''x'', ''w'') = 0 (즉, "거짓" 또는 "거절")이다.
모든 입력 문자열 ''x''와 증거 문자열 ''w''에 대해, 기계 ''M''은 입력 (''x'', ''w'')에 대해 다른 다항식 ''p' ''(|''x''|) 시간 안에 실행을 마친다. (검증 과정 자체가 다항 시간 안에 끝나야 함).

이 정의에서 기계 ''M''을 검증자(verifier)라고 부른다.

부분 집합 합 문제는 NP의 검증자 기반 정의를 이해하는 데 좋은 예시이다.

문제: 주어진 정수 집합 {−7, −3, −2, 5, 8}에서, 원소들의 합이 0이 되는 공집합이 아닌 부분 집합이 존재하는가?
답: 예. 부분 집합 {−3, −2, 5}의 합은 (−3) + (−2) + 5 = 0이다.
어려움: 가능한 모든 부분 집합을 만들어서 합을 계산하는 방법은 집합의 크기가 커짐에 따라 기하급수적으로 시간이 오래 걸린다.
검증: 하지만 누군가가 {−3, −2, 5}라는 부분 집합(증거)을 제시하면, 이 세 숫자를 더해서 합이 0인지 확인하는 것은 매우 빠르다(다항 시간). 이 덧셈 과정을 수행하는 알고리즘이 바로 검증자이다. 합이 0이므로, 이 부분 집합은 문제의 답이 "예"임을 증명하는 증거(증인)가 된다.

이처럼 부분 집합 합 문제는 주어진 증거(부분 집합)를 다항 시간 안에 검증할 수 있으므로 NP에 속한다.

일반적으로, 어떤 결정 문제

\Pi

의 특정 인스턴스

I

에 대한 답이 "예"일 때, 그 답이 "예"임을 증명하는 증거

W

가 존재하고, 이 증거

W

가 정말 올바른 증거인지를 다항 시간 안에 확인할 수 있는 검증자 알고리즘

V

(즉,

V(I, W)

가 다항 시간 내에 "예" 또는 "아니오"를 반환)가 존재한다면, 그 문제

\Pi

는 NP에 속한다.

NP의 검증자 기반 정의는 문제의 답이 "예"일 경우에 대한 효율적인 검증만을 요구한다. 답이 "아니오"일 경우에 대해 효율적인 검증(즉, "아니오"임을 증명하는 증거를 다항 시간 내에 검증)이 가능한 문제들의 집합은 co-NP라고 부른다. NP에 속하는 모든 문제가 co-NP에도 속하는지, 즉 모든 NP 문제에 대해 "아니오" 답을 위한 효율적인 증거와 검증자가 항상 존재하는지는 계산 복잡도 이론의 중요한 미해결 문제 중 하나이다 (NP = co-NP 문제).

일부 문헌에서는 검증자를 "인증자"라고 부르고, 증거를 "인증서"라고 부르기도 한다.^[1]

NP는 또한 NTIME (비결정론적 튜링 기계 시간 복잡도)을 사용하여 다음과 같이 정의할 수도 있다.^[13]

:

\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k)

여기서

\mathsf{NTIME}(n^k)

는 비결정적 튜링 기계가

O(n^k)

시간 안에 해결할 수 있는 결정 문제의 집합이다. 즉, NP는 비결정적 튜링 기계에 의해 다항 시간 내에 풀 수 있는 결정 문제의 클래스이다. NP라는 명칭 자체도 비결정적 다항 시간(Non-deterministic Polynomial time)의 약자이다. 이 NTIME 기반 정의는 앞서 설명한 검증자 기반 정의와 동치이다.

2. 2. 기계 기반 정의

'''NP'''는 비결정적 튜링 기계가 다항 시간 안에 해결할 수 있는 결정 문제의 집합으로 정의될 수 있다. 비결정적 튜링 기계는 계산 과정에서 여러 가능한 다음 상태 중 하나를 '추측'하여 진행할 수 있는데, 이 추측 중 하나라도 문제를 해결하는 경로(수용 상태에 도달하는 경로)로 이어지면 해당 문제의 답은 '예'가 된다.

좀 더 형식적으로, '''NP'''는 NTIME을 사용하여 다음과 같이 정의할 수 있다.^[13]

:

\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k)

여기서

\mathsf{NTIME}(n^k)

는 비결정적 튜링 기계가

O(n^k)

시간 안에 해결할 수 있는 결정 문제의 집합을 의미한다. 즉, '''NP'''는 비결정적 다항 시간(eng)의 약자이다.

'''NP'''는 결정적 튜링 기계를 '검증기'로 사용하여 동치적으로 정의할 수도 있다. 어떤 언어

L

이 '''NP'''에 속한다는 것은, 다음 조건을 만족하는 다항식

p

와

q

, 그리고 결정적 튜링 기계

M

이 존재한다는 의미이다.

모든 입력 $x$ 와 '증거'(certificate) 문자열 $y$ 에 대해, 기계 $M$ 은 입력 $(x, y)$ 에 대해 $p(|x|)$ 시간 안에 실행을 마친다. ( $|x|$ 는 입력 $x$ 의 길이)
언어 $L$ 에 속하는 모든 $x$ 에 대해, $M(x, y) = 1$ (즉, '참' 또는 '수용')을 만족하는 길이 $q(|x|)$ 의 증거 문자열 $y \in \{0, 1\}^{q(|x|)}$ 가 존재한다.
언어 $L$ 에 속하지 않는 모든 $x$ 와 길이 $q(|x|)$ 인 모든 증거 문자열 $y \in \{0, 1\}^{q(|x|)}$ 에 대해, $M(x, y) = 0$ (즉, '거짓' 또는 '거부')이다.

이 검증기 기반 정의는 비결정적 튜링 기계 정의와 동등하다. 비결정적 튜링 기계는 다항 시간 내에 가능한 증거 문자열

y

를 비결정적으로 '추측'하고, 그 증거에 대해 검증기

M

을 실행하는 방식으로 '''NP''' 문제를 풀 수 있다. 반대로, '''NP''' 문제를 푸는 비결정적 튜링 기계

A

가 주어지면, 그 기계의 '수용' 계산 경로 자체가 증거가 되어 이를 확인하는 다항 시간 결정적 검증기를 만들 수 있다. 검증기는

A

를 결정적으로 시뮬레이션하며 제공된 증명(수용 경로)을 따라가 최종적으로 수용 상태에 도달하는지 검증한다. 만약

A

가 입력을 거부하면 수용 경로는 없으므로 검증기는 항상 거부한다.

이러한 관점에서 co-NP는 '존재적 거부 조건'을 가진 다항 시간 비결정적 튜링 기계로 인식 가능한 결정 문제의 클래스로 정의할 수 있다. 존재적 거부 조건은 '보편적 수용 조건'과 동일하며, 이는 NP 대 co-NP 문제가 존재적 수용 조건과 보편적 수용 조건이 다항 시간 비결정적 튜링 기계 클래스에 대해 동일한 표현력을 가지는지 묻는 것과 같음을 의미한다.

3. 예시

컴퓨터 과학의 여러 문제, 특히 많은 탐색 문제와 최적화 문제의 결정 버전이 NP에 속한다. NP 문제의 특징은 해답을 찾는 것은 어려울 수 있지만, 제시된 해답이 올바른지는 다항 시간 안에 쉽게 검증할 수 있다는 점이다.

자연수의 소인수분해 문제: 어떤 자연수를 소인수분해하는 것은 매우 오래 걸릴 수 있다. 예를 들어 100자리 숫자의 소인수분해는 어렵다. 하지만 만약 어떤 수들이 특정 자연수의 소인수분해 결과라고 제시된다면, 단순히 그 수들을 곱해보는 것만으로 원래 자연수가 나오는지, 즉 소인수분해가 올바르게 되었는지 다항 시간 안에 검증할 수 있다. 따라서 소인수분해 관련 결정 문제는 NP에 속한다.

해밀턴 회로 문제: 주어진 그래프에서 모든 정점을 정확히 한 번씩 방문하고 시작점으로 돌아오는 경로(해밀턴 회로)가 존재하는지 묻는 문제이다. 만약 어떤 경로가 해밀턴 회로라고 제시되면, 그 경로가 실제로 모든 정점을 한 번씩 지나 시작점으로 돌아오는지 다항 시간 안에 검증할 수 있다. 이처럼 해답(경로)의 검증이 쉽기 때문에 해밀턴 회로 문제는 NP에 속한다.

합성수 판정 문제와 소수 판정 문제: 어떤 수가 합성수인지 판정하는 문제는 그 수의 약수가 증거로 제시되면 다항 시간 안에 검증 가능하므로 NP에 속한다. 그 보문제인 소수 판정 문제 역시, 정수론의 결과에 따라 특정 정보(예: $p-1$ 의 완전한 소인수분해와 원시근)가 주어지면 다항 시간 안에 검증 가능하여 NP에 속한다. 두 문제 모두 NP에 속하므로, 이들은 $\textsf{NP}\cap\textsf{co-NP}$ 에 속한다. (현재 소수 판정 문제는 AKS 소수판별법의 발견으로 P에 속하는 것으로 증명되었다^[14].)

NP에 속하지만 P에 속하는 것이 증명되지 않은 문제 중 상당수는 NP-완전 문제이다. P에도 NP-완전에도 속하지 않는 문제의 후보로는 그래프 동형성 판정 문제가 있다.

3. 1. 해밀턴 경로 문제

해밀턴 회로 문제는 주어진 그래프에 대해 모든 정점을 정확히 한 번씩 통과하는 회로(해밀턴 회로)가 존재하는지를 묻는 문제이다.^[11] 만약 그러한 회로가 실제로 존재한다면, 그 회로가 정말로 모든 정점을 한 번씩 통과했는지 다항 시간 안에 쉽게 검증할 수 있다. 이처럼 해밀턴 회로 자체를 '증거'로 삼아 문제의 답이 '예'임을 확인할 수 있기 때문에, 해밀턴 회로 문제는 NP에 속한다.^[11] 여기서 중요한 점은, 해밀턴 회로를 직접 찾는 계산의 어려움은 고려하지 않고, 단지 회로가 주어졌을 때 그것이 올바른 해밀턴 회로인지 검증하는 것이 다항 시간 내에 가능한지만 본다는 것이다. 또한, 답이 '아니오'인 경우, 어떤 경로를 제시해도 검증 과정에서 해밀턴 회로라고 잘못 판단되지 않아야 한다.^[11]

3. 2. 소수 판정 문제

합성수 판정 문제는 어떤 수가 합성수임을 보이는 인수가 증거가 되기 때문에 '''NP'''에 속한다는 것을 쉽게 알 수 있다. 하지만 그 보문제인 소수 판정 문제에서는 이처럼 직관적이고 알기 쉬운 증거가 오랫동안 알려져 있지 않았다.

정수론에 따르면, 홀수

p

가 소수임을 다항 시간 안에 검증하기 위해서는

p-1

의 완전한 소인수분해와 원시근이 주어져야 한다. 하지만 이것만으로는 충분하지 않은데,

p-1

의 소인수분해가 정말로 소인수들로만 이루어졌는지 검증하는 과정이 추가로 필요하기 때문이다. 다행히 이 검증 과정을 재귀적으로 수행하면 전체적으로

p

가 소수임을 다항 시간 안에 검증할 수 있다. 따라서 소수 판정 문제는 '''NP'''에 속한다.

합성수 판정 문제 역시 '''NP'''에 속하므로, 소수 판정 문제는 그 보문제와 함께 '''NP'''와 '''co-NP''' 모두에 속하는 문제, 즉

\textsf{NP}\cap\textsf{co-NP}

에 속한다는 것을 알 수 있다. 현재는 AKS 소수판별법의 발견으로 소수 판정 문제가 '''P'''에 속한다는 것이 증명되었다^[14]。

3. 3. 합성수 판정 문제

합성수 판정 문제는 어떤 수의 약수가 주어지면 그 수가 합성수인지 쉽게 검증할 수 있으므로 '''NP'''에 속한다. 예를 들어, 어떤 큰 수가 주어졌을 때 그 수의 약수를 함께 제시하면, 두 수를 곱해보는 것만으로 약수 관계가 맞는지, 즉 원래 수가 합성수인지 다항 시간 안에 확인할 수 있다.

이 문제의 보문제인 소수 판정 문제의 경우, 합성수 문제처럼 직관적인 증거가 바로 알려져 있지는 않았다. 그러나 정수론의 결과에 따라, 어떤 홀수

p

에 대해

p-1

의 완전한 소인수분해 결과와 원시근이 주어진다면,

p

가 소수임을 다항 시간 안에 검증하는 것이 가능하다. 엄밀하게는

p-1

의 소인수분해 결과가 정말로 모두 소수인지 추가 검증이 필요하지만, 이 검증 과정을 재귀적으로 수행하면 전체적으로

p

가 소수임을 다항 시간 내에 검증할 수 있다. 따라서 소수 판정 문제 역시 '''NP'''에 속한다.

합성수 판정 문제와 소수 판정 문제가 모두 '''NP'''에 속하므로, 두 문제는 NP ∩ co-NP에 포함된다. 이후 소수 판정 문제는 '''P'''에 속한다는 사실이 증명되었다.^[14]

3. 4. 정수 인수분해 문제

정수 인수분해 문제는 주어진 정수 ''n''과 ''k''에 대해, 1 < ''f'' < ''k''를 만족하면서 ''n''을 나누는 인수 ''f''가 존재하는지를 묻는 결정 문제이다.^[11] 이 문제는 NP에 속한다. 즉, 어떤 수 ''f''가 ''n''의 인수인지 확인하는 것은 다항 시간 안에 가능하지만, ''n''의 인수를 찾는 효율적인 알고리즘은 아직 알려지지 않았다.

3. 5. 외판원 문제 (결정 버전)

외판원 문제의 결정 버전은 '''NP'''에 속한다. ''n''개의 도시 간 거리를 나타내는 입력 행렬이 주어졌을 때, 문제의 목표는 모든 도시를 방문하는 총 거리가 ''k'' 미만인 경로가 존재하는지 결정하는 것이다.

만약 조건을 만족하는 경로가 존재한다면, 그 경로(도시 방문 순서 목록)를 증거로 제시할 수 있다. 이 증거가 올바른지 검증하는 과정, 즉 제시된 경로를 따라 도시 간 거리를 모두 더해서 총 거리가 ''k'' 미만인지 확인하는 계산은 다항 시간 내에 명확하게 수행될 수 있다. 따라서 외판원 문제의 결정 버전은 '''NP'''에 속한다.

결정 버전의 외판원 문제를 반복적으로 호출하면 최적화 버전 문제(가장 짧은 경로 찾기)도 해결할 수 있다. 예를 들어, 가능한 거리 범위에 대한 이진 검색을 통해 결정 버전을 다항식 횟수만큼 호출함으로써 최단 거리를 찾을 수 있다.^[10]^[11]

3. 6. 부분 그래프 동형 문제

그래프 G가 그래프 H와 동형인 부분 그래프를 포함하는지 여부를 결정하는 부분 그래프 동형 문제이다.^[12]

4. NP와 관련된 복잡도 종류

P, NP, co-NP, BPP, P/poly, PH, PSPACE를 포함한 복잡도 종류들의 포함 관계

NP는 여러 중요한 복잡도 종류와 관련이 있다.

'''P''': 모든 P 문제는 NP에 포함된다( $\mathsf{P \subseteq NP}$ ). 이는 P 문제가 다항 시간 안에 풀리기 때문에, 주어진 증명을 무시하고 직접 문제를 풀어 검증할 수 있기 때문이다.
'''PSPACE''': NP는 PSPACE에 포함된다( $\mathsf{NP \subseteq PSPACE}$ ). 이는 모든 가능한 증명 문자열을 다항 공간 내에서 확인하는 기계를 구성할 수 있기 때문이다. 다항 시간 기계는 다항식 개수의 비트만 읽을 수 있으므로 다항 공간 이상을 사용할 수 없고, 다항 공간 이상을 차지하는 증명 문자열도 읽을 수 없다.
'''EXPTIME''': NP는 EXPTIME에도 포함된다( $\mathsf{NP \subseteq EXPTIME}$ ). NP 문제를 검증하는 알고리즘은 지수 시간 내에 작동하기 때문이다.

'''co-NP'''는 어떤 문제의 답이 '아니오'일 때, 그 답이 맞다는 것을 다항 시간 안에 검증할 수 있는 짧은 증명(반례)이 존재하는 문제들의 집합이다. 예를 들어, 소수 판별법은 어떤 수가 소수가 아님을 증명하기 위해 약수를 제시하면 되므로 co-NP에 속한다. NP와 co-NP는 함께 다항식 계층의 첫 번째 수준을 형성한다.

검증 단계에서 결정론적 기계 대신 확률적 기계를 사용하는 경우(이는 반드시 BPP 기계는 아니다^[7]), '''MA'''라는 복잡도 종류를 얻게 된다. 이는 아서가 멀린에게 통신하지 않는 아서-멀린 프로토콜을 사용하여 해결할 수 있는 문제들의 집합이다.

'''BPP'''(유계 오차 확률적 다항 시간)와 '''NP''' 사이의 관계는 아직 밝혀지지 않았다. '''BPP'''가 '''NP'''의 부분집합인지, '''NP'''가 '''BPP'''의 부분집합인지, 아니면 서로 포함 관계가 없는지는 알려지지 않은 상태이다. 만약 '''NP'''가 '''BPP'''에 포함된다면(

\mathsf{NP \subseteq BPP}

), 이는 NP-완전 문제에 대한 효율적인 확률적 해법이 존재함을 의미하므로 가능성이 낮다고 여겨진다. 이 경우 '''NP''' = '''RP'''이고 '''PH''' ⊆ '''BPP'''가 성립한다.^[8]

NP는 결정 문제의 종류인 반면, 이와 유사한 함수 문제의 종류로는 '''FNP'''가 있다.

현재까지 알려진 NP와 다른 복잡도 종류 간의 엄격한 포함 관계는 다음과 같다. 이는 각각 시간 계층 정리와 공간 계층 정리에서 비롯된다.

$\mathsf{NP \subsetneq NEXPTIME}$
$\mathsf{NP \subsetneq EXPSPACE}$

4. 1. P (복잡도)

'''P'''는 결정적 튜링 머신을 사용하여 다항 시간 내에 풀 수 있는 결정 문제의 클래스이다.

P에 속하는 모든 문제는 NP에도 속하며, 이는

\mathsf{P \subseteq NP}

로 표기한다. 왜냐하면 '''P'''에 속하는 문제에 대한 증명서가 주어졌을 때, 그 증명서를 무시하고 다항 시간 내에 문제를 직접 해결함으로써 답을 검증할 수 있기 때문이다.

정의에 따라 분명히

\textsf{P} \subseteq \textsf{NP}

이지만,

\textsf{P} = \textsf{NP}

인지 아니면

\textsf{P} \neq \textsf{NP}

인지는 아직 해결되지 않은 컴퓨터 과학의 중요한 미해결 문제이다(P-NP 문제).

4. 2. co-NP

co-NP는 어떤 결정 문제의 답이 '아니오'일 때, 그 답이 맞다는 것을 다항 시간 안에 검증할 수 있는 짧은 증명(반례라고도 함)이 존재하는 문제들의 집합이다. 예를 들어, 소수 판별법 문제는 co-NP에 속하는데, 어떤 정수가 소수가 아님을 증명하기 위해 1과 자기 자신 외의 약수(자명하지 않은 인수)를 제시하면 쉽게 검증할 수 있기 때문이다.

정의상 co-NP는 NP에 속하는 문제들의 보 문제들의 집합이다. 즉, 어떤 언어 L이 NP에 속한다면, L의 여집합

\bar{L}

은 co-NP에 속한다.

:

\textsf{co-NP} = \{\bar{L} | L \in \textsf{NP} \}

NP와 co-NP는 모두 P 문제를 포함하며, P보다는 크거나 같은 복잡도 종류로 여겨진다. 이 둘은 함께 다항식 계층의 첫 번째 수준을 형성한다. 구체적으로

\textsf{NP} = \Sigma_1^{\rm P}

이고,

\textsf{co-NP} = \Pi_1^{\rm P}

이다.

만약 NP = co-NP 가 성립한다면, 다항식 계층 전체가 첫 번째 수준으로 붕괴되어

\textsf{NP} = \textsf{PH}

가 된다. 그러나 NP와 co-NP가 같은지는 아직 증명되지 않은 중요한 미해결 문제이며, P-NP 문제와 깊은 관련이 있다. 많은 컴퓨터 과학자들은 이 두 복잡도 종류가 다르다고 추측하며, 이는 다항식 계층이 붕괴되지 않을 것이라는 예상으로 이어진다.

4. 3. NP-완전 (NP-complete)

NP-완전 (NP-complete) 문제의 집합은 NP의 부분 집합으로, 비공식적으로 NP에서 "가장 어려운" 문제들로 설명될 수 있다. 어떤 문제가 NP-완전이라는 것은, NP에 속하는 모든 문제가 다항 시간 안에 이 문제로 환원될 수 있음을 의미한다.^[1] 만약 NP-완전 문제 중 하나라도 다항 시간 안에 풀 수 있는 알고리즘이 존재한다면, NP에 속하는 모든 문제에 대한 다항 시간 알고리즘이 존재하게 되며, 이는 곧 '''P'''=NP임을 의미한다.

이러한 중요성 때문에 NP-완전 문제에 대한 다항 시간 알고리즘을 찾기 위한 많은 연구가 진행되었지만, 아직 성공하지 못했다. 따라서 어떤 문제가 NP-완전임이 증명되면, 해당 문제에 대한 효율적인 (다항 시간 내에 해결하는) 알고리즘은 존재하지 않을 가능성이 높다고 여겨진다.

그러나 실제 문제 해결 과정에서는 최적의 해를 찾는 대신, 근사 알고리즘 등을 사용하여 다항 시간 내에 충분히 좋은 해를 찾는 방법을 사용하기도 한다. 또한 일부 문제의 실제 응용 분야는 이론적인 경우보다 더 쉽게 해결될 수도 있다.

NP-곤란 (NP-hard)은 NP에 속하는 임의의 문제와 적어도 동등하거나 더 어려운 문제들의 집합을 의미하며, NP-완전 문제는 NP-곤란 문제 중에서 NP에 속하는 문제들을 가리킨다. 이러한 개념은 다항 시간 환원을 통해 엄밀하게 정의된다.

대표적인 NP-완전 문제로는 충족 가능성 문제 (SAT)가 있다. SAT 문제는 명제 논리에서 주어진 논리식을 참으로 만드는 변수 값 할당이 존재하는지를 묻는 문제이다.^[9] 쿠크-레빈 정리는 SAT 문제가 NP-완전임을 증명한 중요한 결과이다. 이 외에도 많은 문제들이 NP-완전임이 알려져 있다.

NP-완전 문제 중 하나라도 P에 속한다는 것이 증명되면 P=NP가 성립하지만, 아직 그러한 문제는 발견되지 않았다. 이는 컴퓨터 과학 분야의 가장 중요한 미해결 문제 중 하나이다.

4. 4. NP-난해 (NP-hard)

NP 곤란(NP-hard)은 NP에 속하는 임의의 문제와 비교했을 때, 적어도 그만큼 어려운 문제들의 집합을 가리킨다. 즉, NP에 있는 모든 문제만큼 어렵거나 더 어려운 문제들이 NP-난해에 해당한다. 중요한 점은 NP-난해 문제가 반드시 NP 집합 안에 포함될 필요는 없다는 것이다.

NP-난해 문제들 중에서 특별히 NP에 속하는 문제들을 NP 완전(NP-complete) 문제라고 부른다. NP-난해와 NP 완전이라는 개념은 다항 시간 환원이라는 수학적 방법을 사용하여 정확하게 정의된다. 예를 들어, 유명한 충족 가능성 문제(SAT)는 '''NP''' 완전 문제에 속하는 것으로 알려져 있다(쿡-레빈 정리).

만약 '''NP''' 완전 문제 중 단 하나라도 P(다항 시간 내에 해결 가능한 문제들의 집합)에 속한다는 사실이 증명된다면, 이는 곧 '''P'''='''NP'''라는 결론으로 이어지게 된다. 하지만 현재까지 이러한 '''NP''' 완전 문제는 발견되지 않았으며, 이는 컴퓨터 과학 분야의 중요한 미해결 문제 중 하나이다.

4. 5. 다항식 계층 (Polynomial Hierarchy)

'''P'''는 결정적 튜링 기계를 사용하여 다항 시간 안에 풀 수 있는 문제들의 집합이다. 정의에 따라

\textsf{P} \subseteq \textsf{NP}

임은 분명하지만,

\textsf{P} \neq \textsf{NP}

인지 여부는 아직 해결되지 않은 중요한 문제이다(P-NP 문제). 또한 '''co-NP'''는 '''NP'''에 속하는 문제들의 여집합 문제들로 이루어진 집합이다. 즉, 어떤 언어 L이 NP에 속할 때, 그 여집합

\bar{L}

은 co-NP에 속한다.

:

\textsf{co-NP} = \{\bar{L} | L \in \textsf{NP} \}

이들 복잡도 종류 P, NP, co-NP는 다항식 계층이라는 더 큰 구조의 일부를 형성한다. 다항식 계층은 P를

\Sigma_0^{\rm P} = \Pi_0^{\rm P}

로 정의하고, 점화적으로 더 복잡한 문제들의 집합을 정의하여 만들어진다.

:

\Sigma_0^{\rm P} \subseteq \Sigma_1^{\rm P} \subseteq \Sigma_2^{\rm P} \subseteq \ldots

:

\Pi_0^{\rm P} \subseteq \Pi_1^{\rm P} \subseteq \Pi_2^{\rm P} \subseteq \ldots

이 계층 구조에서 모든 복잡도 종류의 합집합을 '''PH'''(Polynomial Hierarchy)라고 표기한다. 이때,

\textsf{NP}

는

\Sigma_1^{\rm P}

와 같고,

\textsf{co-NP}

는

\Pi_1^{\rm P}

와 같다.

만약 어떤 자연수 ''k''에 대해

\Sigma_k^{\rm P} = \Sigma_{k+1}^{\rm P}

가 성립하면, 이는

\Sigma_k^{\rm P} = \Pi_{k}^{\rm P}

와 동치이며, 이때 "다항식 계층이 제 ''k''층에서 붕괴된다"고 말한다. 다항식 계층의 붕괴는 P-NP 문제와 밀접한 관련이 있다.

만약 $\textsf{P} = \textsf{NP}$ 라면, 다항식 계층은 완전히 붕괴하여 모든 ''k'' ≥ 0에 대해 $\Sigma_k^{\rm P} = \Pi_k^{\rm P} = \textsf{P}$ 가 되며, 결과적으로 $\textsf{NP} = \textsf{co-NP} = \textsf{PH} = \textsf{P}$ 가 성립한다.
만약 $\textsf{NP} = \textsf{co-NP}$ 라면, 다항식 계층은 제1층에서 붕괴하여 모든 ''k'' ≥ 1에 대해 $\Sigma_k^{\rm P} = \Pi_k^{\rm P} = \textsf{NP}$ 가 되며, 결과적으로 $\textsf{NP} = \textsf{PH}$ 가 성립한다.

따라서 P≠NP 문제는 다항식 계층이 완전히 붕괴되지 않을 것이라는 예상과 연결된다. 대부분의 계산 복잡도 이론가들은 다항식 계층이 어느 층에서도 붕괴되지 않을 것이라고 추측하지만, 이는 아직 증명되지 않은 미해결 문제이다. 다항식 계층이 붕괴되지 않는다는 가설은 P≠NP라는 가설을 뒷받침하는 근거 중 하나로 여겨진다.

4. 6. NEXPTIME과 EXPSPACE

NEXPTIME은 비결정적 튜링 기계를 사용하여 지수 시간 내에 풀 수 있는 문제의 종류이며, 시간 계층 정리에 따라

\mathsf{NP \subsetneq NEXPTIME}

임을 알 수 있다. 또한, EXPSPACE는 결정적 튜링 기계의 지수 크기의 공간을 사용하여 풀 수 있는 문제의 종류이며, 공간 계층 정리에 따라

\mathsf{NP \subsetneq EXPSPACE}

임을 알 수 있다.

5. 성질

NP는 합집합, 교집합, 연결, 클레이니 스타 및 역 연산에 대해 닫혀 있다. NP가 여집합 연산에 대해 닫혀 있는지는 아직 알려지지 않았으며, 이는 "NP 대 co-NP 문제"로 알려진 중요한 미해결 문제이다.

6. 다른 표현

기술적 복잡도 이론 측면에서 NP는 존재 2차 논리 (파긴의 정리)에 의해 정의될 수 있는 언어 집합과 정확히 일치한다.

NP는 증명자가 증명서를 제시하고 검증자가 이를 확인하는 결정적 다항 시간 기계인 매우 단순한 유형의 대화형 증명 시스템으로 볼 수 있다. 적절한 증명 문자열이 있으면 이를 수용하므로 완전하며, 수용 가능한 증명 문자열이 없으면 검증자가 이를 수용할 수 없으므로 건전하다.

복잡도 이론의 주요 결과는 NP가 검증자가 O(log ''n'')개의 임의 비트를 사용하고 증명 문자열의 상수 개수 비트만 검사하는 확률적 검사 증명으로 해결 가능한 문제로 특징지을 수 있다는 것이다 (클래스 '''PCP'''(log ''n'', 1)). 더 비공식적으로 말하면, 이는 위에서 설명한 NP 검증기를 증명 문자열의 몇몇 위치를 "임의로 검사"하고 제한된 수의 동전 던지기를 사용하여 높은 확률로 정확한 답을 결정할 수 있는 검증기로 대체할 수 있다는 것을 의미한다. 이를 통해 근사 알고리즘의 경도에 대한 몇 가지 결과를 증명할 수 있다.

다항 시간 검증 가능하다는 측면에서 '''NP'''를 생각하면, 대화 증명으로 간주할 수도 있다. '''AM'''은 ('''P'''를 '''BPP'''로 확장한 것처럼) '''NP'''에서 확률적인 행동을 허용하도록 한 클래스이다. PCP 정리는 $\textsf{NP} = \textsf{PCP}(O(\log n), O(1))$ 을 보여준다.

7. 정의의 동등성

'''NP'''는 두 가지 방식으로 동등하게 정의될 수 있다.

첫 번째 정의는 비결정적 튜링 기계를 사용한다. '''NP'''는 NTIME을 사용하여 다음과 같이 정의된다.^[13]

: $\mathsf{NP} = \bigcup_{k\in\mathbb{N}} \mathsf{NTIME}(n^k)$

여기서 $\mathsf{NTIME}(n^k)$ 는 비결정적 튜링 기계가 $O(n^k)$ 시간, 즉 다항 시간 안에 해결할 수 있는 결정 문제의 집합이다. '''NP'''라는 명칭 자체도 '비결정적 다항 시간'(Non-deterministic Polynomial time^eng)의 약자이다.

두 번째 정의는 결정적 튜링 기계를 '검증기'(verifier)로 사용하여 정의한다. 어떤 언어 ''L''이 '''NP'''에 속한다는 것은, 다음 조건을 모두 만족하는 다항식 ''p''와 ''q'', 그리고 결정적 튜링 기계 ''M''이 존재한다는 의미이다.

모든 입력 ''x''와 '증거'(certificate) 문자열 ''y''에 대해, 기계 ''M''은 입력 $(x,y)$ 에 대해 다항 시간 ''p''(|''x''|) 안에 실행을 마친다.
언어 ''L''에 속하는 모든 원소 ''x''에 대해, $M(x, y) = 1$ (참 또는 '수용')을 만족하는 길이 ''q''(|''x''|) 이하의 증거 문자열 ''y''가 존재한다. 이 문자열 ''y''는 ''x''가 ''L''에 속한다는 증거 또는 증인(witness)이라고 불린다.
언어 ''L''에 속하지 않는 모든 원소 ''x''에 대해서는, 길이 ''q''(|''x''|) 이하의 모든 증거 문자열 ''y''에 대해 $M(x, y) = 0$ (거짓 또는 '거부')이다.

이 두 정의는 서로 동등하다. 즉, 비결정적 튜링 기계(TM)로 다항 시간 안에 풀 수 있는 문제는 결정적 튜링 기계로 다항 시간 안에 검증할 수 있으며, 그 역도 성립한다. 이 동등성에 대한 증명은 마이클 셉서(Michael Sipser)의 ''계산 이론 입문''(Introduction to the Theory of Computation^eng) 7.3절과 같은 여러 계산 복잡도 이론 교과서에서 찾아볼 수 있다.

동등성을 보이는 간략한 아이디어는 다음과 같다.

(검증기 정의 ⇒ 비결정적 기계 정의): 만약 어떤 언어 L에 대해 다항 시간 검증기 M이 존재한다면, L을 다항 시간 안에 푸는 비결정적 튜링 기계 A를 만들 수 있다. A는 입력 x를 받으면, 가능한 모든 증거 문자열 y (길이가 다항식으로 제한됨)를 비결정적으로 추측하여 생성한 뒤, 각 y에 대해 검증기 M(x, y)를 실행한다. 만약 어떤 y에 대해 M이 1을 반환하면 (즉, 유효한 증거를 찾으면), A는 입력을 수용(accept)한다. 만약 모든 가능한 y에 대해 M이 0을 반환하면, A는 입력을 거부(reject)한다. 증거의 길이가 다항식이고 M의 실행 시간도 다항 시간이므로, 전체 과정은 비결정적 다항 시간 안에 끝난다.

(비결정적 기계 정의 ⇒ 검증기 정의): 만약 어떤 언어 L을 다항 시간 안에 푸는 비결정적 튜링 기계 A가 존재한다면, L을 위한 다항 시간 검증기 M을 만들 수 있다. 비결정적 기계 A가 입력 x를 수용한다는 것은, A의 여러 계산 트리 경로 중 적어도 하나가 '수용' 상태로 끝난다는 의미이다. 이 '수용 경로' 자체를 증거 문자열 y로 사용할 수 있다. 검증기 M은 입력 x와 증거 문자열 y를 받아서, 비결정적 기계 A의 계산 과정을 결정적으로 시뮬레이션하되, y에 명시된 경로만을 따라간다. 만약 시뮬레이션 결과 A가 수용 상태에 도달하면, M은 1을 반환한다. 만약 y가 유효한 수용 경로가 아니거나, A가 원래 x를 거부하는 경우 (수용 경로가 없는 경우), M은 항상 0을 반환할 것이다. A가 다항 시간 기계이므로, 수용 경로의 길이도 다항식이고, 시뮬레이션 시간도 다항 시간이다.

이처럼 '''NP'''는 문제를 푸는 데 걸리는 시간(비결정적)과 해답을 검증하는 데 걸리는 시간(결정적)이라는 두 가지 관점에서 동일하게 정의될 수 있다.

8. 다른 클래스와의 관계

컴퓨터 과학 문제 중 상당수는 NP에 속하며, 이는 많은 탐색 및 최적화 문제의 결정 버전과 같다.

NP는 모든 P 문제를 포함한다. 왜냐하면 P 문제는 결정론적 다항 시간 안에 풀 수 있으므로, 그 해답(증명)을 무시하고 그냥 문제를 풀어보는 것만으로도 다항 시간 안에 검증할 수 있기 때문이다.

NP는 PSPACE에도 포함된다. 이는 모든 가능한 증명 문자열을 하나씩 시도해보고, 각각을 다항 시간 검증기로 확인하는 PSPACE 기계를 만들 수 있기 때문이다. 다항 시간 검증기는 다항식 개수의 비트만 읽을 수 있으므로, 다항 공간 이상을 사용할 수 없고, 따라서 다항 공간보다 긴 증명 문자열은 고려할 필요가 없다.

NP는 또한 EXPTIME에도 포함된다. 위에서 설명한 PSPACE 기계와 유사한 방식으로, 모든 가능한 증명을 지수 시간 안에 검증하는 알고리즘을 만들 수 있기 때문이다.

co-NP는 '아니오' 답을 가진 문제 인스턴스에 대해 간단한 증명(반례)이 존재하는 문제들의 집합이다. 예를 들어, 소수 판별법 문제는 co-NP에 속한다. 어떤 수가 소수가 아님을 증명하려면, 1과 자기 자신 외의 약수를 하나 제시하면 되기 때문이다. NP와 co-NP는 함께 다항식 계층의 첫 번째 수준을 형성하며, 이는 P보다는 더 복잡한 문제들을 포함한다.

NP는 결정론적 기계를 사용하여 정의된다. 만약 검증기가 확률적인 기계(반드시 BPP 기계는 아님^[7])라면, 이는 '''MA'''라는 복잡도 종류가 된다. MA 문제는 아서-멀린 프로토콜을 사용하여 해결될 수 있다(아서가 멀린에게 통신하지 않는 경우).

'''BPP'''와 '''NP''' 사이의 관계는 아직 알려져 있지 않다. 즉, BPP가 NP의 부분집합인지, NP가 BPP의 부분집합인지, 아니면 서로 포함 관계가 없는지는 미해결 문제이다. 만약 NP가 BPP에 포함된다면, 이는 NP-완전 문제에 대한 효율적인 확률적 알고리즘이 존재한다는 것을 의미하므로, 많은 연구자들은 이것이 사실이 아닐 것이라고 추측한다. 이 경우 NP = RP이고 '''PH''' ⊆ '''BPP'''가 성립한다.^[8]

NP는 결정 문제들의 종류이다. 이와 유사하게, 해답 자체를 찾는 함수 문제들의 종류는 FNP이다.

현재까지 알려진 NP와 다른 복잡도 종류 간의 엄격한 포함 관계는 시간 계층 정리와 공간 계층 정리로부터 나온다. 이 정리들에 따르면, NP는 NEXPTIME에 엄격하게 포함되고(NP ⊂ NEXPTIME), 또한 EXPSPACE에도 엄격하게 포함된다(NP ⊂ EXPSPACE).

참조

_[1] 논문 On the structure of polynomial time reducibility
_[2] 서적 Algorithm Design https://archive.org/[...] Addison-Wesley
_[3] 문서
_[4] 간행물 Algorithms: Design Techniques and Analysis https://books.google[...]
_[5] 논문 The P=?NP poll https://www.cs.umd.e[...] 2002-06
_[6] 서적 Algorithm Design https://archive.org/[...] Addison-Wesley
_[7] 웹사이트 Complexity Zoo:E https://complexityzo[...] 2018-03-23
_[8] 웹사이트 Pulling Out The Quantumness http://weblog.fortno[...] 2005-12-20
_[9] 서적 Complexity of Computer Computations 1972
_[10] 웹사이트 P=? NP https://www.scottaar[...] 2021-04-13
_[11] 웹사이트 P, NP and mathematics – a computational complexity perspective https://www.math.ias[...] 2021-04-13
_[12] 서적 Computers and Intractability: A Guide to the Theory of NP-Completeness W.H. Freeman
_[13] 서적 Introduction to the Theory of Computation Cengage Learning 2012-06-27
_[14] 논문 PRIMES is in P http://www.cse.iitk.[...]
_[15] 웹인용 Proof verification and hardness of approximation problems http://eccc.uni-trie[...] Journal of the ACM 45(3):501-555, 1998. ECCC TR98-008

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com