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-완전이라는 개념은 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-완전 문제 등 현재 알려진 빠른 최적화 알고리즘이 없을 문제에 대해 주로 사용된다

같이 보기

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