PS하는 사람이면 NP-complete가 뭔지는 알아야 한다고 생각한다

얼마전에 공대생이 NP-complete에 대한 내용을 습득하는 것이 실질적으로 의미가 있는짓이냐는 글을 본 적이 있다

하지만 나는 띠오리하는사람이므로 무시하기로 했다


계산복잡도이론에서 다뤄지는 문제들은 당연히 컴퓨터로 읽고 풀 수 있는 문제들에 한한다

수학적으로 보다 엄밀하게는 {0,1}로 이루어진 유한수열들의 집합에서 {0,1}로 이루어진 유한수열둘의 집합으로 가는 함수가 메인 대상이다

이중에서 공역이 {0,1}인 함수, 쉽게말하면 true, false만 리턴하는 문제를 결정문제(decision problem)이라고 한다


결정문제중 다항시간에 풀리는 문제들의 집합을 우리가 P라고 부른다

쉽게말하면 입력의 크기가 n이면 어떤 다항식 p(x)가 있어서 시간복잡도가 O(p(n))인 알고리즘이 존재할 때 그 문제가 P에 속한다고 한다

여기서 입력의 크기라는건 입력의 비트수를 말한다

어떤 숫자 N을 입력받아서 그 수가 소수인지 아닌지 판별하는 문제를 생각해 보면 1~N까지 다 나눠보면 되니까 당연히 P라고 생각할 수 있는데 숫자 N을 등신처럼 1을 N개입력하는식으로 입력하지 않는 이상 O(log N)개의 비트만을 쓸테니 1~N까지 다 나눠보면 O(N)=O(e^(log N))번의 나눗셈이 필요해서 저 알고리즘은 다항시간 알고리즘이 아니다

물론 어떤 똑똑한사람이 멋진알고리즘을 찾아서 소수판별은 P긴 하다


그러면 NP는 뭐냐... 

비결정론적 튜링머신을 이용한 정의는 튜링머신 시작도 안했으니 생략하고

어떤 함수 f에 대해 다항식 p(x), P에속하는 함수 g가 있어서 만약

f(x)=1일것과 어떤 길이 p(|x|)짜리 문자열 y가 있어서 g(x, y)=1인 것이 동치일 때 f를 NP문제라고 한다(이런 y를 여기서 certificate라고 한다

이렇게 써놓으면 이해가 전혀 안될텐데 교양책에 있는 '답을 검증하는게 polynomial'이랑 같은 말이다

예를들어 아까 나온 소수판별같은 경우에 입력이 x면 y는 곱해서 x가 나오는 1보다 큰 두 수 라고 하면 

두수를 곱해서 x가 나오는지 판단하는건 당연히 다항시간에 되고

저런 y가 있는것과 x가 소수가 아닌건 동치이므로

주어진 수를 입력받아 소수가 '아니면' true를 반환하는 문제는 NP가 된다


비슷하게 주어진그래프의 헤밀톤사이클이 있는지 판별하는 문제는 y를 그런 사이클을 y로 잡으면 되므로 NP가 된다


y를 아무것도 없는 문자열로 잡고 f=g로 잡아버리면 되니까 모든 P문제는 NP문제이기도 하다

거꾸로가 된다는 것을 증명하면 10억을 받는다


NP문제의 complement를 co-NP라고 한다. 쉽게말해서 아까 주어진 수를 입력받아 소수가 '아니면' true를 반환하는 문제가 NP랬으니까 주어진수가 소수면 true를 반환하는 문제는 자동으로 co-NP가 된다

또는 다르게 쓰면 NP는 f(x)=1 iff g(x,y)=1 for some y of length p(|x|) 였으면

co-NP는 f(x)=1 iff g(x,y)=1 for 'every'y of length p(|x|) 이다

방금 소수문제로 예를 들면 y를 x보다 작은 두 수, g는 두 수를 곱해서 x가 '안되면' 1을 출력하는 함수로 만들면 된다

P는 당연히 co-NP이기도 하다


NP와 co-NP의 교집합이 P냐는 것도 중요한 추측이다. P=NP냐는거보다 조금 약해서 10억은 안주지만 이거라도 풀면 킹갓대학에 교수자리 하나 꿀꺽할 수 있다


그러면 NP-complete는 뭐냐

polynomial time reduction이라는걸 먼저 정의해야 하는데 쉽게말하자면 어떤 f를만약에 계산할수 있다고 치면 g도 f를 통해 쉽게 계산할 수 있다는 것 이다

수학적으로 엄밀하게는 다항시간에 계산가능한 함수 h가 있어서(h는 decision이 아닐 수 있음) f(h(x))=1 if and only if g(x)=1이면 우리가 f에서 g로가는 polynomial time reduction이 있다고 한다

NP-hard문제는 '모든' NP문제로 polynomial time reduction이 있는 문제를 말한다

그러니 NP-hard문제중에 하나만 polynomial time에 풀면 f도 polytime, h도 polytime이니까 모든 NP문제를 다항시간에 풀 수 있다는 것 이다. 즉 P=NP이다

그리고 NP-hard문제중에 NP이기도 한 것을 NP-complete라고 한다


정의만 보면 어떤 문제가 NP-complete라는 것을 보이는 것은 어려워보이는데 실제로는 그렇지 않다

Cook-Levin theorem이 SAT문제랑 3-SAT문제가 NP-complete임을 보였고

그 이후로 대부분의 NP-hard 증명은 누군가가 이미 NP-hard임을 보인 문제 중 하나로의 reduction만 보인다


NP-complete 문제들이 어떤게 있나 알아두는 것은 PS할 때 가끔 유용할 수 있는데 문제로 NP-complete문제가 나오면 알고있는 대부분의 좋은 알고리즘들이 안통한다는 사실을 쉽게 알 수 있기 때문이다

그리고 하나 더 PS할때 알아두면 좋은 사실이 있는데

같은 NP-complete 문제사이에도 차이가 있는 경우가 있다

예를들어서 coloring problem(그래프 G랑 숫자 k가 인풋, G가 k채색 가능한지 묻는 문제)의 경우 k가 3 이상이면 무조건 NP-complete다

하지만 vertex cover(그래프 G랑 숫자 k가 인풋, k개의 정점을 골라서 모든 엣지가 이중 적어도 하나랑 만나게 할 수 있는가?)문제는 k가 고정되면 polynomial time에 풀린다

그냥 가능한경우 다해보면 O(n^(k+2))정도면 된다

이 문제가 P가 아닌 이유는 k도 인풋으로 들어오기 때문이다

아주 대충 설명해서 parametrized algorithm이 여기서 모티베이션이 나온 것 이다

엄밀하게는 생략

만약 NP-complete문제가 나왔는데 숫자하나의 제한이 엄청 작다면 그 숫자의 각 값에 대해 polynomial time에 풀리는지를 생각해 보는 것도 좋은 방법이 될 수 있다



마지막으로 몇가지 클레스를 간단히 소개하자면

드릅게 많은 계산복잡도 class들이 있는데 NQP(양자컴퓨터로 다항시간에 풀리는 결정문제들의 집합)같은건 인생에 도움이 안될테니 PS할때 볼만한애들만 보면

BPP: randomized algorithm으로 다항시간에 2/3이상의 확률로 맞추는 결정문제들의 집합이다. 사실 반복하면 되니까 상수만 키우면 원하는 확률로 맞게 할 수 있다

RP, co-RP: BPP의 부분집합으로 각각 진짜정답히 false일때랑 true일때 100%의 확률로 맞추는 알고리즘이 있는 문제들의 집합이다

ZPP: RP랑 co-RP의 교집합이다. 다르게말하면 randomized로 항상 100%확률로 맞출 수 있는 문제들의 집합이다

PSPACE: 메모리를 polynomial로 먹는 집합이다. 사실 PS할때는 별로 메모리신경쓸일이 안많긴 한데 아무튼

NP와 BPP는 둘다 PSPACE안에 있고 '아마도' NP와 PSPACE는 다를것이라고 대부분 '믿고' 있으며 BPP는 P와 같거나 P보다 아주 쬐끔 클거라고 '믿고' 있다

믿는다는 말의 의미는 P=NP문제 처럼 아직 증명 안됐다는 소리다



논문쓰다가 안써져서 써봄