맨위로가기

NP-완전

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

NP-완전은 결정 문제의 집합으로, 두 가지 조건을 만족한다. 첫째, 해당 문제가 NP에 속해야 하며, 둘째, NP에 속하는 모든 문제를 다항 시간 안에 해당 문제로 환산할 수 있어야 한다. NP-완전 문제는 NP-난해 문제 중 NP에 속하는 문제들의 집합이며, 이러한 문제는 현재까지 다항 시간 안에 풀 수 있는 알고리즘이 발견되지 않았다. 스티븐 쿡은 1971년에 NP-완전 개념을 처음 제시했으며, 이후 리처드 카프가 21개의 문제를 NP-완전으로 증명했다. NP-완전 문제의 예시로는 불만족 문제, 배낭 문제, 외판원 문제 등이 있다.

더 읽어볼만한 페이지

  • 1971년 컴퓨팅 - 플로피 디스크
    플로피 디스크는 자기 정보를 저장하는 유연한 자기 디스크로 개인용 컴퓨터의 주요 저장매체였으나, 다른 저장매체의 등장으로 사용이 감소하여 현재는 레거시 기술로 여겨지지만 일부 시스템에서 사용되며 디자인은 소프트웨어 인터페이스의 "저장" 아이콘으로 이어지고 있다.
  • NP-완전 문제 - 지뢰 찾기
    지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
  • NP-완전 문제 - 스도쿠
    스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.
  • 복잡도 종류 - P (복잡도)
    P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
  • 복잡도 종류 - P-NP 문제
    P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
NP-완전
개요
분야계산 복잡도 이론
문제 유형판단 문제
관련 클래스NP
P
NP-hard
정의
설명NP에 속하며, NP에 속하는 모든 문제들이 다항 시간 내에 이 문제로 환원될 수 있는 문제
조건NP에 속해야 함
NP에 속하는 모든 문제가 해당 문제로 다항 시간 내에 환원 가능해야 함
역사
최초 발견스티븐 쿡 (1971년)
중요 공헌리처드 카프 (1972년, 21개의 NP-완전 문제 제시)
예시
대표적인 문제SAT (boolean satisfiability problem, 논리식 만족성 문제)
그래프 색칠 문제
외판원 문제
부분 집합 합 문제
클리크 문제
중요성
의의만약 NP-완전 문제 중 하나라도 다항 시간 알고리즘이 존재한다면, P=NP라는 것을 증명할 수 있음
미해결 문제P=NP 문제의 해결에 중요한 단서 제공
관련 개념
관련 용어NP-hard
다항 시간 환원
P versus NP 문제

2. 정의

NP-완전은 다음 조건을 만족하는 결정 문제 ''C''의 집합이다.

# ''C''가 NP에 속한다.

# NP에 속하는 모든 문제를 다항 시간 안에 ''C''로 변환할 수 있다. 즉, 다항 시간 환산을 할 수 있다.

여기서 두 번째 조건은 NP-난해의 정의이고, NP-완전은 NP-난해 중 NP인 문제들의 집합이다. NP-완전인 ''C''를 다항 시간 안에 풀 수 있다면, 모든 NP 문제를 다항 시간 안에 풀 수 있다.

NP-완전 문제는 NP에 속하며, NP는 해답을 다항 시간 내에 확인할 수 있는 모든 결정 문제의 집합이다. ''NP''는 비결정적 튜링 기계에서 다항 시간 내에 해결할 수 있는 결정 문제의 집합으로 정의할 수도 있다. NP에 속하는 문제 ''p''는 NP-완전 문제인데, NP의 다른 모든 문제를 다항 시간 내에 ''p''로 변환(또는 축소)할 수 있기 때문이다.

NP의 모든 문제를 빠르게 해결할 수 있는지는 알려져 있지 않다. 이를 P 대 NP 문제라고 한다. 하지만 ''어떤 NP-완전 문제''라도 빠르게 해결할 수 있다면 ''NP의 모든 문제''를 빠르게 해결할 수 있다. 왜냐하면 NP-완전 문제의 정의에 따르면 NP의 모든 문제는 모든 NP-완전 문제로 빠르게 환원될 수 있기 때문이다(즉, 다항 시간 내에 환원될 수 있다). 이 때문에 NP-완전 문제는 일반적으로 NP 문제보다 ''더 어렵다''고 말한다.

결정 문제 \scriptstyle C가 NP-완비가 되려면 다음 두 가지 조건을 만족해야 한다.[3]

# \scriptstyle C는 NP에 속하고,

# NP에 속하는 모든 문제는 다항 시간 내에 \scriptstyle C로 환원될 수 있다.

\scriptstyle C가 NP에 속한다는 것은 \scriptstyle C에 대한 후보 해답을 다항 시간 내에 검증할 수 있음을 보여줌으로써 증명할 수 있다.

조건 2를 만족하는 문제는 조건 1을 만족하는지와 관계없이 NP-hard라고 한다.[4]

이 정의의 결과는, 만약 \scriptstyle C에 대한 다항 시간 알고리즘(UTM 또는 다른 튜링-동등 추상 기계)이 있다면, NP에 속하는 모든 문제를 다항 시간 내에 풀 수 있다는 것이다.

위에서 제시된 NP-완전의 정의에서 "환원"이라는 용어는 다항 시간 다대일 환원의 기술적 의미로 사용되었다.

다대일 환원 대신 튜링 환원을 사용하여 NP-완전과 유사한 것을 정의한다면, 결과적인 문제 집합은 NP-완전보다 작아지지 않을 것이다. 더 커질지는 아직 미해결 문제이다.

NP-완전을 정의하는 데 종종 사용되는 또 다른 유형의 환원은 로그 공간 다대일 환원이다. 로그 공간에서 수행할 수 있는 모든 계산은 다항 시간 내에도 수행될 수 있으므로, 로그 공간 다대일 환원이 있으면 다항 시간 다대일 환원도 존재한다. 이러한 유형의 환원은 보다 일반적인 다항 시간 다대일 환원보다 더 정교하며, 이를 통해 P-완전과 같은 더 많은 클래스를 구별할 수 있다. 이러한 유형의 환원 하에서 NP-완전의 정의가 변경되는지는 여전히 미해결 문제이다.

3. 역사

NP-완전 개념은 1971년 스티븐 쿡이 처음 제시하였으나, 'NP-완전'이라는 용어 자체는 나중에 도입되었다. 쿡은 충족 가능성 문제(SAT)가 NP-완전 문제의 조건을 만족함을 증명하였다(쿡-레빈 정리). 1972년 리처드 카프는 카프의 21개 NP-완전 문제를 통해 21개의 다른 문제들도 NP-완전임을 증명하였다. 이후 수많은 문제들이 NP-완전으로 밝혀졌으며, 1979년 마이클 게리와 데이비드 S. 존슨은 ''Computers and Intractability: A Guide to NP-Completeness''를 통해 여러 NP-완전 문제들을 소개하였다.

4. NP-난해와의 관계

'''NP-난해'''(NP-hard)는 NP-완전 문제만큼 어렵거나 그보다 더 어려운 문제들을 의미한다.[4] NP-완전 문제는 NP에 속해야 하지만, NP-난해 문제는 NP에 속하지 않아도 된다. 많은 경우 NP-완전과 NP-난해를 혼동하여 사용하기도 한다.

일반적으로 NP-완전 문제는 조합 최적화 문제의 문제 예시에 비용/이득의 임곗값을 부여한 결정 문제로 정의되는 경우가 많기 때문에, NP-완전과 NP-난해를 혼동하기 쉽다.

5. 근사 알고리즘

NP-완전 문제를 다항 시간 안에 푸는 알고리즘은 아직 발견되지 않았고, 그러한 알고리즘이 실제로 존재하는지도 알려져 있지 않다. 하지만, 특정 NP-완전 문제에 대해서는 최적해에 가까운 해를 찾는 근사 알고리즘이 알려져 있다.[6]

NP-완전 문제 해결을 위해 사용되는 방법들은 다음과 같다.


  • 근사 알고리즘: 최적해가 아닌, 최적해에 근접한 해를 찾는다.
  • 확률적 알고리즘: 무작위성을 활용하여 평균 실행 시간을 단축하고, 낮은 확률로 알고리즘이 실패할 수 있도록 한다. 몬테카를로 방법은 효율적인 알고리즘이라고 보기 어렵지만, 유전자 알고리즘과 같은 진화적 접근 방식은 효율적일 수 있다.
  • 제한: 입력 구조를 제한하여 (예: 평면 그래프) 더 빠른 알고리즘을 만들 수 있다.
  • 매개변수 복잡도: 입력의 특정 매개변수가 고정되면 빠른 알고리즘을 찾을 수 있다.
  • 휴리스틱: 많은 경우에 "상당히 잘" 작동하지만, 항상 빠르고 최적의 결과를 보장하지는 않는 알고리즘이다. 메타휴리스틱 방법이 종종 사용된다.


휴리스틱 알고리즘의 예시로, 일부 컴파일러의 레지스터 할당 단계에서 사용되는 O(n\log n) 탐욕적 그래프 채색 알고리즘이 있다. 이 알고리즘은 그래프 채색 문제를 활용한 전역 레지스터 할당 기술이다. 각 변수는 정점으로, 동시에 사용되는 변수들은 간선으로 연결되며, 색상은 각 변수에 할당된 레지스터를 의미한다. 대부분의 RISC 기계는 많은 수의 범용 레지스터를 가지므로, 이러한 휴리스틱 접근 방식은 효과적이다.

6. NP-완전 문제의 예

다음은 대표적인 NP-완전 문제들이다.

NP-완전 문제의 일부와 증명에 사용되는 환원을 나타낸 그림


오른쪽 그림은 일부 NP-완전 문제와 그 문제들의 NP-완전성을 증명하는 데 사용되는 환원을 나타낸다. 그림에서 문제들은 아래에서 위로 환원된다. 이 그림은 문제들 간의 수학적 관계를 나타내는 것은 아니며, 단지 증명에 사용된 환원을 보여줄 뿐이다. 모든 NP-완전 문제 사이에는 다항 시간 환원이 존재한다.

P에 속하는 문제와 NP-완전 문제 사이에는 작은 차이만 있는 경우가 많다. 예를 들어, 3-SAT 문제는 NP-완전이지만, 이보다 제약 조건이 더 강한 2-SAT 문제는 P에 속한다. 그래프를 2가지 색으로 칠하는 문제는 P에 속하지만, 3가지 색으로 칠하는 문제는 평면 그래프에 대해서도 NP-완전이다. 사이클 그래프나 이분 그래프를 확인하는 것은 쉽지만, 최대 이분 그래프나 최대 사이클 부분 그래프를 찾는 것은 NP-완전이다. 배낭 문제의 경우, 최적해에 근접한 해를 다항 시간에 계산할 수 있지만, 최적해를 찾는 것은 NP-완전이다.

NP-완전 문제들은 난이도가 모두 같지 않으며, 최적화 문제로 변환했을 때 근사 가능성이 크게 다를 수 있다.

; 만족성 문제

: 변수 집합 X=\{ x_1, \ldots , x_n \}에 대한 절 C_1, \ldots , C_k의 집합이 주어졌을 때, 모든 절을 참으로 만드는 변수 할당이 존재하는지 묻는 문제이다. SAT라고도 불린다. 각 절의 길이를 3으로 제한한 3-SAT도 NP-완전이며, 다른 문제의 NP-완전성을 증명할 때 자주 사용된다.[19]

; 부분 집합 합 문제

: 정수 w_1, \ldots , w_n과 목표값 W가 주어졌을 때, \{ w_1, \ldots , w_n \}의 부분 집합 중 원소의 합이 정확히 W가 되는 것이 존재하는지 묻는 문제이다.

; 기타

: 테트리스를 비롯한 다양한 퍼즐 게임[24]도 NP-어려움임이 알려져 있다.

6. 1. 결정 문제


  • 충족 가능성 문제(SAT): 주어진 논리식이 참이 되도록 하는 변수 할당이 존재하는지 판별하는 문제이다.
  • 3-SAT: SAT 문제에서 각 절(clause)이 최대 3개의 리터럴(literal)로 구성된 경우이다. 3-SAT 역시 NP-완전 문제이다.[19]
  • 그래프 색칠 문제: 주어진 그래프의 각 정점에 색을 칠할 때, 인접한 정점끼리는 서로 다른 색을 가지도록 해야 한다. 이때 필요한 최소한의 색의 수가 특정 값(k) 이하인지 판별하는 문제이다.
  • 해밀턴 경로 문제: 주어진 그래프에서 모든 정점을 한 번씩만 지나는 경로(해밀턴 경로)가 존재하는지 판별하는 문제이다.
  • 외판원 문제(결정 버전): 주어진 도시들을 모두 방문하고 출발점으로 돌아오는 최단 경로의 길이가 특정 값 이하인지 판별하는 문제이다.
  • 부분 집합 합 문제: 주어진 정수 집합에서 부분 집합의 합이 특정 값이 되는 경우가 존재하는지 판별하는 문제이다.
  • 배낭 문제(결정 버전): 주어진 물건들을 배낭에 담을 때, 무게 제한을 초과하지 않으면서 가치의 합이 특정 값 이상이 되도록 담을 수 있는지 판별하는 문제이다.
  • 정점 덮개 문제: 주어진 그래프에서 모든 간선(edge)을 포함하는 정점(vertex)의 집합 중 최소 크기의 집합(정점 덮개)의 크기가 특정 값 이하인지 판별하는 문제이다.[20]
  • 클리크 문제: 주어진 그래프에서 특정 크기 이상의 클리크(모든 정점 쌍 사이에 간선이 존재하는 부분 그래프)가 존재하는지 판별하는 문제이다.
  • 독립 집합 문제: 주어진 그래프에서 특정 크기 이상의 독립 집합(어떤 두 정점 사이에도 간선이 없는 부분 집합)이 존재하는지 판별하는 문제이다.
  • 시간표 짜기: 주어진 강의, 수강생, 시간 제약 조건하에서 충돌 없이 시간표를 작성할 수 있는지 판별하는 문제이다.[23]

6. 2. 최적화 문제 (결정 문제 변환)

몇몇 NP-완전 문제는 최적화 문제의 형태를 결정 문제로 변환한 것이다. 예를 들어 다음과 같은 문제들이 있다.

  • 정점 덮개 문제: 이 문제의 최적화 버전(가능한 한 적은 정점 수의 점 커버를 구하는 것)은 2-근사 알고리즘을 가진다.[20]
  • 해밀턴 회로 문제: 이 문제의 최적화 버전(가능한 한 최대 차수가 작은 모든 정점 트리를 구하는 것)은 최소 차수 모든 정점 트리 문제라고 불린다.
  • 외판원 문제: 이 문제의 최적화 버전(가능한 한 가중치가 작은 해밀턴 경로를 구하는 것)은 P=NP가 아닌 한 어떤 상수 근사 알고리즘도 가지지 않는 것으로 알려져 있다. 변 가중치가 삼각 부등식을 만족하는 특별한 경우에는 1.5-근사 알고리즘(Christofides의 알고리즘)이 알려져 있다.[21]
  • 배낭 문제: 이 문제의 최적화 버전(가능한 한 가치가 큰 허용 가능한 부분 집합을 구하는 것)은 다항 시간 근사 기법(PTAS)을 가진다. 즉, 임의의 양의 수 0 < \epsilon \leq 1에 대해 (1 - \epsilon)-근사 알고리즘이 존재한다.[22]

7. 성질

모든 NP-완전 문제의 집합(NPC)은 다음 연산에 대해 '''닫혀 있지 않다'''.[16]



NPC가 보수에 대해 닫혀 있는지는 알려져 있지 않다. NPC=co-NPC인 것은 NP=co-NP일 경우에만 해당하며, NP=co-NP는 미해결 문제이기 때문이다.[16]

8. P-NP 문제와 대한민국

P-NP 문제는 NP-완전 문제를 다항 시간 안에 해결하는 알고리즘이 존재하는지, 즉 P와 NP가 같은 집합인지 묻는 문제로, 컴퓨터 과학 분야의 중요한 미해결 문제 중 하나이다. 클레이 수학 연구소는 이 문제에 100만달러의 상금을 걸고 밀레니엄 문제 중 하나로 선정했다.[5] 대한민국에서는 P-NP 문제 해결을 위한 이론적 연구와 함께, NP-완전 문제의 실용적 해결을 위한 알고리즘 개발 및 교육에도 힘쓰고 있다. 특히, 4차 산업혁명 시대를 맞아 소프트웨어 역량 강화의 중요성이 강조되면서 알고리즘 교육과 문제 해결 능력 함양에 대한 관심이 높아지고 있다.

참조

[1] 문서
[2] 서적 Proc. Logic, Methodology, and Philosophy of Science II North Holland
[3] 서적 Handbook of Theoretical Computer Science Elsevier
[4] 서적 Handbook of Theoretical Computer Science Elsevier
[5] 웹사이트 An eminent mathematician claims to have solved one of math's greatest mysteries — and it's one of 6 problems with a $1 million prize https://www.business[...] 2023-04-24
[6] 논문 Improved upper bounds for vertex cover 2010-09-06
[7] 논문 Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem
[8] 논문 Reducing the complexity of reductions
[9] 웹사이트 Mathematical Writing http://tex.loria.fr/[...] MAA 2010-08-27
[10] 논문 A terminological proposal
[11] 웹사이트 http://www.cs.prince[...] 2011-06-07
[12] 뉴스 DNA computer helps travelling salesman http://www.nature.co[...]
[13] 문서
[14] 논문 SIGACT News Complexity Theory Column 76
[15] 간행물 Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5–8 June 2010 Association for Computing Machinery
[16] citation Complexity and Cryptography: An Introduction https://books.google[...] Cambridge University Press
[17] 간행물 The Complexity of Theorem Proving Procedures
[18] 간행물 Reducibility Among Combinatorial Problems https://www.cs.berke[...] Plenum
[19] 서적 アルゴリズムデザイン 共立出版
[20] 서적 近似アルゴリズムデザイン 共立出版
[21] 서적 近似アルゴリズムデザイン 共立出版
[22] 서적 近似アルゴリズムデザイン 共立出版
[23] 서적 チューリングの計算理論入門 講談社 2014-02-20
[24] citation Tetris is Hard, Even to Approximate


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com