For a better world

P, NP, NP Complete, NP Hard 정의

$P$ : 어떤 문제가 주어졌을 때 다항식으로 표현되어 polynomical time 즉, 다항 시간내에 해결 가능한 알고리즘을 의미하며 알고리즘의 복잡도가 $O(n^k)$로 표현되는 문제를 '$P$'라 한다.

(복잡도 $O(n^k)$ 이하를 가지는 경우 같은 복잡도 내에 모든 해를 구한다.)

$NP$ : 어떤 문제가 주어졌을 때 다항식으로 표현될 수 있는지의 여부가 결정되지 않은 문제들을 'NP(Non-deterministic polynomial)'라 한다.

$NP-Complete$ : NP이면서 동시에 NP-Hard 에 속한다면 그 문제는 'NP-Complete'라 한다. (전수조사가 답)

$NP-Hard$ : 적어도 모든 NP 문제만큼은 어려운 문제들의 집합이며, 만약 P-NP 문제가 P=NP로 풀린다면 P=NP=NP-Complete이므로 P와 NP는 NP-Hard의 부분집합이 되고, P≠NP인 경우는 P와 NP-Hard는 서로소가 된다.

*다항시간 : $T(n) = O(n^k), k$ 는 상수  => $k$가 상수로 고정이 된다면 그 문제는 해결하기 쉬운 문제. 다항시간안에 풀 수 있는 문제이므로.

$P = NP$ 또는 $P \neq NP$ 증명의 의의

$P = NP$ 또는 $P \neq NP$를 증명한다는 것은 100만 달러의 상금과 튜링상 수상 그 이상의 의미를 가진다. 만약 $P = NP$라 증명되면 현재 NP라고 일컬어지는 길찾기, 방문 판매 알고리즘 등을 포함한 모든 문제들이 전부 P 문제로서 풀릴 수 있다는 의미이다. 즉, 방문 판매와 알고리즘과 같이 무조건 시간이 오래 걸리는 방법으로 풀 수 밖에 없다 생각 되는 것 또한 방법만 찾는다면 다항 시간내에 해결할 수 있다는 것이다. 반대로 $P \neq NP$가 증명 되면, 수 많은 NP 문제들이 P 문제로 환원될 수 없음이 증명되었으니 더 쉬운 방법(P 문제로 환원할 방법)을 찾으려 더 이상 애쓸 필요가 없다는 것이다.

즉, 만약 우리가 이에 대한 해답을 알게된다면 지수시간(Exponential time)에 해결 가능한 모든 NP문제를 다항시간(Polynomical time)에 해결 가능한 P로 해결할 수 있기 때문에 아주 중요한 위치를 가지고 있다고 말한다.(예를 들면 암호화 알고리즘을 푸는데에 지수 시간이 걸린다. 소수를 구하는 알고리즘 또한 마찬가지이다).

복잡성 이론

'복잡성 이론 (Complexity Theory)' 이라는 컴퓨터 공학의 한 분야는 엄청난 계산을 필요로 하는 복잡한 문제들을 다룬다. 이것은 말 그대로 컴퓨터가 계산하는 여러 가지 문제들에 대한 '복잡성' 자체를 연구하는 분야다. 이 분야의 연구는 구체적인 알고리즘을 개발하는 것과 직접적인 상관은 없지만 어떤 문제가 쉽게 풀릴 수 잇는 문제고 어떤 문제가 쉽게 풀릴 수 없는 문제인지를 구별하도록 해주기 때문에 프로그래머들이 해결할 가능성이 없는 문제를 붙들고 시간을 허비하는 우를 범하지 않도록 해준다.

지수의 값이 아무리 크다고 해도 그것이 미리 정해진 상수 값이라면 그 알고리즘은 컴퓨터가 적당한 시간 안에 계산해 낼 수 있는 쉬운 알고리즘에 해당하는 것이다. 이렇게 변수위에 붙은 지수가 미리 정해진 상수인 수학 공식을 우리는 다항식 (polynomial) 이라고 부른다. 다음은 다항식의 예다.

$2n^3 \times n^2 -3$

복잡성 이론에서 다항식의 반대말은 '지수 함수 (exponential function)'다. 지수함수란 변수 위에 붙은 지수가 미리 정해져 있는 상수 값이 아니라 그 자신도 변수로 표현되는 함수를 의미한다. 다음은 지수함수의 예다

$2^n$ 혹은 $2n^n-1 + 2^n$

세일즈맨의 여행 문제를 풀기 위해 사용되는 factorial은 다음과 같은 수학 공식으로 표현되므로 다항식이라기보다는 지수함수에 속한다.

$n\times (n-1) \times (n-2)\times ... \times2 \times 1$

이 식을 모두 풀어쓰면 가장 차원이 높은 지수를 갖는 항은 맨 앞에 존재하는 n 으로 n-1 이라는 지수를 갖는다는 사실을 알 수 있다. n 의 크기가 증가하면 팩토리얼 함수 전체의 값이 엄청난 속도로 커진다. 지수함수의 특징은 바로 n 이 조금만 커지면 함수 전체의 값이 기하 급수적으로 커진다는 사실이다. 현재의 전자식 컴퓨터가 계산을 수행할수 있는 속도에는 엄연히 한계가 존재하기 때문에 계산을 수행해야 하는 양이 지나치게 커지면 컴퓨터도 계산을 수행할수 없게 된다. 이렇게 지수함수들은 n 값이 커짐에 따라서 함수의 결과가 엄청나게 빠른 속도로 증가하여 컴퓨터조차 쉽게 계산을 할 수 없기 때문에 '어려운' 문제라고 말한다. 즉 알고리즘의 속도가 다항식이 아니라 지수함수로 표현되면 그것은 어려운 알고리즘인 것이다.

복잡성 이론에서는 알고리즘의 속도가 다항식으로 표현되는 문제들을 묶어서 'P' 라고 부르고, 다항식으로 표현될 수 있는지 여부가 알려지지 않은 문제들을 묶어서 'NP' 라고 부른다. 여기서 P 는 Polynomial (다항식) 의 머리 글자고, NP 는 nondeterministic polynomial (비결정성 다항식) 의 머리 글자를 의미한다. 이때 NP 가 non-polynomial (비다항식) 을 의미하지 않는다는 사실에 유의할 필요가 있다. 다항식이 아니라는 사실과 다항식으로 표현되는지 여부가 아직 알려지지 않았다는 사실 사이에는 엄청난 차이가 존재하기 때문이다. 다항식으로 표현되는 알고리즘은 오늘날의 컴퓨터가 적당한 시간내에 해결할 수 있는 문제기 때문에 P 에 속한 문제들은 '쉬운' 문제들이고, NP 는 그와 반대로 '어려운' 문제를 의미한다.

복잡성 문제를 연구하는 학자들에게 가장 어려운 질문중의 하나는 바로 "NP 에 속하는 문제들이 궁극적으로는 모두 다항식, 즉 쉬운 알고리즘을 이용해서 해결될 수 있을까?" 라는 질문이다. 만약 그렇다면 NP 에 속한 문제나 P 에 속한 문제가 모두 종국에는 다항식으로 표현되기 때문에 'P = NP' 라는 등식이 성립하게 될 것이다. 하지만 NP 에 속하는 문제가 모두 다항식으로 해결될 수 있을지 여부를 파악하거나 증명하는 것이 너무나 어렵기 때문에 이 등식은 아직도 완전하게 입증되지 않은 어려운 명제증의 하나로 통하고 있다.

한편 'NP-hard' 라고 불리는 문제들은 세일즈맨의 여행 문제처럼 모든 경우의 수를 전부 확인해보는 방법 이외에는 정확한 답을 구할 수 있는 뾰족한 수가 없는 문제들을 뜻한다. 어떤 문제가 NP 에 속하면서, 즉 다항식으로 표현될 수 있는지 여부가 알려지지 않았으면서 동시에 NP-hard 에 속한다면, 즉 '무식한 힘' 의 방법말고 다른 절묘한 알고리즘이 알려져 있지 않다면 그 문제는 'NP 완전 문제 (NP complete)' 라고 부른다. 휴, 정말 복잡하다.

컴퓨터 학자들과 프로그래머들은 대개 NP 완전 문제를 실용적인 관점에서 해결하기 위해서 진짜 정답을 찾기를 포기하는 대신 휠씬 적은 양의 계산을 통해서 정답에 가까운 값을 찾는데 만족한다. 이러한 알고리즘은 근사 알고리즘 (Approximation algorithm) 혹은 발견적 알고리즘 (Heuristic algorithm) 이라고 부른다. 앞서 말한 MST, 탐욕 알고리즘 (Greedy algorithm), 평면절단 방법등은 모두 이러한 알고리즘의 예인데, 실전 프로그래밍의 세계에서는 이러한 근사 알고리즘이 생각보다 많이 사용된다.

해밀턴 경로

해밀턴 경로(Hamiltonian Path)의 경우 NP-Complete에 속하는 문제로서 어떤 그래프가 주어졌을 때 모든 꼭짓점을 단 한번만 지나는 경로가 존재하는지에 대한 여부를 묻는다.

Reference

[1] http://www.aistudy.co.kr/computer/complexity_lim.htm

[2] https://wkdtjsgur100.github.io/P-NP/

[3] https://proneer.tistory.com/entry/복잡성이론-P-NP-NP-완전

[4] https://inverse90.tistory.com/entry/PNP-NP-Hard-NP-Complete

최소 비용 신장 트리의 특징

• 그래프의 모든 정점이 간선에 의해 하나로 연결되어 있다.
• 그래프 내에서 사이클을 형성하지 않는다.

최소 비용 신장 트리의 구성에 사용되는 대표적인 알고리즘

• 크루스칼(Kruskal) 알고리즘

가중치를 기준으로 간선을 정렬한 후에 MST가 될 때까지 간선을 하나씩 선택 또는 삭제해 나가는 방식

• 프림(Prim) 알고리즘

하나의 정점을 시작으로 MST가 될 때까지 트리를 확장해 나가는 방식

크루스칼 알고리즘의 핵심

오름차순

1. 가중치를 기준으로 간선을 오름차순 정렬
2. 낮은 가중치의 간선부터 시작해서 하나씩 그래프에 추가
3. 사이클을 형성하는 간선을 추가하지 않음
4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성

내림차순

1. 가중치를 기준으로 간선을 내림차순으로 정렬
2. 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거
3. 두 정점을 연결하는 다른 경로가 없을 경우 해당 간선은 제거하지 않음
4. 간선의 수가 정점의 수보다 하나 적을 때 MST가 완성

크루스칼과 프림 알고리즘 특징

크루스칼 알고리즘의 특징

• 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 $O(E\times logV)$의 시간 복잡도를 가진다.

프림 알고리즘의 특징

• 변의 개수를 E, 꼭짓점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때의 기준으로 $O(E\times logV)$의 시간 복잡도를 가진다.
• 그래프가 충분히 빽빽한 경우 $E=\Omega(V\times logV)$에는 피보나치 힙을 이용하여 훨씬 빠르게 할 수 있다.
• 이 방법은 복잡도가 $O(E + V\times logV)$까지 떨어진다.

Reference

[1] https://ko.wikipedia.org/wiki/크러스컬_알고리즘

[2] https://ko.wikipedia.org/wiki/프림_알고리즘

시간 복잡도

시간 복잡도란 알고리즘의 효율성을 판단하기 위한 지표로서, 알고리즘의 절대시간이 아닌,  알고리즘을 수행하는데 사용되는 연산들이 몇 번 이루어지는가에 대한 것을 수로 표기한 것이다. 연산에는 산술, 대입, 비교, 이동이 있다. 시간 복잡도, 즉 성능 측정에 사용되는 표기법은 크게 세 가지로 나뉘며 Big-O, Big-Omega($\Omega$), Theta($\theta$)가 있다.

• Big-O

모든 $n$, $n \gt n_0$에 대해 $f(n) \le c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=O(g(n))$이다.

예를 들면 $O(n)$: 최악의 경우 $n$번까지 수행되면 프로그램을 끝낼 수 있다.

• Big-Omega

모든 $n$, $n \gt n_0$에 대해 $f(n) \gt c\times g(n)$인 조건을 만족시키는 두 양의 상수 $c$와 $n_0$가 존재하기만 하면 $f(n)=\Omega(g(n))$이다.

예를 들면 $O(n)$: 최소 $n$번은 수행되어야 프로그램을 끝낼 수 있다.

• Theta

모든 $n$, $n \gt n_0$에 대해 $c_1\times g(n) \le f(n) \le c_2\times g(n)$인 조건을 만족시키는 세 양의 상수 $c_1, c_2, n_0$가 존재하기만 하면 $f(n)=\theta(g(n))$이다.

$\Omega와\ O$의 교집합, 즉 차수가 같은 문제이다.

추가적으로 Small-O, Small-omega($\omega$) 표기법도 존재한다.

Small-O는 Big-O에서 등호를 뺀다.

예를 들면 $O(n)$: 최악의 경우에도 n번 미만으로 수행되면 프로그램은 끝낼 수 있다.

Small-O와 Big-O의 차이점은 다음과 같다.

- Big-O는 실수 $c>0$ 중에서 하나만 성립해도 된다.

- Small-O는 모든 실수 $c>0$에 대해서 성립해야 한다.

Big-O 표기법 성능 비교

Better $O(1)$ < $O(log\ n)$ < $O(n)$ < $O(n\times log\ n)$ < $O(n^2)$ < $O(2^n)$ < $O(n!)$ Worse

상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수

Big-O 표기법 예제

• $O(1)$: Operation push and pop on Stack
• $O(log\ n)$: Binary Tree
• $O(n)$: for loop
• $O(n\times log\ n)$: Quick Sort, Merge Sort, Heap Sort
• $O(n^2)$: Double for loop, Insert Sort, Bubble Sort, Selection Sort
• $O(2^n)$: Fibonacci Sequence

시간 복잡도 분석 종류

$T(n)$: Every-case anlaysis

• 입력크기(input size)에만 종속
• 입력값과는 무관하게 결과값은 항상 일정

$W(n)$: Worst-case analysis

• 입력크기와 입력값 모두에 종속
• 단위연산이 수행되는 횟수가 최대인 경우 선택

$A(n)$: Average-case analysis

• 입력크기와 입력값 모두에 종속
• 모든 입력에 대해 단위연산이 수행되는 기대치(평균)
• 각 입력에 대해서 확률 할당 가능

$B(n)$: Best-case analysis

• 입력크기와 입력값 모두에 종속
• 단위연산이 수행되는 횟수가 최소인 경우 선택

표기법 간의 관계

Big-O 계산 실습

a=10 # Constant 1
b=20 # Constant 1
c=30 # Constant 1

for i in range(n):
 for j in range(n):
    x = i * i # n^2
    y = j * j # n^2
    z = i * j # n^2

for k in range(n):
    w = a * k + 40 # n
    v = b * b # n

$T(n) =  3n^2 + 2n + 3$

$T(n) = On^2$

정렬 알고리즘 비교

Reference

[1] https://arer.tistory.com/99

[2] https://noahlogs.tistory.com/27

[3] https://sehoi.github.io/2014-03-03/time-complexity/

[4] https://ratsgo.github.io/data%20structure&algorithm/2017/09/13/asymptotic/

[5] https://blog.chulgil.me/algorithm/

[6] https://wayhome25.github.io/cs/2017/04/20/cs-26-bigO/