다윈의 성선택에 문제 제기하는 암컷들 (중략) 다윈...

다윈의 성선택에 문제 제기하는 암컷들

(중략)
다윈은 ‘원래는 남성에게 속해야 마땅한‘ 성역할이 ‘전환된 것처럼 보이는 승부욕 강한 암컷들의 ‘비정상적인 소수의 사례가 존재한다는 것을 인지했지만 무시해도 좋은 예외로 내쳐버렸다. - P266

14 Darwin, The Descent of Man (1871) - P472

편협하지만 대단히 영향력 있는 다윈의 태도로 인해 이후150년 동안 동성 경쟁의 연구는 짝을 두고 벌이는 수컷의 경쟁에만 초점을 맞췄고, 암컷의 전투적 잠재력은 대개 무시되었다.¹⁵ - P266

15 Paula Stockley and Jakob Bro-Jør-gensen, ‘Female Competition and its Evolutionary Consequences in Mam-mals‘ in Biological Review, 86 (2011),
PP. 341-66 - P472

새의 노래가 대표적인 예다. 명금류의 아름다운 노랫소리는오랫동안 성선택의 고전적 본보기로 여겨졌다. 라이벌과 성공적으로 경쟁하여 이성의 애정을 얻기 위해 한없이 정교해진 수컷들의 장식품이라고 말이다. - P266

실제로 명금류 수컷의 뇌는 노래할 필요가 없는 겨울철에 수축한다고 알려졌다. - P266

암새의 울음소리는 귀가 들리지 않는 과학자들의 귀에 울려 퍼졌고 너무나 익숙한 변명들로 무시되었다. 암새의 소리는 그저 ‘호르몬 불균형‘의 결과이거나 영양의 뿔처럼 수컷과 유전자 설계도를 공유한 덕분에 얻은 비적응성 부산물이라고 말이다.¹⁶ - P267

16 K. A. Hobson and S. G. Sealy, ‘FemaleSong in the Yellow Warbler‘ in Condor,
92 (1990), pp. 259-61; and RachelMundy, Animal Musicalities: Birds,
Beasts, and Evolutionary Listening (Wes-leyan University Press, 2018), p. 38 - P472

이런 집요한 수컷 중심적 분류가 랭모어의 심기를 몹시 불편하게 했다. 지난 30년 동안 랭모어는 명금류 암컷의 복잡한 발성을 연구하고 이들의 음성을 세상이 듣게 하려고 분투하고 있다. - P267

랭모어에 따르면, 150년 동안 암컷의 노래가 잊힌 이유가 단지구식 성차별주의적 편견의 결과만은 아니다. 사실은 지리적 편향에 더 큰 원인이 있었다. - P268

전 세계를 아우르는 분류군임에도 명금류 연구는 전통적으로유럽과 북아메리카에서 주로 이뤄졌다. 저 지역의 명금류는 대부분 철새이고 최근에 진화한 참새목에 속해 있으며 실제로 암컷의 노래가 억제된 편이다. 유럽울새처럼 진짜로 노래하는 암새들은 암수의 형태가 크게 차이 나지 않아 시끄러운 수새로 오해받기 쉽다.²⁰ - P268

20 Naomi Langmore, ‘Quick Guide toFemale Birdsong Current Biology, 30(2020), pp. R783-801 - P472

명금류는 4,700만 년 전에 오스트레일리아에서 진화했다고알려졌다.²² 발상지에서 암새의 노래가 만연하다는 사실로 미루어 랭모어와 동료들은 원래 명금류 암새는 늘 노래하지 않았을까 의심하게 되었다. - P269

22 Carl H. Oliveros et al., ‘Earth Historyand the Passerine Superradiation‘ inPNAS, 116: 16 (2019), pp. 7916-25 - P472

랭모어의 연구 결과는 실로 뜻깊은 반전이었다. 암컷의 노래가 열대지방에서만 발견되는 최근 진화의 변덕이 아니라는 걸 증명했기 때문이다. 명금류 암컷은 언제나 노래를 해왔다. - P269

랭모어는 "암새가 자신의 영역을 방어하는 데는 피치 못할 사정이 있습니다. 수새가 죽을 수도 있고 이혼할 수도 있고 옆집 암새와 몰래 교미할 수도 있기 때문이지요. 어떤 상황이 닥치더라도 암새는 침입자로부터 자신의 영역을 방어해야 하고, 어쩌면 새로운 짝을 유혹하기 위해 노래를 불러야 할지도 모릅니다. 그러므로 열대지방에서는 암새가 노래를 부르는 능력이 대단히 긴요하지요."라고 말했다. - P270

유럽이나 북아메리카의 정원에서는 형편이 다르다. 그곳에서는 겨울이 되면 명금류 대부분이 남쪽으로 이주한다. 그러다가 봄이 되면 대개 수컷이 먼저 돌아와 제 영역을 확보한 다음 노래를 불러서 암컷을 유혹한다. (중략).  그러나 번식기는 짧다. 암새는 서둘러 수컷을 골라새끼를 낳고 다시 짐을 싸서 남쪽으로 이동해야 한다. 그 결과 암컷은 다른 암컷과 싸움할 여유가 없고 노래해야 하는 선택압도 약해졌을 것이다. - P270

사회적 선택social selection이라는 개념은 1979년에 이론생물학자 메리 제인 웨스트 에버하드 Mary Jane West-Eberhard가 주창한 것이다.²⁵ 웨스트 에버하드는 다윈의 성선택 이론이 번식 철 바깥에서 성과 무관하게 영역이나 자원을 두고 벌어진 경쟁에 의해 정교하게 진화한 형질까지 설명할 수는 없다는 것을 깨달았다. - P271

그럼에도 이 개념에는 아직 논란이 많다. 많은 동물학자들은 진화의 파벌에 또 다른 선택의 갈래를 추가할 필요가 없다고 본다.²⁷ - P272

27 Tim H. CluttonBrock, ‘Sexual Selec-tion in Females‘ in Animal Behaviour(2009), pp. 3-11 - P472

 수컷은 주로 암컷에게 접근하기 위해 겨루지만, 암컷은 생식능력과 육아와 관련된 자원을 두고 싸울 가능성이 더 크다.³⁰ 암컷들의 경쟁은 뒤에서 좀 더 은밀하게 이루어질지 몰라도 수컷의 싸움만큼이나 진화의 경로를 설정하는 영향력을 행사한다. - P272

30 Joseph Tobias, Robert Montgomerieand Bruce E. Lyon, The Evolution ofFemale Ornaments and Weaponry:Social Selection, Sexual Selection andEcological Competition‘ in Philosophical Transaction of the Royal Society B, 367 (2012), pp. 2274-93 - P473

암컷의 선택에 관한 논란의 역사

암컷의 선택은 오늘날 진화생물학에서 가장 뜨거운 감자 중하나지만 과거에도 그랬던 것은 아니다. 하지만 다윈도 처음에 여성의 취향이 가지는 힘을 성선택 이론의 일부로 제시했고, 『인간의 유래와 성선택』에서 이를 자세히 설명했다.  - P84

다윈의 메스꺼움은 공작새 꼬리의 주체할 수 없는 경솔함에 관한 것이었다. 그런 꼬리가 새의 전반적인 생존 과업에 도움이 될 것 같지 않았기 때문이다. 아니, 도움은커녕 위협이 닥쳤을 때 숨거나 비행 능력을 방해하여 해를 끼칠 가능성이 더 컸다. 그렇다면 어떻게 왜 그런 과도한 형질이 자연선택이라는 실용주의적 원칙 아래에서 형성되었을까? - P85

빅토리아 시대의 가부장제는 성선택을 자연선택의 하위 분류로 취급하긴 했어도 암컷과 짝지을 권리를 두고 수컷들이 대결한다는 발상을 받아들이는 데는 문제가 없었다. - P85

놀랄 만한 독창성에도 불구하고 성선택은 문화적, 과학적으로 수용되지 못했다. 자연선택에 의한 진화론은 많은 18, 19세기 사상가들에 의해 예측된 바 있고 엄밀히 말해 앨프리드 러셀 윌리스 Alfred Russel Wallace와 공동 발견한 것이지만, 진화의 원동력으로 성선택을 꼽는 것은 과학계에서 전례가 없는 개념이었다.⁶ - P86

6 G. F. Miller, ‘How Mate ChoiceShaped Human Nature: A Review ofSexual Selection and Human Evolutionin Handbook of Evolutionary Pyschology:Ideas, Issues, and Applications, ed. by C.
Crawford and D. Krebs (1998), PP-87-130 - P458

(전략)
하여 다윈의 대담한 새 이론은 공개적으로 조롱과 무시를 받았다. 가장 강한 비판이 앨프리드 러셀 월리스로부터 나왔다. - P86

위대한 인물이 세상을 떠난 후 몇 년 뒤인 1889년에 누구도 오해할 수 없는 제목을 달고 나온 진화론 저서 『다윈주의Darwinism』에서 윌리스는 다윈의 유산을 검열하는 대담한 행보를 보였다. "암컷의 선택이라는 것을………… 거부하면서 나는 자연선택에 더 큰 효능이 있다고 고집하겠다. 그것은 다윈 자신의 탁월한 신조이다. 그러므로 나는 내 책이 다윈주의의 순수한 옹호자 입장임을 주장하는 바이다.¹⁰ - P87

10 Alfred R. Wallace, Darwinism (Macmil-lan & Co., 1889), p. viii - P458

 1970년대의 성 혁명과 페미니즘이 진화론에도 영향력을 미치면서 다윈의 대담한 생각이 100년의 긴잠에서 깨어났다. 새에서부터 물고기, 개구리, 그리고 나방에 이르기까지 암컷이 감각적 평가를 내릴 수 있고 성적 기호를 행사할수 있다는 생각이 과학적으로 증명되고 또 받아들여졌다. - P87

보노보가 충돌을 피하는 법

그러나 랭엄의 법칙을 짓밟고 여성에게 좀 더 힘이 실리는 과거와 미래의 비전에 희망을 주는 영장류가 하나 있으니 바로 보노보다. 프란스 드 발은 보노보를 ‘페미니스트 운동에 내려진 선물‘⁴⁵이라고 불렀다. 침팬지는 부계 중심에 호전적이지만 보노보는 모계 중심에 평화롭다. 인간은 양쪽에 똑같이 피를 나누었다.  - P329

45 Frans de Waal, ‘Bonobo Sex and Society‘ in Scientific American (1995), pp.82-8 - P476

사실 보노보는 정식으로 기재된 마지막 대형 포유류의 하나다. (중략). 1929년 에른스트 슈바르츠ErnstSchwartz라는 독일 해부학자가 크기가 작아 침팬지 새끼로 기재된두개골 하나를 조사하고 있었다. (중략). 그 두개골이 성체의 것이라고 확신한 슈바르츠는 세상에 자신이 새로운 침팬지 아종을 발견했다고 선언했다. - P330

 침팬지처럼 암컷의 몸집은 수컷의 약 3분의 2 정도이고 출생집단에서 나와 이주한다. 그러나 보노보 암컷의 사회생활은 침팬지와는 완전히 다르다. 뒤를 봐줄 사람 하나 없는 외로운 디아스포라로 성인의 삶을 사는 대신 보노보 암컷은 낯선 집단에 합류해서도 피를 나누지 않은 암컷들과 동맹을 형성한다.  - P330

 한마디로 보노보 암컷은 상호적인 프로타주*의 예술을 완성함으로써 가부장제를 전복할 힘을 얻은 것이다.

*옷을 입은 채 몸을 남의 몸, 물건에 문질러 성적 쾌감을 얻는 행위 - 옮긴이 - P330

이런 형태의 섹스가 다른 야생 영장류에서 기록된 적은 없다.
그러나 보노보 암컷은 다른 어떤 성적 활동보다도 G-G에 더 탐닉한다.  - P331

"오르가슴을 느끼는 게 확실합니다." 에이미 패리시Amy Parish가 내게 말했다. "그들의 음핵은 실제로 이런 종류의 성행위에서최고의 자극을 얻을 수 있는 위치에 있거든요."
패리시 박사는 보노보 암컷의 특별한 유대의 숨은 비결을 처음으로 밝힌 과학자다. - P331

패리시는 박사학위 주제로 보노보를 연구하기로 마음먹은 순간부터 30년간 이들의 사회생활을 기록해왔다. 당시 이 자그마한 대형 유인원에 대해 알려진 것은 거의 없었다. - P332

"암컷들이 신기할 정도로 서로 가까워 보였죠. 서로 함께 어울리고 상대의 아기에게도 친절했거든요." 패리시의 말이다. "보통 혈연관계에 있는 암컷들끼리는 잘 지내는 편입니다. 하지만 피를 나누지 않은 암컷 포유류들은 사이가 좋을 일이 별로 없어요. 피차 외면하거나 아예 공격적으로 대해요." - P332

(전략) 패리시는 이 집단의 알파 암컷인 로레타가 먹이를 통제하는 방식을 언급했다. 먹이에 대한 접근은 흔히 성을 주고받는 대가로 제공된다. 암수 모두 먹이를 얻기 위해 섹스를 거래하고 그 결과 모두 행복하게 앉아서 먹이를 먹는다.  - P332

또한 패리시는 보노보 암텃들이 서로 뒤를 봐주면서 연합한다고 언급했다. 수컷 침팬지와 달리 자기들끼리 싸우기 위한 동맹이 아니라공격적인 수컷을 제압하기 위함이다.
패리시는 암컷들이 수컷에게 심각한 상처를 입힌다는 사실을 알게 되었다.  - P333

"암컷이 그저 빈둥대고 있는 게 아니라는 건 확실합니다. 수컷들에게는 심각하고 위험한 일이에요. 암컷을 많이 두려워하죠."
패리시가 내게 말했다.
그 결과 수컷 보노보는 수컷 침팬지보다 공격성이 훨씬 덜 발달했다. "아마 수년에 걸쳐 교훈을 얻었을 겁니다." 드 발의 말이다. - P334

보노보 수컷은 어미와 아주 친밀한 관계에 있다. 어미의 계급과 권력이 아들을 다른 암컷의 괴롭힘으로부터 보호한다. (중략). 야생에서 수컷은 집단 내 가까운 곳에 어미가있을 가능성이 크다. 그래서 암컷의 공격이 실제적 위협이기는 해도 야생 보노보는 침팬지 사촌보다 훨씬 평화롭게 살아간다. - P334

"(전략)." 프란스 드 발이 내게 말했다.
단, 서로서로 섹스하는 야유회다. "섹스는 보노보가 충돌을 피하는 자구책입니다." 드 발이 덧붙였다. 이 특이한 유인원에게 ‘전쟁 대신 사랑을 하는 히피 유인원이라는 별명이 붙은 이유이다. - P334

인간처럼 보노보는 섹스와 번식이 부분적으로 분리되어 있으며, 암컷은 번식기가 아닐 때도 섹스하는 일이 빈번하다. 그러나보노보의 교미는 평균 13초 만에 끝나는 빠른 작업으로 인간의 악수에 해당하는 일상적인 행위에 가깝다. - P335

그러나 가장 큰 파문을 일으킨 것은 보노보 성 레퍼토리의 극보수적인 결말이다. 보노보는 이성과 섹스를 할 때 종종 정상 체위를 시도한다.  - P335

나오며

편견 없는 자연계

이 여정의 끝에서 나는 그 무엇도 ‘부적합자‘로 여기지 않게 되었다.
생물학적 진실을 밝히는 싸움은 지구에 사는 모든 것의 미래를 보호하기 위해,
포용적인 사회를 만드는 데 반드시 필요하다. - P438

‘객관적 지식‘이란 모순이다.¹
-퍼트리샤 고와티, 『페미니즘과진화생물학 Feminism and Evolutionary Biology』

과학이 동물의 암컷을 얼마나 왜곡해왔는지를 책으로 쓰겠노라처음 마음먹었을 때, 그 이야기가 이렇게 커질 줄도 몰랐고 내 대상이 이토록 문화적으로 오염되어왔는지도 몰랐다. - P441

나오며

1 Patricia Adair Gowaty, Feminism andEvolutionary Biology: Boundaries, Inter-sections and Frontiers (Springer Scienceand Business Media, 1997) - P482

[오늘의 한문장] 배트맨 : 롱 할로윈 디럭스 에디션

히어로물보다 추리물에 가깝다.
다시 말하면 히어로물의 탈을 쓴 추리물로 보인다.

CASE 08 경찰서에 남겨진 다잉 메시지 당신은...

CASE 08

경찰서에 남겨진 다잉 메시지

당신은 전혀 예상치도 못한 곳에서 벌어진 살인 사건을 만납니다.
바로 경찰서 한복판에서 형사 한 명이 예기치 못한 죽음을 맞이한 것입니다.
범인이 무엇을 노린 것인지 알아내고 사건을 해결하기 위해서 당신의 도움이 필요합니다. - P134

뜻밖의 순열 조합 문제 많은 사람이 ‘규칙 찾기 문...

뜻밖의 순열 조합 문제

많은 사람이 ‘규칙 찾기 문제‘를 즐겨 푼다. 아래 주어진 숫자조합을 살펴보자.

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

화마다 반전주는 것을 좋아하는 만화. 전작도 좋았고...

화마다 반전주는 것을 좋아하는 만화.
전작도 좋았고, 다음 작품도 번역되었음 좋겠다.