NP

NP(Non-deterministic Polynomial time)는 계산 복잡도의 종류 중 하나로, 비결정론적 튜링 기계(NTM)로 다항 시간 안에 풀 수 있는 판정 문제의 집합이다. 비결정론적 다항시간(非決定論的 多項時間)의 약자이다.

개요

계산 복잡성 이론에서 NP는 의사결정 문제를 분류하는 데 사용되는 복잡성 등급이다. NP는 '예'라는 답이 있는 문제 인스턴스가 결정론적 튜링 기계에 의해 다항 시간 내에 검증 가능한 증거를 갖는 의사결정 문제의 집합이다. 또한 NP의 등가 정의는 비결정론적 튜링 기계가 다항 시간 내에 해결할 수 있는 의사결정 문제의 집합이다. 이 두 가지 정의는 튜링 머신을 기반으로 하는 알고리즘이 두 단계로 구성되는데, 그 중 첫 번째 단계는 비결정론적인 방법으로 생성되는 해법에 대한 추측으로 구성되는 반면, 두 번째 단계는 추측이 문제의 해결책인지를 검증하는 결정론적 알고리즘으로 구성되기 때문에 동등하다. 의사결정 문제는 가장 빨리 알려진 알고리즘에 기초하여 복잡성 등급이 할당된다. 따라서 더 빠른 알고리즘이 발견되면 의사결정 문제가 클래스를 변경할 수 있다. 복합성 등급 P(모든 문제 해결 가능, 결정적으로 다항 시간 내에 해결 가능한 문제)가 NP(다항 시간 내에 해결 가능한 문제)에 포함되어 있음을 쉽게 알 수 있는데, 다항 시간 내에 문제를 해결할 수 있다면 해결책도 문제 해결만으로 다항 시간에서 검증이 가능하기 때문이다. 그러나 NP는 더 많은 문제를 포함하고 있다. 다항식 시간에 그러한 문제를 해결하는 알고리즘도 다항식 시간에 다른 NP 문제를 해결할 수 있다. 또한 복잡도 등급 NP는 NTIME의 관점에서 다음과 같이 정의할 수 있다.

${\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k}).$

여기서 ${\mathsf {NTIME}}(n^{k})$는 비결정론적 튜링 기계가 $O(n^{k})$시간 내에 해결할 수 있는 의사결정 문제의 집합이다. 또는 결정론적 튜링 기계를 검증자로 사용하여 NP를 정의할 수 있다. 공식 언어 'L'은 다항식 'p'와 'q'가 존재하는 경우에만 NP로, 다음과 같은 결정론적 튜링 머신 'M'이 있다.

P-NP 문제는 복잡도 종류 P와 NP가 같은지에 대한 컴퓨터 과학의 미해결 문제로 컴퓨터로 풀이법이 빠르게 확인된 문제가 컴퓨터로 빠르게 풀리기도 할 것인가 아닌가를 묻고 있다. 1971년 스티븐 쿡(Steven Cook)이 그의 논문 〈증명 절차의 복잡성(The Complexity of Theorem Proving Procedures)〉에서 처음으로 제안하였고, 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나이며 컴퓨터 과학에서 중요한 위치를 차지하고 있다. 이것은 본래 1956년 쿠르트 괴델(Kurt Gödel)이 존 폰 노이만(John von Neumann)에게 썼던 편지에서 처음으로 언급되었다. 괴델은 어떤 NP 완전 문제가 2차 혹은 선형 시간 안에 풀릴 수 있는지 아닌지를 물었다. P는 결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이고, NP는 비결정론적 튜링 기계를 사용해 다항 시간 내에 답을 구할 수 있는 문제의 집합이다. 여기에서 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로, P는 NP의 부분집합이 된다. 하지만 여기에서 P와 NP가 같은 집합인지, 아니면 P가 NP의 진부분집합인지는 아직 밝혀지지 않았다. 현재 2000년에 클레이 수학연구소가 100만 달러를 걸었다.

배경

많은 검색 및 최적화 문제의 의사결정 버전과 같이 많은 컴퓨터 과학 문제가 NP에 포함되어 있다.

검증자 기반 정의

NP의 검증자 기반 정의를 설명하려면 다음과 같은 부분집합 문제를 고려해야 한다. {-7, -3, -2, 5, 8}의 정수를 제공받았다고 가정해 보자. 이 정수의 일부가 0에 해당하는지 알고자 할 때. 정수 {-3, -2, 5}이 (-3) + (-2) + 5 = 0의 합에 해당하므로, 대답은 '예'이다. 합이 0인 부분집합이 존재하는지 여부를 결정하는 작업을 부분집합문제라고 한다. 정수의 일부가 0에 추가되면 응답하기 위해 가능한 모든 하위 집합을 얻는 알고리즘을 만들 수 있다. 알고리즘에 입력하는 정수의 수가 커질수록 하위 집합의 수와 계산 시간은 기하급수적으로 증가한다. 그러나 특정 부분집합이 주어진 경우 부분집합 정수를 합하여 부분집합 합계가 0인지 여부를 효율적으로 확인할 수 있다는 점에 유의해야 한다. 합이 0이면, 그 부분집합은 대답에 대한 증거나 증인이 된다. 주어진 부분집합에 합이 0인지 여부를 검증하는 알고리즘이 검증자이다. 부분 집합의 정수 합계는 다항 시간에 이루어질 수 있으며, 따라서 부분 집합 합 문제는 NP에 있다. 위의 예는 모든 의사결정 문제에 대해 일반화될 수 있다. 문제 $\Pi$ 및 목격자 W의 I가 있을 경우, 순서 쌍(I, W)을 입력으로 지정하도록 검증자 V가 존재한다면, 증인이 다항식 시간에서 답이 "예" 또는 "아니오"라는 것을 증명하면 V는 다항식 시간 내에 "예"를 반환하고 그렇지 않으면 $\Pi$는 NP에 있다.

기계적 정의

기계적 정의가 검증자 기반 정의에 상당하는 것은 다음과 같은 특성이다. NP는 다항식 시간에 실행되는 비결정론적 튜링 기계로 해결할 수 있는 의사결정 문제의 등급이다. 즉, 의사결정 문제 $\Pi$는 $\Pi$가 어떤 다항 시간 비결정론적 튜링 머신 $M$에 의해 '존재적 허용 조건'으로 인식될 때마다 NP에 있으며, 이는 $M(w)$의 일부 계산 경로가 수용 상태로 이어지는 경우에만 $w\in \Pi$임을 의미한다. 비결정론적 튜링 기계는 비결정론적으로 인증서를 선택하고 인증서에 검증기를 실행함으로써 다항 시간 내에 NP 문제를 해결할 수 있기 때문에 이 정의는 검증자 기반 정의와 동등하다. 마찬가지로 그러한 기계가 존재한다면, 다항식 시간 검증기는 그것으로부터 자연스럽게 구성될 수 있다. 이러한 관점에서 공동 NP를 실존적 거부 조건을 가진 다항 시간 비결정론적 튜링 기계가 인식할 수 있는 의사결정 문제의 등급으로 정의할 수 있다. 실존적 거부 조건은 보편적 수용 조건과 정확히 같은 것이기 때문에 실존적 수용 조건과 보편적 수용 조건이 다항 시간 비결정론적 튜링 기계의 등급에 대해 동일한 표현력을 가지고 있는지를 묻는 것으로 NP 대 공동 NP 질문을 이해할 수 있다.

특징

기준

NP는 계산 복잡성의 중심 역할을 하기 때문에 다음과 같은 몇 가지 등급의 기준으로 사용된다.

• NP: 결정론적 튜링 기계(또는 다항 시간 내에 비결정론적 튜링 기계로 해결 가능)에 의해 다항 시간 내에 해결책으로 검증될 수 있는 결정 문제의 등급이다.
• NP-난해:최소한 NP에서 가장 어려운 문제들만큼 어려운 문제들의 종류이다. NP-난해인 문제들은 NP의 요소가 될 필요가 없다. 왜냐하면 해독될 수 없을지도 모르기 때문이다.
• NP-완전: NP에서 가장 어려운 문제를 포함하는 의사결정 문제의 등급이다. 각 NP 완료 문제는 NP에 있어야 한다.
• NP-Easy: 최대 NP만큼 어렵지만 반드시 NP에 있는 것은 아니다.
• NP-등가: NP-hard와 NP-Easy 둘 다이지만 NP에서는 반드시 그렇지는 않은 의사결정 문제이다.
• NP-중간: P와 NP가 다르면 NP 영역에는 P와 NP-완전성 문제 사이에 속하는 의사결정 문제가 존재한다. P와 NP가 같은 등급이면 NP-중간 문제는 존재하지 않는다. 이 경우 모든 NP-완전 문제는 P에 속하게 되고, 정의상 NP의 모든 문제는 감소될 수 있기 때문이다.

정의의 등가성

다항식 시간에 비결정론적 튜링머신(TM)이 해결할 수 있는 문제 등급으로서의 NP의 두 가지 정의와 다항식 시간에 결정론적 튜링 머신이 검증할 수 있는 문제 등급은 동등하다. 이것을 보여주기 위해 먼저 결정론적 검증기를 가지고 있다고 가정해 보자. 비결정론적 기계는 가능한 모든 증명 문자열에서 비결정론적으로 검증자를 실행할 수 있다. 이것은 각 단계의 증명 문자열에서 비결정적으로 다음 문자를 선택할 수 있기 때문에 다항식적으로 많은 단계만 필요로 하며, 증명 문자열의 길이는 다항식적으로 경계해야 한다. 어떤 증거가 타당하다면 어떤 경로는 수락할 것이고, 증거가 유효하지 않으면 문자열은 언어에 없고 거부될 것이다. 반대로, $A$라는 비결정론적 튜링머신이 주어진 언어 $L$을 받아들인다고 가정하자. 다항식적으로 많은 단계에서 기계의 계산 트리는 최대 한정된 수의 방향으로 분기된다. 적어도 하나의 합격 경로가 있어야 하며, 이 경로를 설명하는 문자열은 검증자에게 제공되는 증명이다. 그런 다음 검증자는 $A$를 결정적으로 시뮬레이션하여 합격 경로만 따르고 마지막에 합격 여부를 검증할 수 있다. $A$가 입력을 거부하면 수용 경로가 없고 검증자는 항상 거부한다.

관계성

NP는 증거를 무시하고 문제를 풀기만 하면 문제의 어떤 인스턴스도 검증할 수 있기 때문에 모든 문제를 P에 담고 있다. 그리고 NP는 PSPACE에 포함되어 있다. 이를 위해 모든 교정 문자열을 루프하고 각 문자열을 다항식 시간 검증기에 공급하는 PSPACE 기계를 제작하기에 충분하다. 다항식 시간 기계는 다항식적으로 많은 비트만 읽을 수 있기 때문에 다항식 공간 이상을 사용할 수 없고, 다항식 공간 이상을 점유하는 교정 문자열을 읽을 수도 없다. 그러므로 이보다 더 긴 증명은 고려하지 않아도 된다. 같은 알고리즘이 지수 시간으로 작동하기 때문에, NP는 EXPTIME에도 포함되어 있다. 여 NP는 어떤 경우를 위한 간단한 증거를 가지고 있지 않고 때로는 반례라고 불리는 문제들을 포함한다. 예를 들어, 소수점 이하 인자를 공급하는 것만으로도 정수의 소수성을 반박할 수 있기 때문에 소수점 이하에서는 소수점 이하인 소수점 이하를 대상으로 한다. NP와 여 NP가 P보다 높은 다항식 계층 구조에서 첫 번째 수준을 형성한다. 또한 NP는 결정론적 기계만을 사용하여 정의된다. 검증자가 확률론적 아서부터 멀린까지의 통신이 없는 아서-머린 프로토콜을 사용하여 클래스 $MA$를 해결할 수 있게 된다. NP는 의사결정 문제의 한 종류이며, 기능 문제의 유사한 종류는 FNP이다. 유일하게 알려진 엄격한 포함은 시간 계층 정리 및 공간 계층 정리에서 나왔으며, 각각 ${\mathsf {NP\subsetneq NEXPTIME}}$ 및 ${\mathsf {NP\subsetneq EXPSPACE}}$이다.

기타 특성화

서술적 복잡성 이론의 측면에서 NP는 실존적 2차 논리(파긴의 정리)에 의해 정의될 수 있는 언어의 집합에 정확하게 대응한다. NP는 매우 단순한 형태의 쌍방향 증명 시스템으로 볼 수 있는데, 검증자는 증명서를 들고 나오고, 검증자는 그것을 확인하는 결정론적 다항식 시간 기계다. 올바른 증빙 문자열이 있으면 받아들이게 되고, 증빙 문자열이 없으면 검증자가 받아들일 수 없기 때문에 건전하기 때문에 완성된다. 복잡성 이론의 주요 결과는 검증자가 $O(log\ n)$ 무작위 비트를 사용하고, 교정 문자열의 일정한 비트 수 $PCP(log\ n,1)$만 검사하는 확률적으로 검사 가능한 증명들에 의해 NP가 해결 가능한 문제로 특징 지어질 수 있다는 것이다. 좀 더 비공식적으로, 이것은 위에서 설명한 NP 검증기를 교정 문자열의 몇 군데를 스폿 점검하는 것으로 교체할 수 있고, 제한된 수의 코인 플립을 사용하면 높은 확률로 정답을 결정할 수 있다는 것을 의미한다. 이를 통해 근사 알고리즘의 경도에 대한 몇 가지 결과가 입증될 수 있다.

유형

NP 완전

NP-완전(NP-complete, NP-C, NPC)은 NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합이다. 모든 NP 문제를 다항 시간 내에 NP-완전 문제로 환산할 수 있다. NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP의 형태로 풀리게 된다. 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP 문제는 P≠NP의 형태로 풀리게 된다. NP-완전은 다음 두 가지의 조건을 만족하는 결정 문제 C의 집합이다. 첫째, C가 NP에 속한다. 둘째, NP에 속하는 모든 문제를 다항 시간 안에 C로 변환할 수 있다. 즉, 다항 시간 환산을 할 수 있다. 여기에서 두 번째 조건은 NP-난해(NP-Hard)의 정의이고, 즉 NP-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다. 그리고 다항식 시간 안에 구할 수 없는 문제들을 다른 다항 시간 안에 풀 수 있는 다른 문제로 환원해서 푸는 문제들을 특별하게 NP-난해 문제라고 한다. 다항식 시간 안에 도저히 풀 수 없기에 난해라는 이름을 붙였고, 이런 문제들을 위처럼 추측과 검증 과정을 통해서만 결정 해를 구할 수 있다. 그리고, NP 문제이면서 NP-난해 문제를 NP-완전 문제라고 한다. 즉, P-NP 문제는 'NP-완전 문제가 P문제가 맞느냐 아니냐'를 증명하는 것이다.

문제 예시

어떤 새로운 문제가 NP-완전임을 것을 증명하기 위한 가장 쉬운 방법은 먼저 해당 문제가 NP에 있다는 것을 증명하고, 그 다음 알려진 NP-완전 문제를 NP-완전성 문제로 줄이는 것이다. 따라서, 다양한 NP-완전 문제를 아는 것이 유용하다. 아래 목록은 의사결정 문제로 표현될 때 몇몇 잘 알려진 NP-완전 문제들이다.

• 부울 만족도 문제(SAT)
• 배낭문제
• 해밀턴 경로 문제
• 출장 세일즈맨 문제(결정 버전)
• 서브그래프 이형성 문제
• 부분집합 문제
• 클라이크 문제
• 정점 커버 문제
• 독립 집합 문제
• 지배적인 세트 문제
• 그래프 컬러링 문제

NP 난해

NP-난해는 NP에 속하는 모든 판정 문제를 다항 시간에 다대일 환산할 수 있는 문제들의 집합이다. 다시 말하면, NP-난해는 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이다. NP-난해 집합에 속하는 문제가 NP에도 속하면 NP-완전에 속한다. 즉, NP-완전은 NP와 NP-난해의 교집합이다. 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-완전이므로 P와 NP는 NP-난해의 부분집합이 되고, P≠NP인 경우는 P와 NP-난해는 서로소가 된다. 반면 NP-난해 집합은 NP에 속하지는 않는다. NP에 속하지 않는 NP-난해 문제의 한 예로는 정지 문제가 있다. 또한, NP-난해 집합은 판정 문제 뿐만이 아니라 최적화 문제 등 다른 형태의 문제가 포함된다. 수학적으로는 다음과 같이 정의한다.

언어 $L$이 $\forall L^{\prime }\in \mathbf {NP} ,L^{\prime }\leq _{p}L\!$이면 $L$은 NP-난해이다.

문제 예시

NP-난해 문제에 들어가는 판정 문제 가운데 대표적인 예로 부분집합 합 문제(SUBSET-SUM)가 있다. 이 문제는 정수 집합이 하나 있을 때, 원소를 모두 더하면 0이 되는, 공집합이 아닌 부분집합이 있는지를 묻는 문제이다. 이 문제는 NP에 들어가므로 NP-완전도 된다. NP-난해이지만 NP-완전은 아닌 판정 문제도 있다. 예를 들어 정지 문제가 있다. "한 프로그램이 있고, 그 프로그램에 대한 입력이 있을 때, 이 프로그램은 영원히 돌 것인가?" 하는 문제이다. 정지 문제가 NP-난해인 것은 NP-완전 문제인 충족 가능성 문제를 정지 문제로 환산하는 것으로 보일 수 있다. 이때 정지 문제의 입력으로 받는 튜링 기계는 입력으로 받은 식에 대해서 식을 만족하는 진리값을 발견할 때에만 멈추고 그렇지 않으면 무한 루프에 빠지도록 설계하면 된다. 또한 정지 문제는 NP에 속하지 않는데, 이것은 NP 문제는 유한 번의 연산으로 판정이 가능하지만 정지 문제는 그렇지 않기 때문이다.

참고자료

• NP (complexity) Wikipedia - https://en.wikipedia.org/wiki/NP_(complexity)
• NP-완전 위키백과 - https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84
• NP-hardness Wikipedia - https://en.wikipedia.org/wiki/NP-hardness
• gyulee0220, 〈근사 알고리즘(Approximation Algorithm)〉, 《티스토리》, 2019-02-05
• Enough is not enough, 〈P문제와 NP문제(NP-hard)〉, 《티스토리》, 2019-02-17

같이 보기

• NP-완전
• 여 NP
• 여 NP-완전

이 NP 문서는 인공지능 기술에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

인공지능 : 인공지능 기술 □■⊕, 인공지능 활용, 인공지능 개발업체, 인공지능 인물 인간적 행위 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 합리적 사고 결정이론 • 논리학 • 논리주의자 • 삼단논법 • 선호도 • 최대기대효용 • 효용이론 강화학습 ADP • DDPG • DQN • SARSA • 결정이론적 메타추론 • 계통적 강화학습 • 동적 계획법 • 모델 기반 강화학습 • 모델 프리 강화학습 • 반영식 아키텍처 • 수시 알고리즘 • 심층믿음망 • 어니 • 에이전트 • 확률적 경사하강법 인공지능 프로그램 A2I • 어니 • 알파고 • 왓슨 • 카페 • 텐서플로 • 토치 • 한돌 인공지능 알고리즘 AGI • 관계형 네트워크(RN) • 다층퍼셉트론 • 데이터마이닝 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 방사신경망 • 분산 샌드박스 • 비지도학습 • 생성대립신경망(GAN) • 생성형 AI • 수퍼 얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그노이드 함수 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 지도학습 • 코헨 자기조직 신경망 • 텍스트마이닝 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN) 문자인식 ICR • OCR • OMR • 문자인식 인공지능 특징 계산상의 합리성 • 분산성 • 불확실성 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 할루시네이션 계산 복잡도 NP • NP-완전 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전 인공지능 기술 BCI • 멀티모달 • 모달 • 모달리티 • 모달창 • 텔레파시 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반