[완료]NP-completeness에서 "polynomially related"에 대한 보조정리 증명문제
안녕하세요, 알고리즘 책을 보다가 의문나는 점이 있어서 혹시나 해결의 실마리를 찾을까하여 여쭈어 봅니다.
[참고링크]
Introduction To Algorithms 2Nd Edition, Chapter 34에 나오는 내용인데요, 구글에서 검색이 되길래 해당 페이지에 나온 내용을 링크합니다. Lemma 34.1증명 부분을 참고해 주십시오.
http://www.tebyan.net/index.aspx?pid=31159&BookID=23840&PageIndex=230&Language=3
[질문내용]
링크에서 Lemma 34.1에 보면 이런 내용이 나옵니다.
The conversion of encodings takes time O(n^c), and therefore |e1(i)| = O(n^c), since the output of a serial computer cannot be longer than its running time.
결론부터 말씀드리자면 위에 인용한 문장에서 "since ~"이후 부분이 이해가 잘 안됩니다. output이란 것은 얼마든지 조건에 따라 커질 수도 있고 작아질 수도 있는 값인데 무작정 running time보다는 작다라고 주장하면서,
therefore |e1(i)| = O(n^c)
라고 해버리는데요,
1) |e1(i)| 의미하는 output의 길이라는 단위와 Big Oh notation으로 표기되는 실행시간을 나타내는 단위가 서로 같지 아니한데, 어떻게 비교가 될 수 있을까요?
2) output이라는 것은 |e1(i)|에서 표현된 것처럼 단순히 encoding된 값의 길이를 나타내는 것인가요? 예를 들어, C언어로 표기하면 strlen( e1(i) )의 값처럼??
3) 만약 위에 2)의 질문이 맞다면, 256진법으로 표기된 어떤 큰수 a를 이진수 b로 바꾸었을 때, table을 활용하여 구현한 알고리즘이라면, 작은 실행시간에 매우 큰 길이의 b가 output이 되는데요, 이럴 때는 output > running time 이라는 부등식이 성립되는 것은 아닌지요.
4) 책이 틀렸을리는 만무하지만, 책에서 증명된 바와는 다르게 생각해 보았습니다. Figure 34.1에서 나온 것과 비슷한 건데, 결론부분에서 O(n^c + n^k)는 polynomial time이므로 Lemma 34.1이 성립한다고 생각합니다. 어떤 부분에서 제가 잘못 생각한 것인지 지적 좀 부탁드립니다.
5) 구글에 찾아보니, 앞서 나온 문장을 그대로 논문에 인용한 교수들도 있었고, 혹시나 해서 서울대학교에 문병로 교수님이 번역하신 책도 확인해 보았으나 문장 그대로 번역이 되어있네요. 따로 주석같은 것도 없었습니다.
이제 배워나가는 입장이라 모르는 것이 많습니다. 고견부탁드립니다.
이미 해결하셨을지도
이미 해결하셨을지도 모르겠습니다만; 결론부터 말하자면 출력이 전체 수행 시간을 dominate할 수 없다는 게 요지입니다.
문장에서 serial computer라고 하는 것은 튜링 머신이나 그와 동등한 능력을 가진 일반 컴퓨터를 가리키는 것으로 생각하셔야 합니다. 프로그램의 출력을 output 명령으로 내보낸다면 길이 n의 문자열을 출력하기 위해서는 n번의 output 명령이 필요하니 많아 봐야 O(n)의 시간 복잡도가 나올 것이고, 튜링 머신의 경우에도 1을 찍으려면 테이프를 움직여야 하기 때문에 O(n)의 시간 복잡도가 나올 겁니다. 어느 쪽이든 "출력"을 위해 사용하는 primitive가 상수 시간이 걸리는 이상 since 뒤의 조건은 틀린 게 아닙니다.
1)에서 질문하신 문제는 전혀 상관 없는 얘기입니다. |e1(i)| = O(n^c)라는 말은 "e1(i)의 길이는 n^c의 상수배로 bound된다"라는 말로 해석해야 합니다. Big O notation은 어느 함수에라도 쓰일 수 있고 시간과 전혀 상관 없습니다. 그리고 3)은 상수배 차이니까 아무 문제가 없지요.
답변감사합니다 ^_^
답변 진심으로 감사드립니다~
1)에 질문은 제가 잠꼬대를 했는지 이상한 소리를 써놨네요. f(n) = O(g(n))이 암묵적으로 g(n) = O(f(n))을 의미한다는 것을 깜빡하고 있었습니다.
3)은 1)을 다시 생각해보면 아무 문제가 없겠네요. 변명입니다만, polynomial이라는 표현만 들어갔더라면 제가 헷갈릴 일이 없었을 것같습니다. (복잡도 비교가 아니었다면 저 문장 자체는 좀 애매한 느낌이 있다는 생각을 지울 수가 없네요.)
다시 한 번, 감사드립니다.
--
http://njh1983.blogspot.com/
f(n) = O(g(n)) 이면 g(n) =
f(n) = O(g(n)) 이면 g(n) = O(f(n)) 틀렸습니다.
f(n) = n , g(n) = n^2 일 경우
f(n) = O(g(n)) 이지만 g(n) =/= O(g(n))
f(n)이 theta(g(n)) 일때만 양방향이 성립됩니다.
화장실 가다가...
1) Theta일 때만 성립하는 것이 맞습니다. 자꾸자꾸 이상한 소리해서 죄송합니다.
솔직히 f(n) = O(g(n))표현의 의미를 방금 이해했습니다.
Comparison of functions에서 "Symmetry"속성은 theta에만 적용된다고 책에도 잘 나와있네요;
2) 그러고보니, theta에서 성립하더라도 f(n) = theta(g(n)) 이면 g(n) = theta(f(n))이라는 표현은 제가 제기한 문제에 있어서 쓸데없는 단서가 되어버렸네요.
3) 그냥 f(n) = O(g(n))일 뿐이고,,, lifthrasiir님이 지적해 주신 것처럼 serial computer에 대한 개념을 이해하면 되는 문제였는데...
결론적으로 제가 asymptotic notation f(n) = O(g(n))이게 무슨 뜻인지 정확히 이해를 못했었네요.
지적해주셔서 정말 감사합니다.
--
http://njh1983.blogspot.com/
Growth of Function을 오래
Growth of Function을 오래 전에 공부한 탓인지 헷갈리는 부분도 있고 요새 다른 것에 심취해 있어서 머리 속이 뒤죽 박죽 되어가지고 새벽에 이상한 소리를 많이 쓴 것같습니다. 몇 가지 정리를 좀 해야할 것 같네요.
(1) f(n) = theta(g(n)) 이면 g(n) = theta(f(n)).
앞서 이야기하신 내용을 보면,
라고 하셨는데, 이 말은 임의의 상수 k에 대해서 |e1(i)|=k*n^c 라는 의미로 해석됩니다.(upper bound라는 의미였다면 오해의 소지가 조금 있었습니다.) 여기서 제가 첫번째 이상한 소리가 나옵니다.f(n) = O(g(n)) 이면 g(n) = O(f(n))이라고 갑자기 말해버립니다. 즉, 위에 인용된 문장과 토끼군님 말씀에 따르면 상수배로 bound되기 때문에 f(n) = O(g(n)) 이면 g(n) = O(f(n))가 성립되는 것이죠. 비판없이 이 말을 수용하게된 이유가 해당 책의 연습문제 3-4 a번에 이 문장이 나오기 때문입니다. 저는 이것이 lemma인줄 알고 그대로 옮겨 적었습니다. 밤중에 안경을 벗고 스탠드만 켜놓고 책을 보다가 "오~ 여기있군!"하고 그대로 옮겨 적게 되었습니다. 정확하게는,
라고 책에 나옵니다.(물론 우습게도 연습문제에서는 이 말이 틀렸다는 것을 증명하라는 것이었습니다.)
자, 정리하면 "e1(i)의 길이는 n^c의 상수배로 bound된다"라고 말하려면 정확하게는, f(n) = theta(g(n)) 이면 g(n) = theta(f(n))가 되겠습니다. 김전일님이 지적해 주신 것처럼 이 문장은 Big-oh에서는 성립하지 않습니다. 따라서 |e1(i)| = O(n^c)라는 말은 "|e1(i)|의 길이는 n^c의 상수배로 bound된다"라고 말씀하신 것은 옳지 않다고 생각합니다. 저도 사람인지라 순간적으로 착각을 했네요. 만약에 bound를 upper bound라고 생각하고 쓰셨다면 upper라는 단서를 달아야 합니다. theta omega Big-oh모두 bound 이니까요.
(2) serial computer란 무엇인가?
논증의 과정은 일반적으로 "주장"이 나오고 "근거"가 제시됩니다. 그리고 "근거"가 왜 "주장"에 대한 증명이 되는지, 그 상관 관계를 명확하게 해주는 것이 바로 "가정;warrant or assumption"이지요. 제가 원래 질문에서 인용하였던 ", since ~ " 문장이 바로 "가정"이됩니다.
이 가정이라는 것은 독자가 명확하게 이해할 수 없다고 판단되는 경우 가정에 대한 정확한 설명을 곁들이는 것이 기본입니다. 왜냐하면 논증에 있어서 가정이란 것은 일반성을 띄고있는 상식적인 수준에서 제시되는 것을 기본전제로 하기 때문입니다. 예를들면 다음과 같습니다.
A : "어제 밤에 비가 왔는가?"
B : "아침에 마당이 젖어 있는 걸보니, 어제 밤에 비가 온 것이 분명하군."
A : "마당이 젖어 있으면, 밤에 비가 온 것이다라는 주장의 근거는 무엇인가?"
B : "일반적으로 그렇게 생각하기 때문일세"
A와 B의 대화에서 처럼 어제 밤에 비가 왔다는 것을 주장하기 위해 "가정"을 제시합니다. "마당이 젖어 있으면, 밤에 비가 온 것이다." 이 가정은 일반적인 상식으로 누구나 받아 들일 수있기 때문에 예를 들어 마당에 스플링클러가 설치되어 있는 특수한 상황을 제외하고는 옳은 논술이 됩니다.
본론으로 돌아가서, 책에 나온 since 이하의 부분은 "가정"입니다. "가정"이 성립되는 조건하에서 "주장"과 "근거"가 맞물리게 되는 것입니다. 하지만, Lemma34.1에는 serial computer 언급이 전혀없습니다. 하지만 저자는 증명에서는 serial computer를 끌어 왔으므로, 독자를 설득켜서 자신의 주장을 이해시키려면 serial computer라는 것이 무엇인지 명확히 해야합니다. 그렇지 않으면 "좋지 않은 논술"이 되는 것입니다.
토끼군님 지적해주신 것처럼, 이 책의 저자가
라고 serial computer에 대해서 명확히 하였다면 독자들에게 훨씬 친절한 책이 되었을 겁니다.
(3) |e1(i)| = O(n^c)라는 표현은 upper bound가 k*n^c가 된다는 것을 표현
제가 이해한 바로는, 좀 더 정확하게 표현하면 이 lemma에 대한 증명은 worst case를 이용하기 위해 Big-oh를 끌어들입니다. worst case에서도 다항시간(polynomial time)을 만족하면 증명이 성립되기 때문입니다. Chapter4에 보면 어떤 주어진 문제에 대하여 tight한 복잡도를 예측하기 매우 힘들기 때문에 여러 가지 방법을 동원하는데, "the inductive assumption is not strong enough to prove the detailed bound"라고 설명을 합니다.
정리하자면, 이 번 Lemma34.1에 대한 증명 또한 worst case를 이용하게 된 것이라고 보면되겠습니다. 토끼군님이 언급하신 부분을 생각해 볼 때, serial computer의 시간복잡도가 어떤 이유에서건 O(n)이 나올 것이라고 설명하는 것은 상당히 무리가 있는 것같습니다.
정확하게 표현하면 다음과 같을 것입니다.
이렇게 표현하는 것이 정확할 것같습니다. O(n)을 논술에 끌어들이는 것은 부절할 것같군요.
(4) 일단 제가 이해한 것은 여기까지입니다. 한 참이나 지난 질문을 찾아서 답변해주시는 센스에 적잖히 놀랐습니다. 저 질문을 어떻게 찾아서 답변을 다셨을까 신기하기만 합니다. 토끼군님 친절한 답변 덕분에 어리숙했던 제 지식이 조금이나마 발전한 것같아서 기분이 좋습니다. 언제 서울 오시면 술이라도 한 잔 ㅎㅎㅎ
농담입니다. 장황하게 떠들었는데, 제 이야기에 잘못된 부분이 있으면 매콤하게 지적해주시길 부탁드립니다. 아는 것이 별로 없으니 이렇게라도 배우는 것이 큰 도움이 되는 군요. ^_^
그럼 이만.
--
http://njh1983.blogspot.com/
여러 가지 착각하시는 것 같은데
어떤 학문을 배우는 것은, 외국어를 배우는 것처럼, 단순히 단어의 정의를 배우는 것만 아니라 그 일반적인 쓰임새를 배우는 것도 포함됩니다. 물론 쉬운 일은 아닌데, 좀 잘못 알고 계신 부분이 있습니다.
여러 레벨의 논리를 섞어놓아서 정확히 무슨 말을 하시려는지 잘 모르겠습니다만... 전산학에서 bound라고 말을 썼으면 특별한 말이 없는 한 upper bound라고 생각하는 게 옳습니다. 굳이 확실히 써야 한다면 O,Theta,Omega를 쓰거나 "X is upper-bounded by Y" 혹은 (드물게) "X is bounded from (above/below) by Y" 처럼 씁니다.
심지어 저 말을 Theta로 해석하더라도, 이렇게 이해하시면 안됩니다. e1(i) = Theta(n^c)은 아래쪽의 의미로 해석할 수 없습니다. (Hint: (n + 1/n) = Theta(n)입니다. n + 1/n = k*n이 되는 상수 k가 존재할까요?)
지금 해당 챕터에서 계속 P/NP 등등을 얘기하고 있는데, 상식적으로 이 챕터에서 다루는 모든 내용은 튜링 머신과 같은 computational power를 가진 기계를 대상으로 한다고 보는 게 맞습니다. 모든 Lemma 하나하나마다 "이건 parallel computation에는 적용되지 않음"이라고 토를 달 필요는 없지 않겠습니까?
전산학 교과서는 법정 토론이 아닙니다. 저자가 생각할 때 "상식적으로 앞뒤 문맥을 봐서 이해할 수 있는 것"을 구태여 다시 적지는 않습니다.
* 시간이 없어서 여기까지만...
의견감사합니다.
의견감사합니다. 좋은 하루 되세요.
(죄송합니다만, 따로 코멘트는 하지 않겠습니다.)
--
http://njh1983.blogspot.com/
(2)를 굳이 설명할
(2)를 굳이 설명할 필요는 없다고 봅니다. jick 님께서 지적하셨지만 P/NP라는 용어 자체의 정의가 결정적/비결정적 튜링 머신을 가정하기 때문에 그 범위를 넘어 가는 모델을 생각할 이유는 없으니까요. (non-serial computer라... 뭘까요? parallel? quantum?)
의견감사합니다.
의견감사합니다. 바로 윗글에서 jick님이 벌써 정의하셨군요.
(속된말로 "깜놀"이었습니다.)
좋은 하루 되세요.^_^
--
http://njh1983.blogspot.com/
댓글 달기