2007 학습용컨텐츠 Complexity Theory P vs NP http://talent.kaist.ac.kr http://gifted.kaist.ac.kr 여지우 jyeo@kaist.ac.kr 1
P vs NP 0. 서론 1. 알고리즘과복잡도 1.1. 알고리즘 1.2. 복잡도 2. P 와 NP 2.1. 결정형문제 2.2. 결정성 / 비결정성알고리즘 2.3. P 문제 2.4. NP 문제 3. P = NP? 3.1. P 와 NP 의상관관계 3.2. NP- 완전성 3.3. P : NP 문제의의의 2
0. 서론 2003 년 12 월국내한수학교수가 P : NP 문제 를해결했다고하여신문에크게난적이있다. 이것은지난 2000 년미국클레이수학재단이한문제에 100 만달러씩걸고발표한 7 가지난제중첫번째것으로, 현대컴퓨터과학의미해결문제중에서가장중요한것으로손꼽히고있다. 몇년을두고그에대한검증을한다고기사에나왔는데현재어떻게되었는지는모르겠다. 당시기사를읽고던진물음이 P : NP 문제가도대체무엇인가? 였다. 페르마의마지막정리, 골드바흐의추측, 사색문제등이일반인도쉽게이해할수있는난제인데반하여, P : NP 문제는그것이어떤문제인지이해하는데만해도알아야할배경지식이만만치않게많다. 이컨텐츠는 P : NP 문제가무엇인지를알기위해배워야하는개념들의정의와그에대한 설명이주된내용이다. 중간중간에는이해를돕기위한예제들이있다. 예제코드는주로파 이선문법에따라작성하였다. 덧붙여, 본문에서중요한키워드는 굵은글씨 로강조하거나영문용어를함께표기하였다. 더깊게공부하고싶은내용이있으면해당용어를인터넷으로검색하면다양한참고자료를 구할수있을것이다. 3
1. 알고리즘과복잡도 1.1. 알고리즘어떤수학적인문제 problem 를유한한단계안에해결하기위한방법혹은절차를알고리즘 algorithm 이라고한다. 문제 와 알고리즘 은확실히구분해야하는개념이다. 한문제에는그것을계산하기위한서로다른알고리즘이여럿있을수있다. 두자연수가주어졌을때둘의최대공약수를구하는문제를생각해보자. 이문제에대한알 고리즘으로다음의두가지를생각할수있다. 첫째는두수중의작은것으로부터시작해서 1 씩빼가면서주어진두수를나눈나머지 가각각 0 이될때까지, 즉둘의공약수가나올때까지반복하는것이다. 이렇게하면분명 히최대의공약수를찾을수있다. 둘째방법은유클리드호제법 Euclidean algorithm 을이용한것이다. 유클리드호제법은둘중의작은수로큰수를나누었을때나온나머지를이용한다. 이전단계의작은수를큰수로취하고, 나눗셈에서나온나머지를작은주로취하여나머지가 0 이될때까지이것을반복한다. 다음은두알고리즘을파이선문법으로구현한것이다. 첫번째방법 def gcd1(x,y): d = min(x,y) while(x%d!=0 or y%d!=0): d -= 1 return d 두번째방법 def gcd2(x,y): a, b = max(x,y), min(x,y) while(a%b!= 0): a, b = b, a%b return b 직접손으로해보면두번째방법이첫번째에비해훨씬쉽고시간도적게걸린다. 다시 말해, 유클리드호제법이하나씩나누어보는것보다더우수한알고리즘이라할수있다. 4
1.2. 복잡도여러알고리즘이있을때어떤것이더우수하냐를가리기위한기준이바로알고리즘의복잡도 complexity 이다. 알고리즘의복잡도란쉽게말해그방법의효율성, 즉계산을하는데얼마나많은비용 cost 을필요로하는가를뜻한다. 복잡도의척도가되는비용에는컴퓨터로돌렸을때걸리는시간, 총연산수, 사용된메모리의양, 사용된하드웨어의양등이올수있다. 비록어떤문제가계산가능하다할지라도알고리즘의복잡도가너무크다면계산하기가어려울것이다. 예컨대, 이론적으로는모든경우의수를따져보면바둑의최선전략을계산할수있을테지만, 그경우의수는천문학적으로많은수치이므로이것은현실적으로아주힘든문제이다. 알고리즘복잡도의기준으로가장흔히쓰이는것은계산시간과총연산회수이다. 계산시간은기본연산을한번하는데걸리는시간에그연산이등장하는회수를곱한것과같으므로, 이둘은거의같게볼수있다. 이를알고리즘의시간복잡도 time complexity 라고한다. 기본연산을무엇으로두느냐는문제나알고리즘에따라달라질수있는데, 보통두수의덧셈이나곱셈, 논리연산, 메모리할당등을기본연산으로둔다. 최대공약수문제로돌아가자. 둘중의작은수를 n 이라하면, 첫번째알고리즘은최악의 경우, 즉최대공약수가 1 인경우 2 n 번의나눗셈을해야한다. 반면두번째알고리즘으로는 log n 에비례하는시간안에해결이가능하다. 별것아닌것처럼보일지몰라도 n 이아주 커지면경우이두알고리즘의차이는어마어마하게벌어질수있다. 어떤결정형문제가주어졌을때, 그것을계산할수있는알고리즘의시간복잡도에따라 그문제는 P 혹은 NP 로분류될수있다. ( P 와 NP 둘다아닐수도있다.) 다음장에서는 P 와 NP 가무엇인지본격적으로알아보자. 5
2. P 와 NP 2.1. 결정형문제 P 와 NP 는결정형문제에한해서정의된다. 여기서결정형문제 decision problem 란그답이 예 yes 와 아니오 no 둘중의하나로결정되는문제를뜻한다. 이와대조되는개념으로답에셋이상의경우의수가있는문제를함수형문제 function problem 라고한다. 결정형문제의예 : 1 세자연수 n, m, d 가주어졌을때, n 과 m 의최대공약수가 d 인가? 2 자연수 n 이주어졌을때, n 이소수 ( ) 인가? 3 자연수 n 에대해, x = n n n + y z 을만족하는자연수쌍 (, y, z) 4 프로그램 P 와입력 x 가주어졌을때, P(x) 가정지하는가? x 가존재하는가? 함수형문제의예 : 1' 두자연수 n, m 이주어졌을때, n 과 m 의최대공약수를구하여라. 2' 자연수 n 이주어졌을때, n 의약수는몇개인가? 3' 자연수 n 에대해, n n n + y z 을만족하는자연수쌍 (, y, z) x = x 를모두나열하라. 위의예에서볼수있듯함수형문제는결정형문제보다더포괄적이지만, 많은함수형문 제는그와상응하는결정형문제로변형시킬수있다. 어떤결정형문제에대해유한한시간내에답이 예 인경우와 아니오 인경우모두를답할수있으면그문제는결정가능하다 decidable 라고한다. 1, 2, 3은모두결정가능한문제의예이다. 유한한시간내에답이 예 인경우를답할수있으면그문제는해결가능하다 solvable 라고한다. 다른말로, 부분적으로결정가능하다 partially decidable, 반결정가능하다 semidecidable, 증명가능하다 provable 등으로쓰기도한다. 4는결정가능하지는않지만해결가능한문제의대표적인예로, 정지문제 halting problem 로잘알려져있다. 해결가능하지않은문제도존재한다. 대각화언어 diagonalization language 가그예이다. 6
2.2. 결정성 / 비결정성알고리즘결정성알고리즘 deterministic algorithm 은 각단계에서그다음단계가유일하게결정되는알고리즘 을말한다. 우리가여러프로그래밍언어로작성하는코드는모두결정성알고리즘에의한것이다. 비결정성알고리즘 non-deterministic algorithm 은 각단계에서그다음단계가유일하게결정되지않는알고리즘 을말한다. 구체적인예를통해비결정성알고리즘이무엇인지알아보자. 다음은주어진자연수 n 이 합성수인지혹은소수인지를판별하는문제에대한비결정성알고리즘이다. 코드는파이선문법을기반으로작성되어있다. 하지만파이선은비결정성알고리즘을지원 하지않으므로, 붉고굵은글씨 OR 를통해이를표현하였다. 예컨대 A OR B OR C 는 A, B, C 중의한가지를 임의로선택 해서실행시킨다는의미이다. # 예제 : 합성수판별문제에대한비결정성알고리즘 def iscomposite(n): a, b = 2, n-1 while b-a > 0: # 2 a n-1인 a를선택하는과정 m = (a+b)/2 a = m OR b = m if b-a == 1: a = b OR b = a if n%a == 0: return True else: Return False while 문안에있는두개의 OR 가가장중요한부분이다. while 문안에서는두수 a 와 b 의차를한번에반씩줄여나간다. a = m OR b = m 에서 a = m 을실행시키면뒤의반 을취하게되고, b = m 을실행시키면앞의반을취하게된다. n=12 라고하자. 이경우우리가얻어야하는답은 True 이다. 만약 while 문에서 a=5 가 선택되었다면, n%a!= 0 이므로 False 가출력될것이다. 만약 while 문에서 a=4 가선택되 었다면, n%a == 0 이므로 True 가출력될것이다. 이렇듯비결정성알고리즘은같은입력에 대해서도출력이여러가지일수있다. 7
때문에입력 x 에대한비결정성알고리즘 P 의출력을이렇게정의한다. 결과가 True 로나오는경우의수가하나라도존재하면, P(x) = True 이다. 모든경우에대해결과가 False 로나오면, P(x) = False 이다. 이정의에따르면 iscomposiite(12) = True, iscomposite(7) = False 와같이 바른결과를얻는다. 각단계에서이어질수있는다음단계의경우의수가최대 k 가지일때, 그값을알고리 즘의비결정도 degree of non-determinism 라부른다. 합성수판별문제에대한예제의경우 k = 2 이다. # 예제 def f(a): t = 0 for x in A: t += x OR t -= x OR pass for x in A: t *= x OR t *= x+1 OR t *= x+2 OR pass if t > 100: return True else: return False 바로위의예는코드자체에는별의미가없으므로형태에만주목하도록하자. 첫번째 for 문의비결정도는 3 이고두번째 for 문에서는 4 이므로, 전체알고리즘의비결정도는 4 이다. 결정성알고리즘과비결정성알고리즘의계산능력이동일함은증명되어있다. 즉, 비결정성 알고리즘에의해해결가능한문제는결정성알고리즘에의해서도해결가능하다. ( 그역은 당연히성립한다.) 8
2.3. P 문제 P 문제는 결정성알고리즘으로다항식시간내에해결가능한결정형문제 이다. 다항식시간 polynomial time 이라는것은입력의크기를 n 이라할때, 적당한 k 에대하여시간복잡도가 n 의 k 차다항식에비례하거나그보다작게된다는것을뜻한다. 이때다음의세가지연산을기본연산으로허용한다. (1) 변수의값을 1 만증가시키거나감소시키는대입문 (++, --) (2) 값이 0 인경우에계산의흐름을변화시키는조건문 (if) (3) 반복을위한점프문 (goto) 아래예제는점프문을지원하는 C 문법을채용하였다. // 예제 : 세가지기본연산을사용하여구현한두자연수의덧셈 int plus(int a, int b){ L1: if(b==0) goto L2; a++; b--; goto L1; L2: return(a); } 위의세연산을사용하면우리가쓰는프로그래밍언어에내장되어있는 for 문, while 문등 을모두구현할수있다. 따라서앞으로보게될예제에서는위의세가지기본연산외에 파이선에서제공하는함수나연산을자유롭게이용할것이다. n 이하의두자연수가주어졌을때, 둘의최대공약수는 이것은 n 에대한 1 차다항식 log n 시간내에계산될수있었다. 1 n 보다작다. 따라서최대공약수문제는 P 문제이다. P 문제들의모임을 P 클래스 P-class 라한다. 그래프의최단경로탐색등수많은결정형 문제가 P 클래스에속한다. 9
2.4. NP 문제 NP 문제는 비결정성알고리즘으로다항식시간내에해결가능한결정형문제 이다. P 문제와다른점이라면알고리즘이결정성이냐비결정성이냐의차이이다. 다음은부분집합합문제 subset sum problem 에대한비결정성알고리즘이다. 부분집합 합문제는유한집합 A 가주어졌을때, A 의공집합이아닌부분집합중에서원소의합이 0 x S 인것이존재하는가, 즉 x = 0 인 φ S A 가존재하는가를판정하는문제이다. # 예제 : 부분집합합문제에대한비결정성알고리즘 def ssp(a): S = [] for x in A: # A의부분집합 S를구하는과정 S.append(x) OR pass # A의각원소에대해그것을 S에추가할지 선택 if sum(s) == 0: return True else: return False 부분집합합문제에대한예제알고리즘의경우, 집합 A 의원소의개수가 n 개일때시간 복잡도는 1 n 에비례한다. 따라서부분집합합문제는 NP 문제이다. 이문제에대한다항식 시간결정성알고리즘은아직발견되지않았다. 곧, 이문제가 P 문제인지는알수없다. NP 문제들의모임을 NP 클래스 NP-class 라한다. 10
3. P = NP? 3.1. P 와 NP 의상관관계 결정성알고리즘은비결정성알고리즘에서비결정도가 k = 1 인특수한경우이다. 그러므로 P 클래스가 NP 클래스에포함됨은명백하다. 그럼역으로 NP 클래스는 P 클래스에포함될까? 다른말로하면, 모든 NP 문제는 P 문제일까? 이것이바로대망의 P : NP 문제이다. 여기서잠깐! 앞에서결정성알고리즘과비결정성알고리즘의계산능력이동일하다고한 적이있지않던가? 하지만이것은단순히해결가능성에대한이야기이지, 복잡도에대한것이아니다. 일반적 으로한문제에대해 T (n) 으면, 그것을 할수있다. T (n) 이다항식일때, 의시간복잡도와비결정도 k 를가지는비결정성알고리즘이있 T (n) k 이내의시간복잡도를가지는결정성알고리즘으로변환하여시뮬레이션 T (n) k 는지수함수이므로충분히큰 n 에대해서어떠한차수의다항 식보다도큰값을갖는다. 그렇기때문에이사실은 P : NP 문제의답에는그다지큰도움을 주지못한다. 이문제의답은아직확실히밝혀진바가없다. 11
3.2. NP- 완전성사람들은 P : NP 문제의답에다가가기위해 NP- 완전성 NP-completeness 이라는개념을도입하였다. 어떤문제가 NP-완전문제라는것은 (1) 그자체가 NP 문제이며, (2) 다른모든 NP 문제를그것으로다항식시간환원시킬수있다는것을뜻한다. 여기서환원 reduction 은한문제를이용해서다른문제를푸는것이다. 아래그림은문제 A 를문제 B 로환원시킨것을도식화한것이다. 문제 A 와 B 의입출력을맞추어주기위한함수 f, g 가다항식시간내에계산가능할때, 이를다항식시간환원 polynomial-time reduction 이라한다. 따라서만약에우리가 NP- 완전문제들중하나에대한다항식시간결정성알고리즘을찾 는다면, 모든 NP 문제가다항식시간안에풀리게되는셈이다. 즉, P : NP 문제가해결된다. 부분집합합문제는 NP- 완전문제이다. 다른 NP- 완전문제로는다음과같은것들이있다. 충족가능성문제 satisfiability problem (SAT) 논리식이주어졌을때, 논리값을참으로만드는변수대입이존재하는가. 해밀턴경로 Hamiltonian path 그래프가주어졌을때, 각꼭지점을한번씩만지나는경로가존재하는가. 순회세일즈맨문제 traveling salesman problem (TSP) 각변에가중치가주어진그래프와 x 가주어졌을때, 길이가 x 보다작은해밀톤 회로가존재하는가. 12
3.3. P : NP 문제의의의 P : NP 문제가풀린다면그답이 P = NP 이든 P NP 이든엄청난일이다. 만약 P = NP 임이증명되면, 지금까지효율적으로풀수없다고생각했던수많은문제들이 한꺼번에해결되는것이다. 물론다항함수가지수함수나기타비 ( ) 다항함수보다항상작다 고만은할수없다. 999 999n 정도되면웬만큼크지않은 n 에대해서는 n 2 보다훨씬큰값을 갖는다. 그런까닭에 P = NP 를증명한다고해서, 모든어려운계산을순식간에할수있는 것은아닐수도있다. 그럼에도불구하고이론컴퓨터과학에있어서는큰의미를가질것이 다. 반대로 P NP 임이증명되면, 어떤문제에대해서는명백한한계가있음이밝혀지는셈이다. 그다지행복한결과는아니지만, 대부분의컴퓨터과학자들은 P NP 일것으로추측하고있다. 어디까지나추측일뿐이지증명된바는전혀없기때문에여기에너무얽매일필요는없다. 지금까지 P : NP 문제에대한웬만한배경지식은다익혔다. 이제 100 만달러가걸린문 제에한번도전해보는건어떨까? 13