쉽게 들리는 문제는 우리 우주에 비해 너무 큰 숫자를 산출합니다 | 콴타 매거진

5세 어린이가 컴퓨터 과학의 최전선에서 질문을 이해할 수 있는 경우는 흔하지 않지만, 그런 일이 일어날 수 있습니다. 예를 들어, 앨리스라는 유치원생이 사과 두 개를 갖고 있는데 오렌지를 더 좋아한다고 가정해 보세요. 다행스럽게도 그녀의 반 친구들은 환율이 엄격하게 적용되는 건전한 과일 거래 시스템을 개발했습니다. 예를 들어 사과를 포기하면 바나나를 얻을 수 있습니다. 앨리스는 바나나나 칸탈로프를 줍고 내려서 그녀가 가장 좋아하는 과일을 얻는 일련의 거래를 실행할 수 있습니까?

충분히 간단하게 들립니다. “초등학교에 가서 아이들에게 말해 줄 수 있어요.”라고 말했습니다. 크리스토프 하세, 옥스포드 대학의 컴퓨터 과학자. "사람들은 '그건 쉬울 거야'라고 생각할 겁니다."

그러나 벡터 추가 시스템의 도달 가능성 문제라고 불리는 Alice의 딜레마에 깔려 있는 수학 문제는 놀라울 정도로 미묘합니다. 일부 사례는 쉽게 해결할 수 있지만 컴퓨터 과학자들은 문제에 대한 포괄적인 이해를 개발하기 위해 거의 반세기 동안 노력했습니다. 이제 지난 몇 년간 일련의 획기적인 발전을 통해 그들은 문제가 얼마나 복잡해질 수 있는지 정확히 확고히 확립했습니다.

이 어린애 같은 문제는 터무니없이, 거의 만화처럼 복잡하다는 것이 밝혀졌습니다. 너무 복잡해서 사실상 다른 모든 문제가 유명한 어려운 계산 문제 글쎄, 어린이 놀이처럼 보이네. 이 문제를 해결하는 데 필요한 노력을 정량화해 보세요. 곧 너무 큰 숫자에 직면하게 되어 숫자를 세는 것조차 들어본 적 없는 숫자에 도달하게 될 것입니다. 그러한 숫자는 종종 우주의 규모와 비교를 불러일으키지만, 그러한 비유조차도 부족합니다. "그건 정당하지 않을 것입니다."라고 말했습니다. 게오르크 제체, 독일 카이저슬라우테른에 있는 막스 플랑크 소프트웨어 시스템 연구소의 컴퓨터 과학자입니다. “우주는 너무 작아요.”

도달 범위 내에서?

본질적으로 접근 가능성 문제는 숫자 목록인 벡터라고 불리는 수학적 개체에 관한 것입니다. 이 목록의 항목을 구성 요소라고 하며 벡터의 구성 요소 수를 차원이라고 합니다. 예를 들어, 앨리스의 과일 목록은 XNUMX차원 벡터(a, b, c, d), 그 구성 요소는 주어진 시간에 그녀가 가지고 있는 사과, 바나나, 멜론, 오렌지의 수를 나타냅니다.

벡터 추가 시스템(VAS)은 시스템의 상태 간 가능한 전환을 나타내는 벡터 모음입니다. Alice의 경우 전이 벡터(−1, −1, 1, 0)는 사과와 바나나를 멜론으로 교환하는 것을 나타냅니다. VAS 도달 가능성 문제는 특정 초기 상태에서 특정 목표 상태로 이동할 수 있는 허용된 전환 조합이 있는지, 또는 수학적으로 말하면 시작 벡터를 목표 벡터로 변환하는 전환 벡터의 합이 있는지 여부를 묻습니다. 한 가지 문제는 시스템 상태를 설명하는 벡터의 어떤 구성 요소도 XNUMX 아래로 떨어질 수 없다는 점입니다.

"이것은 현실 모델에 대한 매우 자연스러운 제한입니다."라고 말했습니다. 보이치에흐 체르빈스키, 바르샤바 대학의 컴퓨터 과학자. "사과의 개수는 음수일 수 없습니다."

일부 시스템에서는 대상 벡터에 도달할 수 있는지 여부를 쉽게 확인할 수 있습니다. 그러나 항상 그런 것은 아닙니다. 컴퓨터 과학자들은 도달 가능성을 결정하는 것이 얼마나 어려운지 명확하지 않은 단순해 보이는 벡터 추가 시스템에 가장 관심이 있습니다. 이러한 사례를 연구하기 위해 연구자들은 주어진 시스템의 크기를 정량화하는 숫자를 정의하는 것부터 시작합니다. 이 숫자는 다음과 같이 표시됩니다. n에는 차원 수, 전환 수 및 기타 요소가 포함됩니다. 그런 다음 도달 가능성 문제의 난이도가 얼마나 빨리 증가할 수 있는지 묻습니다. n 더 커집니다.

이 질문에 답하기 위해 연구자들은 두 가지 보완적인 접근 방식을 사용합니다. 첫째, 도달 가능성을 결정하는 데 최소한의 노력이 필요한 특히 까다로운 벡터 추가 시스템의 예를 검색합니다. 이러한 최소 수준을 문제의 복잡성에 대한 "하한"이라고 합니다. 그들은 연구원들에게 "주어진 문제에 대한 가장 까다로운 시스템"이라고 말합니다. n 적어도 이 정도는 힘들지.”

둘째, 연구자들은 "상한선", 즉 가장 사악한 시스템에서도 도달이 얼마나 어려운지에 대한 제한을 설정하려고 합니다. “주어진 상황에서 가장 까다로운 사례는 다음과 같습니다. n 기껏해야 이 정도는 힘들지.” 가장 까다로운 시스템에서 도달 가능성이 얼마나 어려운지 정확하게 확인하기 위해 연구자들은 만날 때까지 하한을 위로, 상한을 아래로 밀어내려고 합니다.

악몽의 물건

벡터 추가 시스템은 오랜 역사를 가지고 있습니다. 1960년대부터 컴퓨터 과학자들은 계산을 여러 개의 작은 조각으로 나누고 해당 조각에서 동시에 작업하는 프로그램을 모델링하는 데 이를 사용해 왔습니다. 이러한 종류의 "동시 컴퓨팅"은 이제 어디에나 존재하지만 연구자들은 여전히 ​​그 수학적 기초를 완전히 이해하지 못하고 있습니다.

1976년에 컴퓨터 과학자 리처드 립튼 VAS 도달 가능성 문제의 복잡성을 이해하기 위한 첫 번째 단계를 밟았습니다. 그는 한 상태가 다른 상태에 도달할 수 있는지 여부를 결정하는 가장 빠른 방법이 두 상태 사이의 일련의 전환을 계획하는 시스템 구축 절차를 개발했습니다. 이를 통해 그는 도달 가능성 문제의 난이도를 측정하는 척도로 신중하게 선택된 두 상태 사이의 최단 경로 길이를 사용할 수 있었습니다.

그럼 립톤 증명 그는 규모의 시스템을 구축할 수 있었다 n 두 상태 사이의 최단 경로에는 $latex 2^{2^n}$ 이상의 전환이 포함되었습니다. 이는 그의 시스템에서 도달 가능성을 결정하는 데 필요한 노력에 대한 해당 이중 지수 하한을 의미합니다. 이는 놀라운 발견이었습니다. 두 배의 기하급수적인 성장은 컴퓨터 과학자들의 악몽이었습니다. 실제로 연구자들은 $latex {2^5}= 32$이지만 $latex 2^{2^5}$는 4억이 넘는 일반적인 기하급수적 성장에도 주저하는 경우가 많습니다.

대부분의 연구자들은 Lipton이 가능한 가장 복잡한 벡터 추가 시스템을 조작했다고 생각했습니다. 이는 그가 하한을 최대한 높게 올렸다는 의미입니다. 이 경우 누락된 유일한 것은 그에 따른 상한입니다. 즉, 도달 가능성을 결정하는 것이 더 어려운 시스템이 없다는 증거입니다. 그러나 그것을 증명하는 방법을 아는 사람은 아무도 없었습니다. 컴퓨터 과학자 Ernst Mayr가 가장 가까이 다가왔을 때 증명 1981년에는 원칙적으로 모든 벡터 추가 시스템에서 도달 가능성을 결정하는 것이 항상 가능하다는 사실이 밝혀졌습니다. 그러나 그의 증명은 문제가 얼마나 어려울 수 있는지에 대한 정량적 상한선을 제시하지 않았습니다. 바닥은 있었지만 천장은 보이지 않았습니다.

Lipton은 “나는 확실히 그것에 대해 계속 생각했다”고 말했다. "그러나 얼마 후 나는 포기했고, 내가 말할 수 있는 한 40년 동안 아무도 진전을 이루지 못했습니다."

2015년에 컴퓨터 과학자들은 제롬 르루 및 실뱅 슈미츠 드디어 설립 정량적 상한 — 연구자들은 그것이 Lipton의 하한선을 충족시키기 위해 아래로 밀릴 수 있는 첫 번째 단계일 뿐이라고 가정할 정도로 너무 높습니다.

하지만 그런 일은 일어나지 않았습니다. 2019년에 연구자들은 Lipton의 것보다 훨씬 더 높은 하한을 발견하여 수십 년간의 통념을 뒤집었습니다. VAS 연결 문제는 예상했던 것보다 훨씬 더 복잡했습니다.

힘의 탑

충격적인 2019년 결과는 실패에서 비롯됐다. 2018년에 Czerwiński는 Leroux와 필립 마조비에츠키현재 바르샤바 대학의 컴퓨터 과학자인 , 그것은 관련 문제를 해결하는 데 도움이 되었을 것입니다. 후속 논의에서 연구원들은 매우 복잡한 벡터 추가 시스템을 구축하는 유망한 새로운 방법을 찾았습니다. 이는 오랫동안 진행이 정체되었던 VAS 도달 가능성 문제에 대한 새로운 하한선을 암시할 수 있습니다.

Czerwiński는 “내 마음 속에 있는 모든 것이 VAS 연결 가능성과 연결되어 있습니다.”라고 회상했습니다. 강의량이 적은 한 학기 동안 그는 Leroux, Mazowiecki 및 다른 두 연구원과 함께 해당 문제에만 집중하기로 결정했습니다. 스와보미르 라소타 바르샤바 대학교와 란코 라지치 워릭 대학교 (University of Warwick)

몇 달 후, 그들의 노력은 결실을 맺었습니다. 체르빈스키(Czerwiński)와 그의 동료들 시연 두 상태 사이의 최단 경로가 XNUMX중화(tetration)라는 수학적 연산을 통해 시스템의 크기와 관련되는 벡터 추가 시스템을 구축할 수 있었는데, 이는 심지어 악몽 같은 두 배의 기하급수적 성장도 길들여 보이게 만듭니다.

테트레이션은 덧셈으로 시작하여 수학에서 가장 친숙한 연산을 연결하는 패턴을 직접적으로 확장한 것입니다. 함께 추가 n 숫자의 복사본이며 결과는 해당 숫자에 다음을 곱하는 것과 같습니다. n. 같이 곱하면 n 지수의 복사, 즉 숫자를 제곱하는 것과 같습니다. n번째 힘. 종종 위쪽을 가리키는 한 쌍의 화살표로 표시되는 테트레이션은 이 순서의 다음 단계입니다. n 지수화한다는 뜻이다 n 권력의 탑을 생산할 시간 n 이야기가 높습니다.

$latex 2 uparrowuparrow 3$ 또는 $latex 2^{2^2}$는 16이고, $latex 2 uparrowuparrow 4$는 65,000이 조금 넘고, $latex 2 uparrowuparrow 5$는 거의 20,000자리 숫자입니다. $latex 2 uparrowuparrow 6$의 모든 숫자를 적는 것은 물리적으로 불가능합니다. 이렇게 작은 우주에 사는 부담입니다.

획기적인 결과에서 Czerwiński와 그의 동료들은 크기의 벡터 추가 시스템이 존재한다는 것을 증명했습니다. n 도달 가능성을 결정하는 가장 좋은 방법은 $latex 2 uparrowuparrow n$ 전환보다 많은 경로를 계획하는 것입니다. 이는 Lipton을 왜소하게 만드는 새로운 하한을 암시합니다. 그러나 테트레이션만큼 어리둥절하기는 하지만 여전히 문제의 복잡성에 대한 최종 결정은 아니었습니다.

Quinquagintillion과 그 너머로 

VAS 도달 가능성의 복잡성에 대한 충격적인 새로운 하한이 나온 지 불과 몇 달 후, Leroux와 Schmitz 아래로 밀려 그들은 XNUMX년 전에 설정한 상한선을 사용했지만 테트라레이션까지는 도달하지 못했습니다. 대신 그들은 도달 가능성 문제의 복잡성이 Ackermann 함수라는 수학적 괴물보다 더 빠르게 커질 수 없다는 것을 증명했습니다.

해당 기능을 이해하려면 XNUMX차화를 정의하는 데 사용되는 패턴을 암울한 결론으로 ​​가져가십시오. 펜테이션(pentation)이라고 하는 시퀀스의 다음 작업은 반복되는 테트라레이션을 나타냅니다. 그 뒤에는 반복되는 펜테이션을 위한 또 다른 작업(헥산)이 뒤따릅니다.

$latex A(n)$로 표시된 Ackermann 함수는 수직선의 각 정지점에서 이 작업 사다리를 한 단계 위로 이동할 때 얻을 수 있는 것입니다: $latex A(1) = 1 + 1$, $latex A (2) = 2 × 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$ 등. $latex A(4)$의 자릿수는 그 자체로 대략 1경에 해당하는 엄청난 숫자입니다. 이는 1 뒤에 153개의 5이 오는 기발하고 거의 필요하지 않은 이름입니다. “Ackermann of XNUMX에 대해 걱정하지 마세요.”라고 조언했습니다. 하비에르 에스파자, 뮌헨 기술 대학의 컴퓨터 과학자.

Leroux와 Schmitz의 결과는 하한과 상한 사이에 큰 격차를 남겼습니다. VAS 도달 가능성 문제의 정확한 복잡성은 범위의 끝이나 범위 사이에 있을 수 있습니다. Czerwiński는 그 격차를 그대로 두려고 하지 않았습니다. “우리는 이 일이 우리 인생에서 해본 일 중 가장 큰 일이라는 것이 분명했기 때문에 계속해서 노력했습니다.”라고 그는 말했습니다.

마지막 돌파구는 2021년에 이루어졌으며, Czerwiński는 Łukasz Orlikowski라는 학부생 XNUMX학년에게 조언을 하고 있었습니다. 그는 Orlikowski에게 문제의 간단한 변형을 할당하여 속도를 높였으며 Orlikowski의 작업은 두 사람이 일반적인 도달 가능성 문제에도 적용되는 새로운 기술을 개발하는 데 도움이 되었습니다. 그것은 그들이 할 수 있게 해주었다 하한을 올려라 실질적으로 – Leroux와 Schmitz의 Ackermann 상한까지. 독립적으로 일하면서 Leroux는 동등한 결과 같은 시간에.

마지막으로 연구자들은 도달 가능성 문제의 실제 복잡성을 파악했습니다. Czerwiński, Orlikowski 및 Leroux의 하한은 두 상태 사이의 최단 경로가 Ackermann 함수에 비례하여 증가하는 점진적으로 더 큰 벡터 추가 시스템의 시퀀스가 ​​있음을 보여주었습니다. Leroux와 Schmitz의 상한선은 도달 가능성 문제가 이보다 더 복잡해질 수 없음을 보여주었습니다. 이를 해결하기 위한 확실한 실제 절차를 원하는 사람에게는 거의 위안이 되지 않습니다. 이는 단순해 보이는 계산 문제가 얼마나 미묘해 보일 수 있는지를 보여주는 놀라운 예시입니다.

완료되지 않음

연구자들은 VAS 도달 가능성 문제의 정확한 복잡성을 파악한 후에도 계속해서 연구해 왔으며, 질문에 대한 많은 변형이 아직 답변되지 않은 상태로 남아 있습니다. 예를 들어, Ackermann 상한과 하한은 증가하는 다양한 방법을 구분하지 않습니다. n, 예를 들어 벡터의 차원을 늘리거나 허용되는 전환 수를 늘리는 것입니다.

최근 Czerwiński와 그의 동료들은 진전 고정 차원을 갖는 벡터 추가 시스템의 변형에서 복잡성이 얼마나 빨리 증가할 수 있는지 연구하여 이러한 뚜렷한 효과를 분리합니다. 그러나 아직 해야 할 일이 더 남아 있습니다. 벡터 추가 시스템을 쉽게 시각화할 수 있는 XNUMX차원에서도 도달 가능성 문제의 정확한 복잡성은 아직 알려지지 않았습니다.

Mazowiecki는 “어떤 면에서 이는 우리에게 당혹스러울 뿐입니다.”라고 말했습니다.

연구자들은 상대적으로 단순한 사례에 대한 더 나은 이해가 벡터 추가 시스템보다 더 정교한 다른 계산 모델을 연구하기 위한 새로운 도구를 개발하는 데 도움이 되기를 바라고 있습니다. 현재 우리는 이러한 보다 정교한 모델에 대해 거의 아는 바가 없습니다.

Zetzsche는 "나는 이것을 계산 가능성을 이해하기 위한 매우 근본적인 탐구의 일부라고 생각합니다."라고 말했습니다.

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 컴퓨터 과학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 상품.