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-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다. 그리고 다항식 시간 안에 구할 수 없는 문제들을 다른 다항 시간 안에 풀 수 있는 다른 문제로 환원해서 푸는 문제들을 특별하게 NP-난해(NP-Hard) 문제라고 한다. 다항식 시간안에 도저히 풀 수 없기에 난해라는 이름을 붙였고, 이런 문제들을 위처럼 추측과 검증 과정을 통해서만 결정 해를 구할 수 있다. 그리고, NP 문제이면서 NP-난해 문제를 NP-완전 문제라고 한다. 즉, P-NP 문제는 'NP-완전 문제가 P문제가 맞느냐 아니냐'를 증명하는 것이다.

역사

NP-완전이라는 개념은 1971년에 스티븐 쿡(Stephen Cook)이 제시했지만, 그가 용어를 처음 만든 것은 아니다. 1971년 STOC 회의에서는 'NP-완전 문제가 다항식 시간에 결정론적 튜링 기계로 해결될 수 있는가'라는 주제로 컴퓨터 과학자들 사이에 치열한 논쟁이 있었다. 존 홉크로프트(John Hopcroft)는 해당 안건은 어느 쪽이든 그들의 주장에 대한 공식적인 증거를 가지고 있지 않았기 때문에 나중에 해결되도록 연기되어야 한다고 주장했고, 회의 참석자들은 이에 만장일치로 동의했다. 이것은 P=NP의 의문으로 알려져 있다. NP-완전 문제가 다항식 시간에 실제로 해결될 수 있는지 여부를 결정적으로 판단할 수 있는 사람은 아무도 없었으며, 이는 수학의 가장 큰 미해결 문제 중 하나가 되었다. 스티븐 쿡은 충족 가능성 문제(SAT)가 위 정의의 두 가지 조건을 모두 만족한다는 것을 쿡-레빈 정리(Cook-Levin theorem)를 통해 증명했다. 1972년에 리처드 카프(Richard Karp)는 21가지의 다른 문제들도 마찬가지로 위 두 가지 조건을 만족한다는 것을 증명했다. 쿡이 최초의 NP-완전 문제를 발견한 이후로, 많은 사람들이 NP-완전 문제라고 이미 알려진 문제로부터 환산하는 방법으로 수많은 문제들 역시 NP-완전임을 증명했다. 마이클 게리(Michael Garey)와 데이비드 존슨(David Johnson)이 1979년에 컴퓨터 및 난해성: NP-완전성 지침서(Computers and Intractability: A Guide to NP-Completeness)를 통해 여러 NP-완전 문제들을 소개하였다.

NP-완전 문제의 예

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

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

P의 문제와 NP-완전성 문제 사이에는 작은 차이만 있는 경우가 많다. 예를 들어 부울만족도 문제의 제한인 3-만족도 문제는 NP-완전 상태로 남아 있는 반면, 약간 더 제한적인 2-만족도 문제는 P(NL-완전)에 있고, 약간 더 일반적인 최대 2-sat. 문제는 다시 NP-완전반적으로 NP-완전이다. 그래프를 2가지 색상으로 채색할 수 있는지 여부를 결정하는 것은 P지만 3가지 색상은 평면 그래프로 제한되어 있더라도 NP-완전하다. 그래프가 사이클인지 또는 양분인지 결정하는 것은 매우 쉽지만(L에서), 최대 양분율 또는 최대 사이클 하위 그래프를 찾는 것은 NP-완전이다. 최적 솔루션의 고정 비율 내에서 배낭 문제의 해결책은 다항 시간 내에 계산할 수 있지만, 최적의 해결책을 찾는 것은 NP-완전이다.

해밀턴 경로

해밀턴 경로(Hamiltonian path)는 1857년 윌리엄 로언 해밀턴이 정십이면체의 그래프 위의 해밀턴 순환을 찾는 문제를 제안하였다. 해밀턴은 이 문제를 아이코시언 게임(영어: icosian game)이라고 불렀다. 모든 꼭짓점을 한 번씩 지나는 경로이다.

거리 공간 외판원 문제

크리스토피데스 알고리즘

크리스토피데스 알고리즘(Christofides algorithm)은 니코 크리스토피데스(Nicos Christofides)에 의해 1976년 개발된 .거리 공간 외판원 문제에서 근사해를 구하는 알고리즘이다. 위 근사 알고리즘은 최대 최적해의 3/2배 길이 안에 근사해를 구할 것을 보장한다. 특정 조건에서의 거리 공간 외판원 문제를 제외한 일반 거리 공간 외판원 문제를 해결하는 가장 좋은 근사해라고 알려져 있다.

알고리즘

외판원 문제 G=(V,w)를 정의해 보자. G는 V의 점들과 점들 사이 변으로 이루어진 완전 그래프이고, w는 G의 모든 변들에 0 이상의 가중치를 부여한다. 이 때 G의 모든 점들 u, v, x에 대해 다음의 삼각 부등식이 성립한다. w(uv) + w(vx) >= w(ux)

크리스토피데스 알고리즘은 다음과 같은 수도 코드로 표현할 수 있다.

1. G의 최소 비용 신장 트리 T를 구한다.
2. T의 홀수 차수 점들의 집합을 O라고 정의하면, O는 악수 보조 정리에 의해 짝수개의 원소를 가지게 된다.
3. O에 의해 형성된 유도 부분 그래프에서 최소 비용의 완벽 부합 M을 찾는다.
4. M과 T의 변들을 합쳐 모든 점들이 짝수 차수를 갖는 다중 그래프 H를 형성한다.
5. H에서 오일러 회로를 구성한다.
6. 5단계에서 찾은 회로에서 반복되는 점들을 제거하여 해밀턴 회로로 변경한다.

근사 비율

위 알고리즘으로 근사 비율은 3/2이다. 이를 증명하기 위해 C를 외판원 문제의 최적해라고 하자.

C에서 임의의 변을 제거하면 신장 트리를 얻을 수 있는데, 이 신장 트리의 비용은 C의 비용보다 작다. (w(T) < w(C))

C의 주위에 순환 순서로 O의 꼭짓점에 숫자를 매기고 C를 다음 두 개의 경로 집합으로 나눈다. 이는 첫 번째 경로 꼭짓점이 홀수인 경로 집합과 첫 번째 경로 꼭짓점이 짝수인 경로 집합이다. 각 경로 집합은 O의 완벽 부합에 상응하는데, 각 경로와 경로의 두 끝점을 일치시켜 완벽 부합을 얻을 수 있다. 이 부합의 가중치는 경로의 가중치와 같아야 한다. 이 두 경로 집합이 C의 변 집합을 분할하기 때문에 두 집합 중 하나는 최대 C의 가중치의 절반을 가지며 해당 완벽 부합 또한 최대 C의 가중치의 절반에 해당하는 가중치를 가진다. w(M) ≤ w(C)/ 2.

T와 M의 가중치를 더해 오일러 경로를 구하면 최대 3w(C)/2의 가중치 변 집합을 얻을 수 있다. 지름길(Shortcutting)은 가중치를 증가시키지 않으므로 출력의 가중치도 최대 3w(C)/2이다.

근사 알고리즘

현재 NP-완전 문제를 다항 시간 안에 푸는 알고리즘은 발견되지 않았고, 또한 그러한 알고리즘이 존재할 것인지도 알려지지 않았다. 대신, 특정한 NP-완전 문제에 대한 근사 알고리즘(approximation algorithm)이 알려져 있다. 근사 알고리즘은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다. 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다. 근사 알고리즘은 NP-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다

근사 비율

근사 알고리즘은 근사해가 얼마나 최적해에 가까운지를 나타내는 근사 비율(Approximation Ratio)을 알고리즘과 함께 제시하여야 한다. 근사 비율은 근사해의 값과 최적해의 값의 비율로서, 1.0에 가까울수록 정확도가 높은 알고리즘이다. 근사 비율을 계산하려면 최적해를 알아야 하는 모순이 생긴다. 따라서 최적해를 대신할 수 있는 ‘간접적인’ 최적해를 찾고, 이를 최적해로 삼아서 근사 비율을 계산한다.

분기 한정법

분기 한정법(Branch and Bound)은 일정한 범위를 정하고 이 안에 해결이 가능한지 분석을 반복적인 시행착오를 통해 해를 구하는 방법이다.

다음은 분기한정법의 대표적인 문제인 '출장 영업사원 문제'(Traveling Salesperson Problem)이다.

외판원 한 명이 1번을 시작점으로 총 다섯 지역을 최소 시간으로 방문하려고 한다. 그리고 지점에서의 거리는 다음과 같다.

0 1 6 2 7

1 0 2 1 7

6 2 0 3 2

8 5 2 0 4

7 3 2 1 0

위는 각 지점에서 다른 지점으로 가는 거리를 나타내는 매트릭스이다. 예를 들어 1번 지점에서 5번 지점으로 가려면 총 7의 시간이 소요되고, 2번에서 4번 지점으로 이동하려면 1의 시간이 소요된다.

분기 한정법은 해를 구하기 위한 범위를 정하는 작업이다. 위 매트릭스의 각 열은 각 정점에서 다른 지역으로 가는데 걸리는 시간을 의미한다. 즉 각 열에서 자기 자신으로 이동하는 0을 제외하고 최소로 방문 하는 정점들을 하나씩 선택하여 최소값을 구할 수 있다. 이 값이 분명 우리가 구하려는 해는 아닐 것이다. 하지만, 해당 거리보다는 분명 크거나 같은 값이 나올 것이다.

첫번째 Bound = min (1, 6, 2, 7) + min (1, 2, 1, 7) + min (6, 2, 3, 2) + min (8, 5, 2, 4) + min (7, 3, 2, 1) = 1 + 1 + 2 + 2 + 2 = 8

두 번째 분기를 설정하기 위해서 하나의 가정을 한다. 1번 정점에서 2번 정점으로 가는데 소요되는 시간은 1이다. 이 경로를 고정 시키고 최소값을 구하는 것이다. 1-2간선은 무조건 간다는 가정 하에 다른 최소 정점들을 구하는 것이다. 2번 정점을 갔다고 가정했으므로 2번 정점으로 가는 간선을 포함하지 않고 최소값을 구하면 된다.

두번째 Bound = (1,2) 시간 + min (2, 1, 7) + min (6, 3 ,2) + min (8, 2, 4) + min (7, 2, 1) = 1 + 1 + 2 + 2 + 2 = 8

두 번째 분기의 경우 1번에서 각 정점을 간다고 예상해야 하므로, 한 번의 계산으로 끝나지 않을 것이다. 위의 계산이 2번 정점을 대상으로 한 것이었고, 똑같이 3, 4, 5에 대해 진행을 해야 한다. 따라서 두 번째 Bound를 모두 진행한다면 2~5번 정점에 대한 분기는 8, 16, 9, 13으로 나오게 되고 (1,2) 정점이 선택되고 두번째 Bound 계산을 마친다.

같은 방법으로 세 번째 Bound를 계산한다. (1, 2)가 선택되었으므로, 1-2-3 / 1-2-4 / 1-2-5 로 간다는 가정 하의 최소 거리들을 구하면 된다.

세번째 Bound (1-2-3) = 1 + (2,3) 시간 + min (6, 3, 2) + min (8, 4) + min (7, 1) = 1 + 2 + 2 + 4 + 1 = 10 세번째 Bound (1-2-4) = 1 + (2,4) 시간 + min (6, 2) + min (8, 2, 4) + min (7, 2) = 1 + 1 + 2 + 2 + 2 = 8 세번째 Bound (1-2-5) = 1 + (2,5) 시간 + min (6, 3) + min (8, 2) + min (7, 2, 1) = 1 + 7 + 3 + 2 + 1 = 14

이렇게 1-2-4의 경로가 선택되었다. 이와 같은 Bound 계산을 지속하면 1->2->4->3->5->1로 돌아오는 것이 최단 경로라는 점을 알 수 있고, 거리는 총 13이다. 이처럼 각 단계별로 가장 짧게 가는 정점을 순차적으로 구하는 방법이 바로 분기한정법이이다.

비 거리 공간 외판원 문제의 근사 불가능성

어떤 변에서는 삼각 부등식이 성립하지 않는 비 거리 공간 외판원 문제는 어떤 최적화 문제에 대해 항상 p배를 벗어나지 않는 근사해를 구하는 알고리즘이 모든 p에 대해 존재하지 않는다.

비 거리 공간 외판원 문제 G를 정의하자.

마찬가지로 해밀턴 회로 판단 문제 G를 정의하고 G로부터 완벽 그래프 G'을 V(G') = V(G)를 만족하도록 골라 가중치 w를 G에 포함된 변일 경우 1, 아닐 경우 kn을 부여한다. 이 때 "G에서 k 다항 시간 근사 해법을 찾을 수 있다"는 명제와 "G'에서 가중치가 kn보다 작은 해밀턴 경로를 찾을 수 있다"는 명제가 동치임을 증명한다. G가 해밀턴 경로를 가지지 않는다면 모든 G'의 해밀턴 경로는 적어도 하나 이상의 G에 포함되지 않은 변을 사용해야하므로 가중치가 kn보다 크다. G가 해밀턴 경로를 가진다면 G'에서도 가중치가 n인 같은 해밀턴 경로 T*를 찾을 수 있다. 그렇다면 다항 시간 근사 해법에 의하면 해밀턴 경로는 최대 k · w(T*) = kn 의 가중치를 가지게 된다. 따라서 비 거리 공간 외판원 문제 G의 근사 알고리즘이 존재한다면, 해밀턴 회로인지 판단하는 문제의 다항 시간 근사 해법이 존재하게 되어 NP-complete인 해밀턴 회로 판단 문제가 P임이 증명되었으므로 P=NP임이 증명되어 모순이다.

참고자료

• NP-완전 위키백과 - https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84
• NP-completeness Wikipedia - https://en.wikipedia.org/wiki/NP-completeness
• 크리스토피데스 알고리즘

위키백과 - https://ko.wikipedia.org/wiki/%ED%81%AC%EB%A6%AC%EC%8A%A4%ED%86%A0%ED%94%BC%EB%8D%B0%EC%8A%A4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

• 박동규 교수, 〈근사 알고리즘〉, 《창원대학교》
• 근사 알고리즘 위키백과 - https://ko.wikipedia.org/wiki/%EA%B7%BC%EC%82%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
• gyulee0220, 〈23. 근사 알고리즘(Approximation Algorithm)〉, 《티스토리》, 2019-02-05

같이 보기

• 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 • GPT • 딥블루 • 딥페이크 • 멀티모달 • 모달 • 모달리티 • 모달창 • 알렉스넷 • 왓슨 • 텔레파시 • 환각 인공지능 법적 지위 권리주체성 • 전자대리인 • 전자적 인간 • 책임법 • 코파일럿 인공지능 업무 데이터라벨러 • 데이터라벨링 • 크라우드워커 위키 : 자동차, 교통, 지역, 산업, 기업, 단체, 업무, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반