검수요청.png검수요청.png

NP-완전

위키원
sosodam (토론 | 기여)님의 2020년 7월 23일 (목) 16:07 판
이동: 둘러보기, 검색

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의 형태로 풀리게 된다.[1]

정의

NP-완전은 다음 두 가지의 조건을 만족하는 결정 문제 C의 집합이다. 첫째, C가 NP에 속한다. 둘째, NP에 속하는 모든 문제를 다항 시간 안에 C로 변환할 수 있다. 즉, 다항 시간 환산을 할 수 있다. 여기에서 두 번째 조건은 NP-난해의 정의이고, 즉 NP-완전은 NP-난해 중 NP인 문제들의 집합이다. 또한 위 정의에서 알 수 있듯이, NP-완전인 C를 다항시간 안에 풀 수 있다면 모든 NP-완전 문제를 다항시간 안에 풀 수 있다.[1]

역사

NP-완전이라는 개념은 1971년에 스티븐 쿡(Stephen Cook)이 제시했지만, 그가 용어를 처음 만든 것은 아니다. 1971년 STOC 회의에서는 'NP-완전 문제가 다항식 시간에 결정론적 튜링 기계로 해결될 수 있는가'라는 주제로 컴퓨터 과학자들 사이에 치열한 논쟁이 있었다. 존 홉크로프트(John Hopcroft)는 해당 안건은 어느 쪽이든 그들의 주장에 대한 공식적인 증거를 가지고 있지 않았기 때문에 나중에 해결되도록 연기되어야 한다고 주장했고, 회의 참석자들은 이에 만장일치로 동의했다. 이것은 P=NP의 의문으로 알려져 있다. NP-완전 문제가 다항식 시간에 실제로 해결될 수 있는지 여부를 결정적으로 판단할 수 있는 사람은 아무도 없었으며, 이는 수학의 가장 큰 미해결 문제 중 하나가 되었다.[2] 스티븐 쿡은 충족 가능성 문제(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-완전 문제들을 소개하였다[1]

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

근사 알고리즘

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


각주

  1. ↑ 1.0 1.1 1.2 1.3 NP-완전 위키백과 - https://ko.wikipedia.org/wiki/NP-%EC%99%84%EC%A0%84
  2. ↑ 2.0 2.1 NP-completeness Wikipedia - https://en.wikipedia.org/wiki/NP-completeness
  3. ↑ 근사 알고리즘 위키백과 - https://ko.wikipedia.org/wiki/%EA%B7%BC%EC%82%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

참고자료

같이 보기


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

인공지능 : 인공지능 서비스, 인공지능 로봇, 인공지능 기술 □■⊕, 인공지능 기업, 인공지능 인물
인공지능 기술 AI 워싱 • 랭체인 • 로봇공학 • 로봇기술 • 인지과학 • 자동추론 • 자연어 처리 • 지능 • 지식표현 • 컴퓨터 비전 • 튜링 테스트 • 프롬프트 • 프롬프트 엔지니어링
문자인식과 음성인식 ICR • OCR • OMR • TTS • URL • 글자 • 답변 • 대화 • 동영상 • 디자인 • 맥락 • 문서 • 문자 • 문자인식 • 문자채팅 • 발음 • 번역 • 분류 • 상담 • 소스코드 • 스토리 • 얼굴 • 얼굴인식 • 음성 • 음성채팅 • 음성인식(STT) • 이미지 • 인공어 • 인공지능 음성 • 자막 • 자연어 • 질문 • 채팅 • 코드 • 코딩 • 텍스트 • 통번역 • 통역 • 파일 • 폴더 • 화상채팅 • 화자인식
인공지능 데이터 데이터라벨러 • 데이터라벨링 • 데이터셋 • 돌마 • 벡터 • 벡터DB • 벡터공간 • 스칼라 • 임베딩 • 크라우드워커 • 토큰 • 토큰화
인공지능 학습 ADP • CoLLM • DALL-E • DDPG • DQN • LAM • LMM • SARSA • sLLM • SLM • 강화학습 • 거대언어모델(LLM) • 결정이론적 메타추론 • 계통적 강화학습 • 과적합 • 동적 계획법 • 딥러닝 • 딥큐러닝 • 머신러닝(기계학습) • 메타추론 • 모델 기반 강화학습 • 모델 프리 강화학습 • 미세조정(파인튜닝) • 반영식 아키텍처 • 비지도학습 • 사전학습 • 수시 알고리즘 • 어니 • 에이전트 • 인공지능 학습 • 전이학습 • 준지도학습 • 지도학습 • 추론 • 학습 • 확률적 경사하강법
인공지능 알고리즘 AGI • ANI • ASI • RAG • XAI • 가중치 • 관계형 네트워크(RN) • 뉴런 • 다층퍼셉트론 • 단층퍼셉트론 • 데이터마이닝 • 방사신경망 • 볼츠만 머신 • 분산 샌드박스 • 생성대립신경망(GAN) • 생성형 AI • 수퍼얼라인먼트 • 순전파 • 순환신경망(RNN) • 시그모이드 함수 • 신경망 • 신경망 구조 • 심층신경망(DNN) • 심층신뢰신경망(DBN) • 양방향 비고정값 암호 체계(TSID) • 역전파 • 은닉층 • 인공신경망(ANN) • 인공지능(AI) • 제한 볼츠만 머신(RBM) • 전방전달신경망 • 주의 메커니즘 • 코헨 자기조직 신경망 • 텍스트마이닝 • 트랜스포머 • 파이 • 퍼셉트론 • 합성곱 신경망(CNN)
계산복잡도 NP • NP-완전 • 계산복잡도 • 공간복잡도 • 시간복잡도 • 여 NP • 여 NP-완전
인공지능 프로그램 BCI • GPT • 딥블루 • 딥페이크 • 멀티모달 AI • 모달 • 모달리티 • 모달창 • 알렉스넷 • 어니 • 알파고 • 알파고제로 • 알파폴드 • 왓슨 • 카페 • 컨트롤넷 • 텐서플로 • 텔레파시 • 토치 • 파이토치 • 한돌
인공지능 특징 결정이론 • 계산상의 합리성 • 논리학 • 논리주의자 • 분산성 • 불확실성 • 삼단논법 • 선호도 • 예측곤란성 • 완벽한 합리성 • 유계 합리성 • 이유 불충분의 원리 • 자율성 • 최대기대효용 • 할루시네이션 • 효용이론
인공지능 법적 지위 권리주체성 • 소버린 AI • 전자대리인 • 전자적 인간 • 책임법
위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반
원본 주소 "http://wiki1.kr/index.php?title=NP-완전&oldid=322969"