숫자 15는 무한 그리드의 비밀 한계를 설명합니다.

칠레 대학교의 학부생으로서, 베르나르도 수베르카소 수학을 하기 위해 컴퓨터를 사용하는 것을 희미하게 보았습니다. 그것은 진정한 지적 발견과 상반되는 것처럼 보였습니다.

"컴퓨터를 사용하여 문제를 해결하는 것에 대한 본능이나 본능적인 반응이 있습니다. 환상적인 논쟁의 이상적인 아름다움이나 우아함에 반하는 것처럼 말입니다."라고 그는 말했습니다.

하지만 2020년에 수베르카소는 사랑에 빠졌고 종종 그렇듯이 그의 우선순위가 바뀌었습니다. 그의 집착의 대상은 그가 온라인 포럼에서 본 질문이었다. 대부분의 문제는 훑어보고 잊어버렸지만, 이 문제가 그의 눈에 들어왔습니다. 그는 오른쪽으로 스 와이프했습니다.

그는 "나중에 다른 사람이 솔루션을 게시했을 때 알림을 받기를 바라며 페이스북 그룹의 게시물에 좋아요를 누른 것"이라고 말했다.

문제는 무한한 그리드를 숫자로 채우는 것이었습니다. 밝혀진 바와 같이 그것은 사람이 종달새로 해결하는 종류의 문제가 아니었습니다. 그러기 위해 수베르카조는 칠레를 떠나 카네기 멜론 대학교 대학원에 진학해야 했습니다.

그곳에서 2021년 XNUMX월, 그는 우연한 만남을 가졌다. 마리진 힐레, 어려운 수학 문제를 해결하기 위해 방대한 컴퓨팅 성능을 사용하는 컴퓨터 과학자. Subercaseaux는 Heule에게 문제를 시도하고 싶은지 물었고, 올 XNUMX월에 절정에 달하는 협업을 시작했습니다. 증거 하나의 숫자로 요약할 수 있습니다: 15.

가능한 모든 방법

2002년에 웨인 고다드 Clemson 대학과 같은 생각을 가진 몇몇 수학자들은 특정 제약 조건에서 지도를 색칠하는 것에 대한 이 분야의 주요 질문에 대한 새로운 왜곡을 제시하려고 시도하면서 조합론의 문제를 뱉어내고 있었습니다.

결국 그들은 영원히 계속되는 그래프 용지와 같은 그리드로 시작하는 문제에 도달했습니다. 목표는 숫자로 채우는 것입니다. 한 가지 제약 조건이 있습니다. 같은 숫자가 나올 때마다 거리가 숫자 자체보다 커야 합니다. (거리는 수직 및 수평 분리를 합산하여 측정되며, 이는 그리드가 있는 도시 거리에서 이동하는 것과 유사한 방식으로 "택시" 거리로 알려진 메트릭입니다.) 한 쌍의 1은 택시 거리가 1인 인접한 셀을 점유할 수 없습니다. 그러나 그들은 거리가 2인 직접 대각선 셀에 배치될 수 있습니다.

처음에 Goddard와 그의 협력자들은 유한한 숫자 집합으로 무한한 격자를 채우는 것이 가능한지 알고 싶었습니다. 하지만 그와 네 명의 공동 작업자가 이 "포장 색상" 문제를 게시했습니다. 저널 아르스 콤비나토리아 2008년에 그들은 22개의 숫자를 사용하여 풀 수 있음을 증명했습니다. 그들은 또한 다섯 개의 숫자만으로 풀 수 있는 방법이 없다는 것도 알고 있었습니다. 즉, 문제에 대한 실제 답(필요한 숫자의 최소 수)이 그 중간 어딘가에 있다는 의미입니다.

연구원들은 실제로 무한 그리드를 채우지 않았습니다. 그럴 필요가 없었습니다. 대신 그리드의 작은 하위 집합(예: 10x10 정사각형)을 숫자로 채운 다음 채워진 하위 집합의 복사본을 서로 옆에 배치할 수 있음을 보여주는 것으로 충분합니다. 타일 ​​사본이 있는 바닥.

Subercaseaux는 이 문제를 처음 알게 되었을 때 펜과 종이를 사용하여 타일을 찾기 시작했습니다. 그는 숫자 격자를 스케치하고 줄을 그은 다음 다시 시도했습니다. 그는 곧 그러한 접근 방식에 싫증이 났고 친구에게 지뢰 찾기 게임과 유사한 웹 기반 도구를 설계하도록 요청하여 조합을 더 빠르게 테스트할 수 있도록 했습니다. 몇 주 더 작업한 후 그는 XNUMX개의 숫자로 그리드를 채울 방법이 없다고 스스로 확신했지만 그 이상은 얻을 수 없었습니다. 다양한 방법으로 숫자를 채울 수 있습니다.

나중에 분명해지겠지만 문제는 격자가 특정 숫자 집합으로 덮일 수 없다는 것을 보여주는 것이 가능하다는 것을 보여주는 것보다 훨씬 더 어렵다는 것입니다. Goddard는 "단지 한 가지 방법이 통하지 않는다는 것을 보여주는 것이 아니라 가능한 모든 방법이 통하지 않는다는 것을 보여주는 것입니다."라고 말했습니다.

Subercaseaux는 CMU에서 시작하여 Heule이 그와 함께 일하도록 설득한 후 15개의 숫자로 그리드를 덮는 방법을 빠르게 찾았습니다. 그들은 또한 12개의 숫자만으로 문제를 풀 가능성을 배제할 수 있었습니다. 그러나 그들의 승리감은 오래 가지 못했습니다. 그들은 단지 오랫동안 있었던 결과를 재현했을 뿐이라는 것을 깨달았습니다. 2017년까지만 해도 연구자들은 답이 13보다 작거나 15보다 크지 않다는 것을 알고 있었습니다. .

자신의 애완동물 문제를 해결하기 위해 거물 교수를 묶은 XNUMX학년 대학원생에게는 불안한 발견이었습니다. “무서웠습니다. 나는 기본적으로 이것을 깨닫지 못한 채 문제에 대해 몇 달 동안 노력해 왔으며 더 나쁜 것은 Marijn을 만들었습니다. 그것에 그의 시간을 낭비!” 수베르카소 쓴 그들의 작업을 요약하는 블로그 게시물에서.

그러나 Heule은 과거의 결과에 대한 발견이 고무적임을 발견했습니다. 그것은 다른 연구자들이 그 문제가 작업하기에 충분히 중요하다는 것을 발견했음을 보여주었고, 그에게 얻을 가치가 있는 유일한 결과는 문제를 완전히 해결하는 것임을 확인했습니다.

“우리가 이 문제에 대한 20년 간의 작업이 있었다는 것을 알게 되자 상황이 완전히 바뀌었습니다.”라고 그는 말했습니다.

저속함을 피함

수년 동안 Heule은 가능한 방대한 조합 중에서 검색하는 효율적인 방법을 찾는 데 경력을 쌓았습니다. 그의 접근 방식은 SAT 풀이(Satisfiability)라고 합니다. 여기에는 0 또는 1의 두 가지 가능한 결과를 가질 수 있는 부울 수식이라고 하는 긴 수식을 구성하는 작업이 포함됩니다. 결과가 1이면 수식이 참이고 문제가 충족됩니다.

패킹 색상 문제의 경우 수식의 각 변수는 주어진 셀이 주어진 숫자로 채워져 있는지 여부를 나타낼 수 있습니다. 컴퓨터는 공식을 만족시키기 위해 변수를 할당하는 방법을 찾습니다. 컴퓨터가 할 수 있다면 설정한 조건에서 그리드를 압축하는 것이 가능하다는 것을 알 수 있습니다.

불행하게도 패킹 색상 문제를 부울 수식으로 간단하게 인코딩하면 수백만 개의 용어로 확장될 수 있습니다. 컴퓨터 또는 여러 대의 컴퓨터가 그 안에 변수를 할당하는 모든 다양한 방법을 영원히 테스트할 수 있습니다.

Goddard는 "이 무자비한 힘을 시도하는 것은 순진하게 한다면 우주가 끝날 때까지 걸릴 것"이라고 말했습니다. "따라서 가능한 것으로 낮추려면 멋진 단순화가 필요합니다."

더욱이 포장 색상 문제에 숫자를 추가할 때마다 가능한 조합이 늘어나는 방식으로 인해 문제가 약 100배 더 어려워집니다. 즉, 병렬로 작동하는 컴퓨터 뱅크가 하루 계산에서 12개를 제외할 수 있다면 100개를 제외하려면 13일의 계산 시간이 필요합니다.

Heule과 Subercaseaux는 어떤 면에서 무차별 대입 계산 접근 방식을 저속한 것으로 간주했습니다. Subercaseaux는 "몇 가지 유망한 아이디어가 있었기 때문에 '클러스터에서 48시간 이내에 이 문제를 계산할 수 있을 때까지 접근 방식을 최적화하자'는 마음가짐을 가졌습니다."라고 말했습니다.

이를 위해 그들은 컴퓨팅 클러스터가 시도해야 하는 조합의 수를 제한하는 방법을 제시해야 했습니다.

"[그들은] 단순히 해결하는 것이 아니라 인상적인 방식으로 해결하기를 원합니다."라고 말했습니다. 알렉산더 소이퍼 콜로라도 스프링스에 있는 콜로라도 대학의

Heule과 Subercaseaux는 많은 조합이 본질적으로 동일하다는 것을 인식했습니다. XNUMX개의 서로 다른 숫자로 다이아몬드 모양의 타일을 채우려는 경우 첫 번째 숫자를 중앙 사각형의 위쪽과 오른쪽에 하나씩 또는 아래에 하나와 왼쪽에 하나씩 배치하는 것은 중요하지 않습니다. 중앙광장. 두 배치는 서로 대칭이며 정확히 같은 방식으로 다음 이동을 제한하므로 둘 다 확인할 이유가 없습니다.

Heule과 Subercaseaux는 컴퓨터가 대칭 조합을 등가로 취급하여 전체 검색 시간을 3분의 5로 줄이는 규칙을 추가했습니다. 그들은 또한 Heule이 이전 작업에서 개발한 Cube and Conquer라는 기술을 사용하여 서로 병렬로 더 많은 조합을 테스트할 수 있었습니다. 주어진 셀이 7, XNUMX 또는 XNUMX을 포함해야 한다는 것을 알고 있는 경우 문제를 분할하고 서로 다른 컴퓨터 세트에서 세 가지 가능성 각각을 동시에 테스트할 수 있습니다.

2022년 13월까지 이러한 개선 사항을 통해 Heule과 Subercaseaux는 14일 미만의 컴퓨팅 시간이 필요한 실험에서 포장 색상 문제에 대한 답으로 15을 배제할 수 있었습니다. 이것은 그들에게 XNUMX 또는 XNUMX의 두 가지 가능한 대답을 남겼습니다.

빅 플러스

14를 배제하고 문제를 해결하기 위해 Heule과 Subercaseaux는 컴퓨터 검색 속도를 높일 수 있는 추가 방법을 찾아야 했습니다.

처음에 그들은 그리드의 각 개별 셀에 변수를 할당하는 부울 공식을 작성했습니다. 그러나 2022년 XNUMX월, 그들은 셀 단위로 진행할 필요가 없다는 것을 깨달았습니다. 대신 그들은 더하기 기호 모양의 XNUMX개의 셀로 구성된 작은 영역을 고려하는 것이 더 효과적이라는 것을 발견했습니다.

그들은 여러 변수가 다음과 같은 질문을 나타내도록 부울 공식을 다시 작성했습니다. 이 더하기 모양 영역 내에 어딘가에 7이 있습니까? 컴퓨터는 7이 있을 수 있는 지역의 정확한 위치를 식별할 필요가 없었습니다. 거기에 있는지 여부를 결정하기만 하면 됩니다. 답을 찾는 데 훨씬 더 적은 계산 리소스가 필요한 질문입니다.

Heule은 "특정 위치 대신 플러스에 대해서만 이야기하는 변수를 갖는 것이 특정 셀에서 플러스에 대해 이야기하는 것보다 훨씬 낫다는 것이 밝혀졌습니다."라고 말했습니다.

더하기 검색의 효율성 덕분에 Heule과 Subercaseaux는 14년 2022월 컴퓨터 실험에서 13개를 제외하고 XNUMX개를 제외하는 데 사용한 것보다 실행 시간이 더 적게 걸렸습니다. 그들은 다음 XNUMX개월 동안 다음을 확인했습니다. 컴퓨터의 결론은 정확했습니다. 처음에 컴퓨터가 그 결론에 도달하는 데 소요한 시간과 거의 맞먹습니다.

Goddard는 "어떤 임의의 저널에 일종의 부차적인 질문으로 생성한 내용이 여러 사람이 문제를 해결하는 방법을 찾기 위해 몇 달 동안 시간을 ​​소비하게 만들었다는 사실을 생각하면 기뻤습니다."라고 말했습니다. 말했다.

Subercaseaux에게 그것은 그의 연구 경력의 첫 번째 진정한 승리였습니다. 그리고 그것이 그가 처음 수학에 대해 생각했을 때 이상화했던 유형의 발견이 아닐 수도 있지만, 결국에는 그것 자체의 지적 보상이 있다는 것을 발견했습니다.

"당신이 나에게 칠판을 주는 형식을 이해하는 것이 아닙니다. 왜 그것이 15인지 보여줄 수 있습니다."라고 그는 말했습니다. “그러나 우리는 문제의 제약이 어떻게 작용하는지 이해하게 되었고 여기에 6이 있고 저기에 7이 있는 것이 얼마나 더 나은지 알게 되었습니다. 우리는 직관적인 이해를 많이 얻었습니다.”