태리정's IT

tensorflow installation trouble.

Error Case)
이와 같은 오류가 나는 경우)

from google.protobuf import symbol_database as _symbol_database
ImportError: cannot import name symbol_database

Solution ) this is path problem!

Try this:

python
>>> import google.protobuf
>>> google.protobuf.__file__

then you can see which file is using.
if other version is used instead of distro-provided(check your package folder) get off the confused one.

in my case

/usr/lib/python2.7/dist-packages/google/protobuf/__init__.pyc

instead of

/usr/local/lib/python2.7/dist-packages/google/protobuf/__init__.pyc

위와 같이 명령어를 실행하면 어떤 파일이 사용 중인지 확인 할 수 있다.
만약 distro-provided가 아닌 경로를 참조 중이라면 해당 모듈을 끄면 해결 할 수 있다.

sudo apt-get remove protobuf

이 명령어로 삭제한다.

최근 알고리즘을 공부하면서 NP Complete를 다시 이해하려고 하는데 도무지 용어 정리가 안되는 문제가 발생했다. 하루종일 찾아보다가 결국 깔끔하게 정리를 하긴 했는데 한글로 된 설명은 도무지 부족한 것 같다.

그래서 블로그에다가 정리를 해두면 많은 사람들이 쉽게 접근 하지 않을까? 란 생각과

내가 가진 지식의 정리도 깔끔하게 될 것 같아 기록하고자 한다.

이것을 Theory 공간을 따로 만들어서 정리해야 할지, 수학이라고 해야할지 고민하다가 그냥

P-NP문제와 함께 이야기 하면 좋을것 같아서 다 같이 말해본다.

P-NP Problem는 클레이 수학연구소에서 발표한 7개의 '밀레니엄 문제' 중 하나로 컴퓨터 과학에서 중요한 위치를 차지하고 있는 문제다[1]. (밀레니엄 문제에는 모두 현상금이 걸려있다는 사실!, 너 내 동료가 되라)

여기서 P란
P : Polynomial time 이내에 해결 가능한 알고리즘을 말한다. 즉, 알고리즘의 복잡도가 O(n^x)로 표현되는 모든 문제들을 말한다. 이때, 해결 이란 단어에 대해 자세히 말하고 싶은데, 여기서 말하는 해결이란 어떠한 instance에 대해 동일하게 해답을 내놓을 수 있는 방법을 말한다.

그리고 NP란

NP : Polynomial time에 답의 존재유무를 확인 할 수 있는 문제를 말한다. 사실 P는 deterministic polynomial time의 약자고 NP는 non-deterministic polynomial time의 약자인데, 그 이유는 NP에 속하는 문제들이 다항시간에 해결 가능한지, 불가능한지 모르기 때문이다(그 누구도 증명하지 못했다). 마찬가지로 답을 확인한다는 것에 대해 말하고 싶은데 흔히 결정문제라고도 말한다. 해결 방법은 모르지만 답의 유무는 확인 가능한 문제들의 집합이다.

일반적으로 문제가 P에 속한다면 NP라고 말할 수 있다. 왜냐하면 P인 경우 어떠한 instance에 대해서도 문제의 해답을 내놓을 수 있기 때문에 답의 존재유무에 대해 판별하는 문제 또한 같은 복잡도내에 해결 할 수 있기 때문이다(복잡도 O(n^x)이하를 가지는 경우 같은 복잡도 내에 모든 해를 구하기 때문).

즉, 보충 설명을 요약하면 NP는 P보다 큰 집합이고 NP는 P보다 '해결'하기 어려운 문제임.

 True                    ??

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

휴, 이제 NP Hard를 설명하고자 한다. NP-Complete를 먼저 해야할지 NP Hard를 먼저 해야할 지 고민되었지만 개인적으로 생각하건데 NP Hard를 이해하고 NP-Complete를 이해하는 일이 쉽다고 생각한다.

NP-Hard는 누가 이름지었는지 모르지만 비직관적인 동시에 직관적이다. 무엇인지 이해한 사람은 매우 직관적으로 느껴질법한 그런 이름이라고 생각한다. (내 경험담이다)

NP-Hard : "at least as hard as the hardest problems in NP"[2]. 개떡같은 설명이다. 번역하면 NP-난해. NP만큼은 어려운 문제란다. 사실 맞는 말이다. 그치만 이를 이해하려면 우선 transformation algorithm을 설명해야만 할 것 같다.

transforamtion algorithm에 대한 자세한 것은 [3]을 참조하라!( 읽기 싫으면 밑의 그림 설명도 충분하다 )

이 그림은 어떤 problem A에 대한 알고리즘의 변경이다. 그림에서 tran은 transformation algorithm을 의미하는데 각 instance x는 A문제의 instance이고 y는 problem B의 instance를 의미한다. 그러니까 tran이란 함수는 어떤 문제 A의 instance x들을 어떤 문제 B의 instance y로 맵핑하는 일이다.
그리고 이러한 x들과 y의 관계는 다대일이 될 수 있어서 다대일 환산이라고도 한다. 그리고 만약 이 변형이 다항시간내에 이루어 질 수 있다면 polynomial-time many-one reducible(다항시간 축소변환?)이라고 한다.

이제 NP-Hard를 제대로 말 할 수 있는 토대의 지식을 다 설명한 것 같다.

다시 한 번, NP-Hard란

NP-Hard : NP에 속하는 모든 문제에 대해 다른 문제로 polynomial-time many-one reducible되는 문제를 말한다. 이 개념이 참 어렵다. 원문으로 보자면 "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H"[2]. 이렇다. 솔직히 가끔은 나도 모르겠다! 아니 양반, 도대체 이게 무슨 개소리요? 하고 때려치우고 싶을테지만 NP와의 차이점을 요목조목 짚으며 넘어가면 우린 충분히 이해 할 수 있다. NP에 있는 문제들은 다항시간에 답을 확인 할 수 있는 문제인 동시에 P를 포함하고 있다. 하지만 NP-Hard의 경우는 그렇지 않은 것이 다항시간에 답을 확인 할 수 있다고 하여( O(n^x) * O(n^y) 는 결국 다항시간의 복잡도를 가지니까) P로 결론 내릴 수 있지 않기 때문이다. 이 차이점을 인지하고 위키의 글을 보면 조금 편하다.

아직 증명이 되지 않은 탓에 두가지 다이어그램을 가지고 있다.

흔히 위키에서도 어디에서건 보면 이 다이어그램을 많이 사용하는데 나도 이제는 충분히 이 다이어그램이 인지하기에 충분하다고 생각한다. (이전엔 이게 무슨 개소리요!? 했단 말이다)

마지막으로 이제는 NP-Complete이야길 해야겠다. 이게 우리 전공에 가장 적합한 이야기이기도 한 동시에 원래 하고자 한 이야기니까. NP-Complete문제는 많이 들어봤을것이다. SAT, Salesman Traveling, Hamiltonian path, graph coloring 등등. 왜 NP-Complete인가? 는 위의 다이어그램을 봤다면 알 것 같다.

NP인 동시에 NP-Hard일 것. 사실 NP인 동시에 NP의 문제를 다항시간내에 다른 문제로 reduction한 내용은 그 유명한 Stephen Arthur Cook의 〈The Complexity of Theorem Proving Procedures〉에 나온 SAT가 그 시초이다. 그리고 하나를 통해 나머지 몇 문제들을 환산함으로써 NP-Complete들의 문제가 등장하게 되었다. 가끔 NP문제중 가장 난해한 문제라고도 한다. 왜냐면 "현재"의 알고리즘으로 그것을 다항시간 내에 해결 가능한지 불가능한지 알 수 없지만 적어도 다항시간 이상은 걸릴 수 밖에 없는 알고리즘일 것이기 때문이다.(다항시간축소변환에만 다항시간이 걸리기 때문. 하지만 다항시간*다항시간이라면 다항시간 이니 느린것은 아니다)

길게 적어왔지만 결국은

NP-Complete :

문제 A가 NP에 속하며,

동시에 NP에 속하는 모든 문제에 대해 polynomial-time many-one reducible되는 문제들의 집합이다.

이 그림 참 많이 쓰이는데, 그에 대한것은 SAT가 먼저 reduction 가능함을 보였기 때문이다. 이후 SAT로 문제를 치환할 수 있다면 NP-Complete임을 보일 수 있는 연구가 진행되었고 다음과 같이 나왔다. 어떤 NP문제를 이와 같은 문제로 치환 가능하다면 당연히 NP-Complete임을 보일 수도 있다. 물론 다양한 방식이 있을 수 있음을 전제하는 것이 연구하는 것에 도움 되리라 생각한다.

http://4mhz.de/cook.html[4] 이곳에 들어가면 Stephen Arthur Cook의 논문을 읽어볼 수 있다. 당시의 출판본을 다시 쓴 글이다.(논문이 사장되고 싶지 않다면 이렇게 인지도가 있어야 한다, 요즘이야 인터넷에 올리면 되겠지만서도 당시의 스캔본을 깔끔하게 정리한 것을 보면 새삶 그의 창의력이 부럽기만 하다)

이로써 오늘 적고 싶은 내용이 마무리 된 것 같다. 이걸 머릿속에 정리하는데 5시간은 걸린 것 같다. 수업 시간에 분명 듣고 넘어간 기억이 있는데 아무래도 내 hash function은 그다지 좋은 성능은 아니다(오류가 있다).

부디 많은 이가 P-NP문제에 도전하길 바란다. 정말 수학계나 컴퓨터계에 큰 자리매김을 하게 될 것이다.

Reference

[1] http://ko.wikipedia.org/wiki/P-NP_%EB%AC%B8%EC%A0%9C
     http://en.wikipedia.org/wiki/P_versus_NP_problem
[2] http://en.wikipedia.org/wiki/NP-hard
[3] http://en.wikipedia.org/wiki/Polynomial-time_reduction
[4] http://4mhz.de/cook.html

힐베르트(Hilbert) 18번 문제.

다면체로 n차원의 공간을 메우는 문제는 이미 100년도 전에 제기되었던 문제로 2차원과 3차원에 한에서는 그 이전에도 이미 증명된 바 있는 흥미로운 문제다.

공간을 메울때는 틈이나 겹치는 부분이 없어야 한다는 제약 조건이 있는데, 이 때 공간을 채울 수 있는 도형이 유한가지임을 증명하는 문제다(이미 해결되었으니 문제는 아니다)

[그림1] 2차원 벽지 타일(조금 아쉬운 예의 그림을 구했구나 싶다)

평면(2차원)에서는 17개의 대칭군이 존재한다.(참고, 그림1)

3차원에서는 219개의 대칭군이 존재한다(Fedorov, Schoenflies).(참고, 그림2)

이것이 시사하는 바는 매우 큰 의미를 지니는데 어떤 벽지를 만들때에 있어서 인쇄하는 방법이 정확히 17가지가 있다는 이야기이기 떄문이다.

즉, 어떤 벽지를 만들때에 있어서 17가지 이상의 대칭군을 가지는 벽지를 만들 수는 없다는 이야기이다.

3차원의 이야기는 좀 더 흥미롭다. 이것은 원자의 결정체를 이루도록 분자를 구성하는 방법(atomic arrangement)이 정확히 219가지가 존재한다는 이야기다! 이것은 실험이나 관찰을 통해 얻은 결과가 아니다!

순수한 논증만으로 이 세계의 구성을 알아냈다는 것은 참으로 놀라운 일이 아닐수 없다.

[그림2] 3차원상에서의 구성방법

이를 넘어 4차원 이상에 대해서도 수학자들의 연구는 계속되고 있으며 몇몇 차원에 관해서는 이미 증명되어있다. 어떻게 생긴 구조인지 상상할 수 없어도 문제는 해결 가능하다는 것이 신비로울 따름이다.

[1] http://en.wikipedia.org/wiki/Space_group

[2] "케플러의 추측", 조지 G. 슈피로, p. 207