뜻밖의 순열 조합 문제
많은 사람이 ‘규칙 찾기 문제‘를 즐겨 푼다. 아래 주어진 숫자조합을 살펴보자.
1, 3, 9, 33, 153, ?
마지막에 올 숫자는 얼마일까? 생각나지 않아도 괜찮다. 답은 확실히 모두의 예상을 빗나가기 때문이다. 이 숫자는 순열 조합문제에서도 ‘초순열Superpermutations 문제‘이다. - P150
해외 애니메이션 마니아 사이트에는 「스즈미야 하루히의 우울」을 가장 빨리 보려면가능한 모든 순서를 어떻게 사용할 수 있을까?"라는 글이 올라왔다. - P150
예를 들어, 이 애니메이션이 3부작이라고 가정할때, 모든 순열의 수는 3!=6이다. 이렇게 총 6가지 서로 다른 순서로 이 애니메이션을 본다고 할 때, 123, 132, 213, 231, 312, 321의 경우를 생각할 수 있다. - P151
예를 들면, 1, 2, 3의 순서로 3부작을 다 본 다음 1화를 볼 수 있는데 즉, 순서는 1231이다. 뒤 세 번의 순서를 보면 231의 순서로다 본 셈이 된다. 1231을 본 후 시간을 아끼려면 2화를 봐야 할게 뻔한데, 이렇게 되면 312라는 조합을 다 본 셈이 된다. - P152
목표는 1, 2, 3이라는 세 개의 숫자로 이루어진 가장 짧은 숫자배열을 찾아내는 것이며, 그것은 1, 2, 3의 여섯 가지 배열 순서를 모두 포함하는 것이다. - P152
그 예로 3의 초순열은 여러분이 종이에 조금만 써봐도 찾을 수 있는데(예: 123121321), 그 길이는 9이다. 4의 초순열을 찾는 것은조금 어렵지만 그 길이는 33이다. 주의할 점은 초순열을 찾아내는 것이 어려운 것이 아니라, 그것이 개의 문자로 만든 순열을모두 포함하는 문자열에서 길이가 가장 짧다는 것을 증명하는 것이 매우 어렵다는 것이다. - P152
실제로 n-1의 초순열 수에 n!을 추가하면 2의 초순열 수라고 믿는다.
1!+2!+3!+・・・ +n!
예를 들면, 6의 초순열 수는, 153+6!=873이라고 추측한다. - P153
예상치 못한 일이 2014년에 일어났다. 로빈 휴스턴Robin Houston이라는 연구자가 컴퓨터 프로그램을 이용하여 길이가 872인 6의초순열 수를 찾아낸 것이다. - P154
길이가 872인 6의 초순열
12345612345162345126345123645132645136245136425136452136451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654132654312645316243516243156243165243162543162453164253146253142653142563142536142531645231465231456231452631452361452316453216453126435126431526431256432156423154623154263154236154231654231564213564215362415362145362154362153462135462134562134652134625134621536421563421653421635421634521634251634215643251643256143256413256431265432165432615342613542613452613425613426513426153246513246531246351246315246312546321546325146325416325461325463124563214563241563245163245613245631246532146532416532461532641532614532615432651436251436521435621435261435216435214635214365124361524361254361245361243561243651423561423516423514623514263514236514326541362541365241356241352641352461352416352413654213654123 - P154
예를 들어, 123이라는 지점에서 231 이라는 지점까지의 연결을 고려한다면, 123 배열에 1만 더 쓰면 231 이라는 조합을 포함하기 때문에 이 선의 가중치는 1이 된다. 반대로 231이라는 점에서 123이라는 점으로 연결하려면 231 배열에 2와 3을 써야 123 배열을 얻을 수 있기 때문에 이 경우는 가중치가 2가 된다. 이렇게추론하면 모든 6개 점 사이의 연결에 이러한 가중치를 부여할 수있다. - P156
하지만 불행히도 여행하는 외판원 문제는 알고리즘 이론에서
‘NP-완전 문제‘(쉽게 이해하자면 하나의 답도 매우 느리게 확인하는 문제)로, 알고리즘을 구하는 것은 매우 비효율적이다. - P156
이렇게 출력된 결과가 최단 경로를 보장할 수 없고 일정 시간내에 반드시 출력이 있다는 보장도 없기 때문에 ‘확률적 알고리즘‘이라고 한다. 그가 길지 않은 시간에 길이가 753인 경로를 찾아낸 것은 행운이었다. - P157
그략 이건안 로빈 휴스턴이 초순열 수 문제에 대해 발견한 것을 보고 관심을 가졌으며, (중락).
그가 제시한 새로운 상한은 다음과 같다.
n!+(n-1)!+ (n-2)!+(n-3)!+(n-3) - P159
얼마 후 캐나다 수학 교수 존스턴이 순열 조합 문제를 검색하던 중 검색엔진에서 이 답변을 보게 됐다. 그는 이 익명의 대답에조금 주의를 기울인 결과, 그의 증명이 기본적으로 옳다는 것을 알았다. - P161
예를 들어 n=6일 때 우리는 하한 공식에 따라 867을 계산하는데 현재 찾은 가장 짧은 것은 872로 5만큼 차이가 난다. 7의 초순열 수는 5884와 5908 사이로 이 문제는 해결되지 않았다. - P161
길이가 153인 5의 서로 다른 8가지 초순열
벤 채핀Ben Chaffin0 2014년 3월에 처음 발견하였다.
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
123451234152341253412354123145231425314235142315423124531243512431524312543121354213524135214352134521325413251432513425132451321543215342153241532145321
123451234152341253412354123145231425314235142315421352413521435213452135421534215432154231245321453241532451325413251432513425132453124351243152431254312
123451234152341253412354123145213425134215342135421345214352145321452314253142351423154231245312435124315243125432154325143254132451324153241352413254312
123451234152341253412354132541352413542134521342513421534213541231452314253142351423154231245321435214325143215432145324153245132453124351243152431254312
123451234152341253412354132514325134251324513254135241354213541231452134521435214532154321534215324153214523142531423514231542312453124351243152431254312
123451324513425134521354213524135214352134512341523412534123541231452314253142351423154231245312435124315243125432153421532415321453215432514325413254312
123451324153241352413254132451342513452134512341523412534123541231452314253142351423154213542153421543214532143521432514321542312453124351243152431254312 - P162
‘복잡도 동물원‘ 속의 ‘마트료시카‘
앞에서 ‘시간 복잡도‘와 ‘P와 NP문제‘가 무엇인지에 대해 이야기하였다. ‘P와 NP 문제‘ 외에 복잡도에 대한 질문이 또 있을까? 대답은 ‘그렇다‘이다. 게다가 매우 많다. - P291
첫 번째로 소개할 복잡도는 ‘다항식 계층polynomial Hierarchy, PH 문제‘
이다. PH문제는 NP 문제의 일반화인데, 그것의 정의는 ‘2차 논리‘로 언어의 집합을 표현할 수 있다는 것이다. - P292
6명의 소그룹이 존재하여 이 6명은 다른 사람들과 모두 친한 사이가아니며, 7명의 소그룹이 존재하지 않아 이 7명은 다른 사람들과도 친한사이가 아니다.
보다시피 이 명제는 이전의 명제보다 훨씬 복잡하지 않은가? - P293
물론 우리는 이전의 명제에 계속 추가하여, 다음과 같이 바꿀수도 있다.
모든 자연수 에 대하여 2개의 소그룹이 존재하고, n + 1개의 소그룹이 존재하지 않는다. - P293
게다가 과학자들은 ‘P문제=NP 문제‘, 즉 P=PH라면 PH문제가 NP문제에 비해 본질적으로 복잡성이 증가하지 않다는 사실을 발견했다. - P293
다음은 ‘다항식 공간-SPACE 문제‘에 대한 이야기다. 여기서 P는
‘다항식‘, space는 바로 ‘공간‘이다. 기존에는 시간 복잡도를 고려했지만 하나의 알고리즘이 실행될 때는 시간뿐 아니라 메모리도소모해야 하는데, 여기서 메모리는 ‘공간‘으로 추상화할 수 있다. - P294
과학자들은 이미 모든 PH문제가 다항식 공간 문제‘임을 증명했고, 모든 NP 문제는 ‘다항식 공간 문제라는 것도 간단하게 증명할 수 있다. - P294
NP문제를 풀 때 우리는 이미 열거한 상황의 일련번호만 남겨두면 된다. 다시 ‘소그룹 문제‘를 예로 들자면, 시간 소모를 고려하지 않을 때 우리는 열거법으로 풀 수 있다. 즉, 2명 중에서 6명의 조합을 취하는 경우를 일일이 열거할 필요가 있다. - P294
어떤 다항식 공간 문제는 NP문제가 아닌가? 이는 미해결 문제이다. 현재 찾아낸 몇 가지 가능한 문제는 바둑의 끝내기 문제 등 보드게임과 관련된 문제이다. - P295
그런데 끝내기 문제는 또 NP문제가 아닌 것처럼 보인다. 만약 당신에게 쌍방의 낙점 순서를 준다면, 이것이 쌍방의 가장 좋은 낙점 순서인지 어떻게 판단할 수 있을까? - P297
여러분이 추측한 바와 같이, 현재 과학자들은 지수 시간 문제이지만 다항식 공간 문제가 아닌 어떤 문제가 존재한다는 것을아직 증명하지 못했다. 즉, 이 문제는 지수 시간 계산이 필요하고지수 수준의 메모리 소모도 반드시 필요하다. - P298
여기까지 우리는 NP, PH 및 P-SPACE의 단순한 순서에서 복잡한 순서로 복잡도 사슬을 구성하였다. 또한 이전에 P가 NP의 하위 집합임을 언급하였다. 흥미롭게도 사람들은 양자컴퓨터를 연구하면서 P와 NP 사이의 두 가지 복잡도를 발견(또는 정의)했다. - P298
첫 번째 유형으로 ‘BPpBounded-error, Probabilitic, Polynomial time‘라고 하며 제한된 오류 확률을 가진 다항 시간‘이라는 의미이다. 이름에서 알 수 있듯이 BPP문제는 먼저 다항 시간 알고리즘을 가지고있지만, 우리는 이 알고리즘이 일정한 오류 확률을 갖도록 허용한다. - P299
우리는 ‘계발적‘ 수단을 써서 가능한 한 빨리 합리적인 해답을찾을 수 있다. 예를 들어, ‘3색 문제‘를 해결할 때, 우선 어떤 영역에 어떤 색을 칠해 보고 그 영역에서 확산시켜 가능한 한 적은 색상으로 모든 영역을 채색할 수 있다. - P299
이와 같이 2개의 영역이 있는 그래프에서 최대 3 번 시도해도답이 없다면 ‘해가 없다‘고 한다.
컴퓨터 프로그램으로 위의 과정을 충분히 시뮬레이션할 수 있으며, 이 알고리즘은 다항 시간 내에 끝낼 수 있다. - P300
두 번째 유형은 BQPBounded-error, Quantum, Polynomial time 문제이다. 이것은 ‘제한된 오류 확률을 가진 양자 다항 시간‘이라고 하는데, 사실 BPP문제보다 ‘양자‘라는 단어가 더 많다. - P300
그러나 양자의 행동은 통제되지 않고 모두 ‘확률적인 행동이며,
‘계산‘ 결과는 항상 오차가 있을 수 있다. ‘평행우주 이론‘에 따르면, 매번 양자컴퓨터의 계산 결과를 ‘측정한 후에 우리는 어떤 우주에서는 정확한 결과를 얻었고, 어떤 우주에서는 잘못된 결과만을 얻을 수 있었다. - P301
어쨌든 양자컴퓨터는 항상 오차가 있기 때문에 빠르게 처리할수 있는 문제를 ‘제한된 오류확률을 가진 양자 다항 시간 문제‘,
줄여서 ‘BQP문제‘라고 부르는 것이다. 현재 전형적인 BQP문제는 소인수분해 문제이다. - P301
1994년 수학자 피터 윌리스턴 쇼어 Peter Willistone shor(1959~)는 복잡도가 O(log³ N)에 불과한 표준 다항 시간 문제인 소인수분해양자 알고리즘을 제안했는데 이 소인수분해는 곧 BQP 문제이다. - P302
‘확실‘에서 ‘불확실성‘
앞에서 난수 검정에 대해 알아보았다. 여기서는 컴퓨터를 사용하여 난수를 생성하는 방법에 대해 설명하려고 한다. 흔히 컴퓨터의 난수 생성 알고리즘을 가짜 난수 생성 알고리즘 또는 결정식 난수 생성기 DRBG라고 하는데, 이는 한 자리 이진수 0 또는 1을 50%의 확률로 생성할 수 있다는 뜻이다. 왜 이런 알고리즘은 모두 이진수 생성기일까? 그 이유는 평소 균일 분포의 난수를 사용하는 경우가 가장 많고, 균일 분포의 난수가 있으면 다른 분포로변환하는 것도 비교적 간단하기 때문이다. - P82
그렇다면 왜 ‘가짜 난수 생성 알고리즘‘이라고 할까? 굳이 ‘가짜‘를 붙인 이유가 궁금하다. - P82
상당히 오랜 역사를 가지는 난수에 근거하는 것으로 당대 주류의 계산 능력으로는 불가능하며, 상당 기간 후에 난수에 대한 추측의 성공 또는 실패 확률과 0.5 사이에 ‘무시할 수 있는 차이가 발생한다는 것이 확인된다면, 이러한 난수는 적합하다.
위의 정의에서 적합한 가짜 난수 생성 알고리즘의 조건은 동적이고 발전할 수 있다는 것을 알 수 있다. 알고리즘은 기술과 계산력이 발전함에 따라 합격에서 불합격으로 바뀔 수도 있다. - P83
|