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

NP-완전 이론 : 문제를 현실적인 시간에 풀 수 있는가에 관한 이론

 

복잡한 문제가 주어졌을 때, 고민할 것

• 답이 존재?
• 어떻게 답을 찾는가?
• 찾은 것이 올바른지 어떻게 검증?

 

• 쉬운문제 / 답은 구하는데 시간이 짧은 문제
• 어려운 문제 / 답을 구하는데 시간이 오래 걸리는 문제
• 풀 수 없는 문제 / 너무 어려워서 풀리지 않는 문제
• 아리송한 문제 / 어떤 집단 문제들은 어려워 보이기는 하지만, 그 답을 보면 옳다는 것을 검증하기가 쉬운 그러한 집단 문제
  • 예) 퍼즐 맞추기 : 모나리자를 500조각 낸 퍼즐을 구입하여 짝을 맞추는 문제 : 문제를 푸는 것은 어렵지만, 답을 보고는 그것이 옳다는 것을 판정하는데 500 조각만 조사하면 됨으로 검증하기 쉽다.

---

이번 포스팅에서 다룰 것.

1. 문제의 난이도 "다루기 힘든 정도 (Intractability)" 를 이해하기
2. P와 NP 문제 구별하기
   • P(Polynomial) 문제 : 다항식 시간 알고리즘을 가진 문제
   • NP(Non-deterministic Polynomial time) 문제 : 비결정적 다항식 시간 알고리즘을 가진 문제
   • NP-Complete 문제 : NP 문제들 중에서 NP-hard 인 문제
   • NP-hard 문제 : 모든 NP 문제를 다항식 시간 안에 문제 A로 변환(환원)이 가능할때, 그 문제 A
3. 결정 (Yes/No) 문제와 최적화 문제의 차이를 이해하기
4. NP-완전(NP-Complete, NP-완비) 문제를 이해하기
   • NP-완전 증명 방법을 이해하기
   • NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제의 부분집합
   • NP-완전이라는 사실이 판명됨으로써 얻을 수 있는 이득을 이해하기

 

---

문제의 종류

해결 가능성 (다루기 힘든 정도 = Intractability)에 따른 분류

다루기 힘든 문제의 정의 : 다항식으로 시간복잡도가 표시되는 알고리즘을 찾을 수 없는 문제

 

 

 

 

 

현실적인 시간 vs 비현실적인 시간

1️⃣ 현실적인 시간

• 현실에서 사용할만한(쓸만한)알고리즘. 현실에서 사용되기에 적절한 비용을 가진 알고리즘
• 다항식 시간 (polynomial time)을 의미
  • 입력의 크기 n의 다항식으로 표시되는 시간
  • 어떠한 문제를 계산하는 데에 걸리는 시간이 문제의 크기 n의 다항식 함수보다 크지 않은 것을 의미
  • 입력 길이의 다항 시간이 걸리는 경우를 '빠른' 혹은 '다루기 쉬운(tractable) 경우'라고 표현함
  • 복잡도 함수 m(n) = O(n^k), k: 상수
• 실제 현실적인 비용 : O(n), O(n^2), O(n^3)
• 그 이상의 차수를 갖는 다항식 O(n^4),... 은 다항이라도 실제 사용하기에는 너무 비효율적
• 그러나, 비용/복잡도가 큰 다항 문제들도 계속 연구되면서 그 비용이 줄어듦 ( 개선될 가능성! )
  • 예) O(n^100) -> O(n^4) -> O(n^2.5)
• 일단 다항 알고리즘을 가지게 된 문제는, 필요하다면 더 빠른 (다항 차수가 적은) 알고리즘이 늘 꾸준히 찾아져 왔다.

 

2️⃣ 비현실적인 시간

• 다항 시간보다 오래 걸리는 경우를 초다항 시간으로 부르며, 이 경우는 '다루기 힘든(intractable) 경우'로 표현한다.
• 지수 시간 (예: 2^n)
• 계승 시간 (예: n!)

 

 

 

 

결정 문제 vs 결정 불가능한 문제

1️⃣ 결정 문제 (decision problem, 판정 문제)

• 어떤 형식 체계에서 '예' 또는 '아니오' 대답으로 이루어지는 문제
• 예 : 그래프 G에서 길이가 k 이하인 해밀토니안 경로가 존재하는가? 
  • 어떤 연결된 그래프에서 모든 꼭짓점을 한 번 씩만 지나는 경로가 존재하는가?
• 예 : 두 숫자 x와 y가 있을 때 y는 x로 나누어 떨어지는가?
  • x와 y의 값에 달라짐
• 어떤 판정 문제를 푸는 알고리즘이 있으면, 그 문제는 결정 가능하다고 하고, 없으면 결정 불가능하다고 함
• 결정 불가능한 문제 : undecidable probelm
• 두 문제는 동적의 앞뒷면과도 같다.

2️⃣ 결정 불가능한 문제

• 다루기 힘들다고 증명된 문제
• 정지/종료 문제 (Halting Problem) : 어떤 프로그램 P가 정상적으로 수행되어서 종료하는지를 결정하는 문제
  • 어떤 프로그램 P에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라.

정리 : 정지/종료 문제는 결정 불가능하다!
- 1936년 Alan Turing에 의해서 모든 가능한 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명함
- 그러므로 '정지문제는 튜링 기계에서 판정할 수 없다'고 함
정지 문제는 처음으로 증명된 판정불가능한 문제라는 점에서 역사적으로 중요한 의미

3️⃣ 결정 불가능한 문제 : 정지/종료문제 (Halting Problem)

• 정리 : 정지/종료 문제는 결정 불가능하다.
• 증명 : (귀류법) 정지 문제는 풀 수 있는 알고리즘 Halt가 존재한다고 가정하자.
  • Halt 알고리즘은 어떤 프로그램을 입력으로 받아서 그 프로그램이 종료하면 '예'라는 답을 주고, 종료하지 않으면 '아니오'라는 답을 반환할 것이다.

    nonsense() {
    	if(Halt(nonsense())) 
        		while(true) 
            		do something;
    }

    1. nonsense 알고리즘이 정상적으로 종료하는 알고리즘이라고 한다면, Halt(nonsense())는 true가 되므로, 절대로 nonsense 알고리즘은 종료되지 않는다 -> 모순!
    2. nonsense 알고리즘이 정상적으로 종료하지 않는 알고리즘이라고 한다면, Halt(nonsense())는 false가 되므로, nonsense 알고리즘은 종료한다 -> 모순!
    3. 두 경우 모두 가정에 위배되므로 모순이다. 따라서 Halt 알고리즘은 존재할 수 없다.

 

 

 

 

 

최적화 문제 vs 결정 문제

• 최적화 문제 : 최적의 해를 찾는 문제 (예 : 최솟값이나 최댓값을 구하는 형태의 문제)
• 결정 문제 (판정문제) : 어떤 기준을 주어주고 기준을 만족하면 '예', '아니오'로 이루어지는 문제
• 최적화 문제에 대한 다항시간 알고리즘이 있다면, 그 알고리즘으로부터 그 문제에 해당하는 결정문제에 대한 다항시간 알고리즘도 쉽게 유추/만들 수 있음 

  

  

  

• 최적화문제와 결정문제의 상관관계
  • 결정 문제가 상당히 제한적인 것으로 생각될 지 모르나, 최적화문제와 밀접한 관계를 가짐
  • 임의의 최적화 문제에 대한 다항시간 알고리즘이 있으면 그에 상응하는 결정 문제에 대한 다항시간 알고리즘도 쉽게 찾을 수 있다.
    • ex) 외판원 최적화문제를 해결하는 다항시간 알고리즘을 통해 얻은 일주경로의 길이가 120이면, 외판원 결정 문제에서 d가 120보다 큰 값이라면 주어진 외판원 결정문제의 답은 'no'이고, 120보다 작거나 같은 값이라면 주어진 외판원 결정 문제의 답은 'yes'가 된다.
  • 또, 결정/판정 문제에 대한 해를 구하는 알고리즘이 있다면, 추측된 해 값 d를 여러번 바꾸어 가면서 판정 문제를 여러번 수행하여 최적화 문제의 해도 구할 수 있다.

 

 

 

 

 

 

Deterministic algo. vs Non-Deterministic algo.

1️⃣ Deterministic algorithm (결정론적 알고리즘)

• 예측한 그대로 동작하는 알고리즘
• 같은 입력이 들어오면 언제나 똑같은 과정을 거쳐서 언제나 똑같은 결과를 출력, 즉, 알고리즘의 각 단계마다 정확한 결정을 내린다.
• 예) 수학함수 : 함수에 특정한 입력이 들어오면 언제나 동일한 결과를 거쳐서 동일한 결과값이 나옴
• f(x) = x+1, f(1) = 2, f(k) = k+1
• 결정론적인 성질을 가지는 추상기계의 예 : 결정론적 튜링기계
  • 기계가 결정론적이면, 초기 상태 이후로 현재 상태가 앞으로 어떤 상태가 될지 결정하며 어떤 상태를 거쳐서 동작할지 미리 결정
• 결정론적 알고리즘의 문제점
  • 어떤 문제는 결정론적 알고리즘을 찾기 어렵다.
  • 예) 어떤 수가 소수인지 아닌지를 판별하는 확률적 알고리즘 (페르마 소수 판별법)
    • 1970년대에 발견
    • 확률론적 알고리즘은 아주 작은 확률로 틀릴 가능성이 있기는 하지만, 효율적인 알고리즘
    • 그 이후로 30년 동안 연구한 끝에 소수인지 판별하는 결정론적 알고리즘을 찾아냈으나, 실행시간은 비교할 수도 없이 오래 걸린다.
  • 예) 실생활에서 중요한 의미를 가지는 많은 문제들 : NP-완전
    • 이 문제들은 비결정론적 튜닝 기계라는 엄청난 능력을 가진 가상의 병렬 기계를 이용하면 쉽게 풀 수 있으나, 아직까지 이런 기계를 실제로 구현하지 못하고 있다.
    • 기껏해야 NP-완전 문제의 근사해(approximate solution)을 구하거나 특별한 경우의 해를 구하는 정도이다.

 

2️⃣ Non-deterministic (비결정론적 알고리즘)

• 같은 입력이 주어지더라도 실행될 때마다 다른 행동을 취한다. 추측을 통해 문제를 해결한다고 볼 수 있다.
• 예측불가, 출력 다양!
• 내, 외부 환경등이 변수로서 알고리즘 동작에 영향을 줌
• 비결정론적 알고리즘 만들기 : 외부입환경, 시간, 하드웨어내 정보등을 알고리즘 변수로 사용

 

 

---

Reference

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