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-완전이다.

근사 알고리즘

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

분기 한정법

분기 한정법(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이다. 이처럼 각 단계별로 가장 짧게 가는 정점을 순차적으로 구하는 방법이 바로 분기한정법이이다.

참고자료

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