[Algorithm] NP-완전 문제 (2)

지난번 NP-완전 문제 (1) 포스팅에 이어서 계속한다.

 

저번 포스팅에서는 결정문제까지 다루었는데, 이번 포스팅에서 다룰 건 아래와 같다.

 

NP-완전(NP-Complete, NP-완비) 문제를 이해하기

• NP-완전 증명 방법을 이해하기
• NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합
• NP-완전이라는 사실이 판명됨으로써 얻을 수 있는 이득을 이해하기

 

 

음 일단 그전에! P와 NP 문제를 이해해보자

 

---

1️⃣ 문제의 분류 ( P와 NP )

P : 다항식 시간복잡도를 가진 알고리즘으로 해결되는 (polynomial) 문제 집합

• [결정문제 관점에서] 결정 문제들 중에서 쉽게 풀리는 것을 모아 놓은 집합. 다항식 시간에 Yes 또는 No 대답을 할 수 있는 문제
• 전산학자들이 제안한 '풀기 쉬운' 문제의 집합

NP : 다항식보다 큰 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합

• Non-Polynomial의 줄임말은 절대 아님! 🚫
• P 문제 집합과 NP-complete (NP-완전) 문제 집합을 둘 다 포함하는 문제의 집합
• 비결정적다항식시간 알고리즘을 가진문제

 

결정문제 관점에서의 NP 문제 집합

• 결정 문제들 중에서 적어도 검산은 쉽게 할 수 있는 것을 모아놓은 집합으로도 정의할 수 있다. 정확히 말하면, 어떤 결정 문제의 답이 Yes일 때, 그 문제의 답이 Yes라는 것을 입증하는 힌트가 주어지면, 그 힌트를 사용해서 그 문제의 답이 정말로 Yes라는 것을 다항식 시간 이내에 확인할 수 있는 문제 -> 쉽게 검증할 수 있는 증명서를 가진 문제
• 어떤 문제들은 다항시간 안에 해를 찾을 수 있는 방법이 알려져 있지 않음. 그렇지만, 해가 무엇인지를 나타내는 정보/근거 주어진다면 해를 다항시간안에 확인하는 것이 가능한 문제들의 집합
• 문제를 풀어 해를 찾기는 쉽지 않지만, 주어진(추측된) 해 정보에 대해서는 답이 맞는지 확인하기는 쉬운 문제
• 주어진 입력에 대해 Yes 대답이 나오는 해를 제공했을 때, 이것이 Yes 대답을 내는 해라는 사실을 다항식 시간에 확인해줄 수 있는 문제

 

NP 알고리즘의 정의 : 비결정적 다항시간 알고리즘

• NP 알고리즘은 해를 찾는 알고리즘이 아니라, 해를 다항식 시간에 확인하는 알고리즘이다. 

1. 추측단계 (비결정적) : 주어진 입력에 대해서 하나의 해를 '추측'한다.
2. 검증단계 (결정적) : 주어진 입력과 추측한 그 해를 입력으로 받아, 다항식 시간에 확인한 후에, 그 해가 '맞다'라고 답을 준다. 즉, 추측한 해가 올바른 해

• NP 알고리즘은 추측한 해를 확인하여 '맞다'라고 답하므로, 문제의 해가 'yes' 혹은 'no'가 되도록 주어진 문제를 변형시켜야한다. 

 

[NP 문제의 직관적인 예]

• '크키가 N인 어떤 정수 집합이 주어졌을 때, 이 집합의 부분집합들 중에서 원소의 합이 0이 되는 집합이 존재하는가?' 라는 문제는 적어도 NP 문제인 것은 확실하지만, 이것이 P 문제인지 아닌지는 아직 모르는 상황이라고 할 수 있다.

 

 

 

전산학에서 문제를 해결하는 다항시간 알고리즘을 만드는 것이 불가능하면 이 문제를 다루기 힘든 (intractable) 문제라 함.

다루기 힘든 정도에 따른 문제의 분류

• 분류 1 : 다항시간 알고리즘이 발견된 문제 -> P
• 분류 2 : 다루기 힘들다고 증명된 문제
  • 비다항식 크기의 결과를 요구하는 문제 예) 해밀토니안 순환경로를 결정하는 문제
  • 요구가 현실적이지만 다항시간 알고리즘이 존재하지 않는다고 증명된 문제
    • 이런 종류의 문제는 아직가지는 별로 없다.
    • 결정불가능한 문제 : 문제를 풀 수 있는 알고리즘 자체가 없다고 증명된 문제 예) 종료문제
• 분류 3: 다루기 힘들다고 증명되지 않았을 뿐만 아니라 다항시간 알고리즘도 발견하지 못한 문제 -> 많은 문제가 이 분류에 속한다. 예) 배낭 채우기 문제, 외판원 문제, m-색칠하기 문제
• 지금까지 대부분의 문제는 분류 1이거나 분류 3에 속한다.

 

P와 NP의 관계 : 𝑃⊆𝑁𝑃

• P문제를 위한 NP 알고리즘은 해를 추측하는 단계를 생략하고, 해를 확인하는 단계 대신에 해를 직접 다항식 시간에 구하고 확인 결과를 '맞다'라 응답하기 때문에 위의 관계가 성립

 

NP-Complete (NP-완전) 문제 집합

• 다루기 어려운 문제에서 가장 중요한 문제 집합
• NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분 집합
• Stephen Cook 처음 발견
  • NP에 있는 하나의 문제를 찾아서 그 문제가 모든 NP 문제보다 어렵다는 것을 증명
  • SAT (충족가능성문제) : 주어진 부울논리식을 모두 만족(참으로)시키는 각 부울 변수의 값을 찾는 문제
  • 현재, NP-완전 문제를 다항시간안에 푸는 알고리즘은 발견되지 않았고, 또한 그러한 알고리즘이 존재할 것인지도 알려지지 않았다. 대신, 특정한 NP-완전 문제에 대한 근사 알고리즘이 알려져있다.
• 지금까지 기술로는 다항식 시간에 풀기 어렵다고 판단되면서 서로 밀접한 논리 관계를 가진 문제 집합
  • 이 집합에 속하는 문제는 다항식 시간 안에 해결가능함을 보인 것이 없음
  • 우리가 일상생활에서 많이 접하는 문제들
    • 지수시간 시간복잡도를 가진 알고리즘으로 해결되는 문제 집합
    • 예) 외판원 문제 뿐만 아니라 0-1 배낭 채우기 문제, m-색칠하기 문제
• 어떤 문제가 NP-완전임을 아는 것은 이 문제가 아무도 풀지 못한 어려운 문제의 집단에 속한다는 것을 증명하는 것임
• 그러면 이 NP-완전 문제가 어려운 문제를 판별하는 기준으로 사용가능!
  • 어떤 문제가 어렵다 -> 그 문제는 P가 아님!
  • P != NP가 사실이라면 (추정), 그 문제가 적어도 완전 문제만큼 어렵기만 하면 그 문제는 P 바깥문제임
  • 따라서, 어떤 문제가 주어졌을 때, 다항식 알고리즘을 찾지 못하고 있다면, NP완전인지 아닌지, 알려진 NP 완전 문제를 그 문제로 환원/변환하여 풀 수 (바꾸어 풀 수) 있는지를 확인한다.
  • 그렇다면, 적어도 주어진 그 문제는 NP-완전 문제만큼 어려운 문제이다.
  • 그러면, 그 문제는 P !=NP 가 사실 이라면, P 바깥의 문제임이 확실하다.
  • 하지만, P!=NP인지 아직 확인 못함..

 

 

💡NP-완전 문제집합들 사이의 논리 관계 : 거대한 군을 이룸

• 어느 하나의 NP-완전 문제가 현실적인 시간(다항식시간 내)에 풀리면 모든 다른 NP-완전 문제도 다항식 시간에 해를 구할 수 있는 논리적 연결관계를 갖음.
• 따라서, NP-완전 문제 중 하나라도 P에 속한다는 것을 증명한다면, 모든 NP 문제가 P에 속하기 때문에, P-NP 문제가 P=NP 형태로 풀리게 된다.
• 반대로 NP-완전 문제 중의 하나가 P에 속하지 않는다는 것이 증명된다면 P=NP에 대한 반례가 되어 P-NP문제는 P!=NP 의 형태로 풀리게 된다.
• 지금, 어떤 문제가 NP-완전임이 확인된다면 이 문제를 현실시간에 풀수 있는 방법은 아직 없다.

 

 

 

2️⃣ NP-완전 문제의 특성

NP-완전 문제의 특성을 상세히 알기위해서는 먼저 어떤 문제를 다른 문제로 변환 또는 환원하는 과정을 이해하여야 한다.

• 서로 다른 두 문제의 "난이도"를 비교하는 데 사용
• 예)
  1. 문제 A : 주어진 n개의 숫자의 중간값을 비교하는 문제
  2. 문제 B : 주어진 n개의 숫자를 크기 순서로 정렬하는 문제
• 어떤 사람이 문제 B를 쉽게 풀 수 있다면, 그 사람은 문제 A도 쉽게 풀 수 있다. 왜냐하면 주어진 숫자들을 정렬하고 나면, 그 중 정 가운데에 있는 수를 뽑기만 하면 그것이 중간값이 될 것이기 때문이다.
• 이와 같은 일이 벌어진다면, 문제 A를 문제 B로 환원시킬 수 있다고 표현하며, 문제 A의 난이도는 문제 B의 난이도보다 어려울 수 없다는 것을 알 수 있다.

 

💡 문제의 환원/변환이란?

• 문제 A를 해결하기 위해서 문제 B를 해결하는 알고리즘을 이용하는 것!
• 어떤 문제를 다른 문제로 변형하는 과정

1. 문제 A의 입력을 문제 B의 입력 형태 (format)로 변환
2. 변환된 입력으로 문제 B를 해결하는 알고리즘을 수행
3. 수행 결과인 해를 문제 A의 해로 변환

문제를 변환하는 전 과정의 시간복잡도는 다음 3단계의 시간복잡도의 합

1. 문제 A의 입력을 문제 B의 입력으로 변환하는 시간 : 단순한 입출력 변환이므로 다항식 시간에 수행
2. 문제 B를 위한 알고리즘이 수행되는 시간
3. 문제 B의 해를 문제 A의 해로 변환하는 시간 : 단순한 입출력 변환이므로 다항식 시간에 수행

• 따라서, 문제 환원/ 변환의 시간 복잡도는 두번째 단계인 '문제 B를 해결하는 복잡도'에 의존한다.

• 문제 A와 문제 B 사이에 위와 같은 관계가 성립하면, 문제 A가 문제 B로 다항식 시간에 환원/변환 가능하다고 한다.
• 만일, 문제 B가 문제 C로 다항식시간에 변환가능 => 결국 문제 A가 문제 C로 다항식 시간에 변환 가능하다.
• 이러한 추이관계로 NP-완전 문제들이 서로 얽혀 있어서, NP-완전 문제들 중에서 어느 한 문제만 다항식 시간에 해결되면, 모든 다른 NP-완전 문제들이 다항식 시간에 해결된다.

 

❗️또 다른 문제 집합인 NP-하드(hard) 문제 집합❗️

• 어느 문제 A에 대해서, 만일 모든 NP 문제가 문제 A로 다항식 시간 안에 환원/변환이 가능하다면, 문제 A는 NP-하드문제이다.
• 하드란, 적어도 어떤 NP 문제보다 해결하기 어렵다는 뜻
• 모든 NP 문제가 NP-하드 문제로 다항식 시간에 변환가능하여야 함에도 불구하고, NP-하드 문제는 반드시 NP문제일 필요는 없다.
• 알려진 임의의 NP-하드문제 A로부터 어떤 문제 B로 다항식 시간에 변환 가능하면, 문제 B도 NP-하드이다.
• EX) 세일즈 맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법이외에는 정확한 답을 구할 수 있는 뾰족한 수가 (즉, 적당한 알고리즘이 존재하지 않는) 없는 문제들

  

NP 완비성 증명

1. 알려진 하나의 NP-완전 문제가 해당 문제로 다항식 변환됨을 보인다.

   

2. 해당 문제를 푸는 비결정론적 튜링기계가 존재함을 보인다.

 

 

 

3️⃣ NP-완전문제의 소개

1. SAT - 충족가능성 문제
2. 부분 집합의 합 : 주어진 정수의 집합 S의 원소의 합이 K가 되는 S의 부분 집합을 찾는 문제
3. 분할 : 주어진 정수의 집합 S를 분할하여 원소의 합이 같은 2개의 부분 집합을 찾는 문제
4. 0-1 배낭
5. 정점 커버 : 최소 크기의 정점 커버를 찾는 문제
6. 독립집합 : 서로 선분으로 연결 안된 최대 크기의 독립 집합을 찾는 문제
7. 클리크 : 독립집합의 반대 (최대크기의 클리크 찾기)
8. 그래프 색칠하기 : 가장 적은 수의 색을 사용하여 그래프를 색칠 (인접한 정점은 같은 색 X)
   • 각 정점의 차수를 가지고 가장 높은 차수를 가진 정점에 색을 칠하고 그 정점과 맞닿지 않은 부분을 같은 색으로 칠함
9. 집합 커버 : 가장 적은 수의 부분 집합으로 이루어진 집합 커버를 찾는 문제
10. 최장 경로 : 가장 긴 경로를 찾는 문제 (반복되는 점 X)
11. 여행자 문제 : 모든점을 1번씩만 방문하고, 다시 시작점으로 돌아오는 경로 중 최단 경로
12. 헤밀토니안 사이클 : 모든점을 1번씩만 방문하고 다시 시작점으로 돌아오는 경로 찾는 문제
    • 여행자 문제의 해가 헤밀토니안 사이클의 해가 될 수 있다. (선분의 가중치가 동일)
13. 통 채우기 : 가장 적은 수의 통을 사용하여 모든 물건을 통에 채우는 문제

나중에, 근사 알고리즘으로 NP완전문제를 해결하는 것을 배울 것임

 

 

 

4️⃣ NP 이론의 유용성

어떤 문제가 NP-Complete/Hard임이 확인되면, 

• 쉬운 알고리즘을 찾으려는 헛된 노력 중지!
• 주어진 시간 예산 내에서 최대한 좋은 해를 찾는 알고리즘(휴리스틱) 개발에 집중한다.
• 그리디 방식, 제네틱 알고리즘 등..

 

5️⃣ 요약

• NP-완전 문제의 특성 : 어느 하나의 NP-완전 문제에 대해서 다항식 시간의 알고리즘을 찾아내면, 모든 다른 NP-완전 문제도 다항식 시간에 해를 구할 수 있는 것
• 다항식 시간 복잡도를 가진 알고리즘으로 해결되는 문제의 집합을 P(Polynomial) 문제집합이라고 한다.
• 어느문제 A에 대해서, 만일 모든 NP 문제가 문제 A로 다항식 시간에 변환이 가능하다면, 문제 A는 NP-하드 문제 이다
• 문제 A가 NP-완전 문제가 되려면, 문제 A는 NP 문제이고 동시에 NP-하드 문제여야 한다.

 

 

---

Reference

• 알기쉬운 알고리즘 도서
• 서울과학기술대학교 컴퓨터공학과 알고리즘 수업