컴퓨터 과학자들이 주요 알고리즘 목표에 한 걸음 더 다가서다 | 콴타 매거진

누군가 두 개체가 동일한지 확인하도록 요청하는 경우 사소한 요청처럼 보일 수 있습니다. 대부분의 일상적인 경우에 정확한 판단을 내리려면 한 눈에 보는 것만으로도 충분합니다.

그러나 컴퓨터 과학에서는 훨씬 더 복잡한 질문입니다. 사실, 그것은 컴퓨터가 할 수 있는 것의 미해결 핵심을 꿰뚫는 것입니다. 개체가 무엇인지, 동일성을 어떻게 정의하는지에 따라 컴퓨터가 질문에 신속하게 답할 수 있는지 또는 느리고 힘든 접근 방식이 본질적으로 관리할 수 있는 최선인지는 여전히 알 수 없습니다.

지난 XNUMX년 동안 컴퓨터가 그것보다 적어도 조금 더 잘할 수 있음을 보여주는 몇 가지 중요한 결과가 있었습니다. 중 하나 가장 큰 최근 결과 컴퓨터 과학에서 두 개의 그래프가 동일한 때를 결정하는 더 빠른 알고리즘이었습니다. 2015년 작품, 라슬로 바바이 시카고 대학의 한 가지 중요한 계산 속도 장벽을 허물었지만 다른 것에는 미치지 못했습니다.

지금, 에 의해 논문 샤오루이 선 일리노이 대학의 시카고 대학은 그룹 동형사상 문제라는 관련 질문에 대한 새롭고 빠른 알고리즘을 제시했습니다. 이 문제는 그룹이라고 하는 두 개의 수학적 개체가 동일한지 아는 것과 관련이 있습니다. 작품, 온라인 게시 지난 XNUMX월, 개체 비교와 관련된 기본 계산 복잡성을 명확히 하기 위한 작은 단계입니다.

Sun의 작업은 그룹 동형사상 문제 중 가장 해결하기 어려운 사례로 간주되는 그룹의 특정 클래스에 대한 오랜 속도 제한을 깨뜨렸습니다. 알고리즘이 이러한 종류의 그룹을 빠르게 비교할 수 있다면 모든 유형의 그룹을 빠르게 비교할 수 있기를 바랍니다.

"우리는 그런 정리를 모르지만 그런 정리가 사실이어야 한다고 믿을 만한 이유가 있습니다."라고 말했습니다. 조시 그로초우 University Colorado, Boulder.

비교 비교

두 가지가 정확한 방식으로 동일한지 여부를 확인하려면 먼저 "동일한"을 정의해야 합니다. 두 개의 숫자 문자열은 단순히 동일한 숫자만 포함하거나 동일한 순서로 동일한 숫자를 포함해야 하는 경우 동일한 것으로 간주될 수 있습니다.

Isomorphism은 수학에서 많이 나오는 특정한 종류의 동일성입니다. 두 객체가 서로 동형적이라는 것은 대략적으로 동일한 요소를 포함하고 해당 요소가 서로 동일한 관계에 있음을 의미합니다.

그래프 — 모서리(선)로 연결된 정점(점) 모음 — 동형이 어떻게 생겼는지 볼 수 있는 접근 가능하고 시각적인 방법을 제공합니다. 한 그래프의 꼭짓점을 다른 그래프의 꼭짓점과 일치시킬 수 있는 경우 두 그래프는 동형입니다. 즉, 첫 번째 그래프에서 가장자리로 연결된 꼭짓점은 두 번째 그래프에서 가장자리로 연결됩니다. 동형 그래프는 표면에서 다르게 보일 수 있지만 기본 구조를 공유합니다.

그룹은 그래프보다 더 추상적이지만 여전히 동형사상으로 비교할 수 있습니다. 그룹은 결과도 컬렉션에 포함되도록 일부 작업에 따라 서로 결합할 수 있는 숫자와 같은 요소의 컬렉션입니다. 예를 들어, 요소가 정수(모든 양수 및 음수 정수에 XNUMX을 더한 것)이고 연산이 덧셈인 그룹을 가질 수 있습니다. 임의의 두 정수를 더하면 결과는 항상 다른 정수입니다.

두 그룹은 한 그룹의 각 요소를 다른 그룹의 요소와 쌍을 이루어 첫 번째 그룹의 두 요소에 대한 연산 결과가 두 번째 그룹에 있는 해당 요소의 등가 값에 대한 연산 결과와 일치하는 경우 동형입니다. 그룹.

다음은 각각 두 개의 요소가 있고 서로 동형인 두 그룹의 간단한 예입니다. 첫 번째 그룹은 숫자 0과 1로 구성되고 두 번째 그룹은 문자로 구성됩니다. a 및 b. 두 그룹 모두 특정 방식으로 그룹의 요소를 결합하기 위한 작업을 포함하며 결과는 아래 표에 나와 있습니다.

0이 다음과 쌍을 이루기 때문에 그룹은 동형입니다. a, 1쌍 b, 요소를 결합하여 생성되는 구조적 관계는 두 그룹에서 동일합니다.

"우리는 두 그룹이 기본적으로 동등하다면 동형이라고 말합니다."라고 Sun은 말했습니다.

불균형한 진행

Isomorphism은 그래프와 그룹이 광범위하게 사용되는 수학에서 중요한 개념입니다. 수학자들이 피상적인 차이점을 지나서 관련 개체가 실제로 동일할 수 있는 방식에 집중할 수 있기 때문입니다. 그러나 그것은 컴퓨터 과학에서도 기본입니다. 연구자들은 두 객체가 동형인지 여부를 결정하는 알고리즘을 찾을 뿐만 아니라 해당 알고리즘이 얼마나 빨리 실행될 수 있는지도 측정합니다.

그 측정은 까다로울 수 있습니다. 알고리즘의 속도는 작업 중인 개체의 크기에 따라 런타임이 어떻게 변경되는지에 따라 달라집니다. 예를 들어 두 쌍의 그룹이 있다고 가정합니다. 한 쌍의 각 그룹에는 10개의 요소가 포함됩니다. 다른 그룹에는 각 그룹에 XNUMX개의 요소가 포함되어 있습니다.

더 많은 요소가 있는 그룹이 동형인지 여부를 결정하는 데 알고리즘이 더 많은 시간이 걸릴 것으로 예상할 수 있습니다. 하지만 얼마나 더 시간이? 시간이 두 배로 걸리나요? 5² 더 길게? 2⁵ 더 길게? 이러한 질문은 알고리즘 속도의 중요한 광범위한 분류에 해당합니다. 선형 시간(이 경우 시간이 두 배 더 걸린다는 의미), 다항식 시간(5² 이상) 및 기하급수적 시간(2⁵ 더 길게).

컴퓨터 과학자들은 대부분의 컴퓨팅 질문이 어떤 속도 범주에 속하는지 알고 있지만 전부는 아닙니다.

"대부분은 가장 쉽거나 가장 어려운 [종류의 질문]이지만 아직 알려지지 않은 몇 가지 예외가 있습니다."라고 Sun은 말했습니다. 그래프와 그룹 동형은 이러한 예외에 속하며, 이것이 연구에 매우 매력적인 이유입니다.

1970s에서, 로버트 타잔 of Princeton University는 두 그룹이 $latex n^{{(log,n)}}$의 런타임으로 동형인지 여부를 결정할 수 있는 알고리즘이 있음을 깨달았습니다. 여기서 n 각 그룹의 요소 수입니다. 이를 준다항식 시간 알고리즘이라고 하며 런타임 계층 구조에서 지수 시간(2ⁿ) 그러나 다항식 시간(n²). 이것은 Babai의 그래프 동형사상 알고리즘과 거의 같은 속도이며, 거의 50년이 지난 후에도 여전히 그룹에 대해 할 수 있는 최선입니다.

Sun은 "대략 반세기 동안 진전이 없었다는 의미"라고 말했습니다.

Tarjan의 결과 당시에는 그룹 동형사상 문제가 그래프 버전보다 더 광범위하게 연구되었습니다. 부분적으로는 그래프 동형이 흥미진진한 혁신에 박차를 가한 반면 그룹 동형은 정체되었기 때문입니다.

"우리의 모든 도구는 몇 년 동안 정말 느렸고 [그룹의] 대수학에 대해 우리가 알고 있는 것을 활용하기가 어려웠습니다."라고 말했습니다. 제임스 윌슨 콜로라도 주립 대학의.

그러나 진행 중인 이러한 불일치에도 불구하고 두 문제는 이름의 유사성보다 더 깊은 연관성이 있습니다. 그룹 동형 문제(적어도 이 공식에서는)가 그래프 동형 문제로 축소됩니다. 이는 그래프 문제를 풀 수 있는 모든 알고리즘이 비슷한 시간 내에 그룹 문제도 풀 수 있음을 의미합니다. 그 반대는 사실이 아닙니다. 그룹의 진행 상황이 그래프의 진행 상황을 의미하지 않습니다. 그러나 그룹 문제에 대한 발전의 부족은 그래프 문제에서 상응하는 이득을 추구하는 수학자들에게 부담이 되었습니다. 밀접하게 연관되어 있고 더 쉬워 보이는 일을 먼저 성취할 수 없다면 어떻게 더 어려운 일을 성취할 수 있겠습니까?

"즉," Sun은 "그래프 동형을 더욱 개선하기 위해 그룹 동형이 큰 병목 현상입니다."라고 말했습니다.

변형된 문제

그룹 동형사상에 대해 그랬던 것처럼 문제에 대한 진행이 지연되면 일반적으로 해결하기 위해 발명이 필요합니다. Grochow는 "큰 진전이 있을 때 그것은 새로운 아이디어가 있다는 표시가 되어야 합니다."라고 말했습니다.

Sun의 작업에는 중요한 유형의 그룹을 대상으로 하고 해당 그룹을 비교하기 위해 여러 조각으로 나누는 영리한 방법을 찾는 것과 관련된 몇 가지 아이디어가 포함되어 있습니다.

Sun의 알고리즘이 작동하는 그룹은 다음과 같습니다. p-클래스 2 그룹과 지수 p. 두 요소의 곱이 다른 요소이고 곱하는 순서에 관계없이 곱이 동일하게 유지되는 그룹과 유사합니다. 그러나 정말로 중요한 것은 전체 그룹 동형사상 문제에 대해 그들이 무엇을 나타내는가입니다. 이러한 그룹은 구조가 매우 단순하므로 비교하기 쉬워야 합니다. 그러나 이러한 단순성에도 불구하고 연구원들은 알고리즘 속도를 높이는 방법을 찾지 못했습니다. 그들이 할 수 있을 때까지 그룹 동형사상에 대한 일반적인 질문을 개선하는 것은 가망이 없다고 느꼈습니다.

Sun은 설정을 그룹에서 선형 대수학의 기초 객체 역할을 하는 숫자 배열인 행렬로 전환하는 것으로 시작했습니다. 이것은 그룹 동형사상 질문의 이 버전을 행렬에 대한 완벽하게 유사한 문제로 변환하는 Baer 대응이라고 하는 1930년대의 정리로 인해 가능했습니다. 특히 Sun은 특별한 속성을 가진 행렬 모음인 행렬 공간을 사용하여 작업했습니다. 공간에 있는 두 행렬의 (선형) 조합은 공간의 다른 행렬과 같습니다.

즉, 이러한 공간은 그룹과 매우 유사하게 구성됩니다. 따라서 두 그룹이 동형인 경우를 이해하려고 시도하는 대신 Sun은 두 개의 행렬 공간이 등축인 경우(그룹의 동형에 해당하는 행렬 공간의 동형 개념)를 이해하려고 할 수 있습니다.

Sun은 이 접근 방식을 채택한 최초의 연구원은 아니었지만 매트릭스 공간을 두 조각으로 분할하는 추가 단계를 처음으로 도입했습니다. 한 조각은 모든 행렬이 단순한 공간의 핵심입니다. 다른 조각은 모든 매트릭스가 특히 복잡한 코어를 둘러싼 공간입니다. 이 이동은 전체 요소 중 일부만 포함하는 하위 그룹으로 그룹을 분할하는 것과 같습니다.

그런 다음 Sun은 이러한 각 부분에 서로 다른 알고리즘 방법을 적용했습니다. 코어는 단순한 구조를 가지고 있기 때문에 구조의 특성화를 사용하여 보다 체계적으로 표현했습니다. 외부 레이어는 더 복잡하므로 다른 레이어와 비교할 수 있는 분명히 빠른 방법이 없습니다. 대신 Sun의 방법은 하나의 외부 레이어를 다른 레이어에 매핑하는 가능한 대부분의 방법을 배제하기 위해 개별화 및 개선이라는 접근 방식을 취한 다음 컴퓨터를 사용하여 동형 일치가 존재하는지 여부를 결정하기 위해 남아 있는 모든 가능한 방법을 통해 작업합니다.

이 방법은 스도쿠 퍼즐을 푸는 방법과 정신이 비슷합니다. 잠재적인 값이 이미 알고 있는 것(행렬 공간의 핵심)에 의해 제한되는 일부 사각형이 있으므로 빠르게 채울 수 있습니다. 그런 다음 제약 조건이 적지만 가능한 모든 값을 시도하여 알아낼 수 있는 다른 레이어(외부 레이어)가 있습니다. 이러한 종류의 사각형이 너무 많지 않은 한 여전히 퍼즐을 풀 수 있습니다. 합리적인 시간.

윌슨은 "제약할 수 있다고 빨리 알 수 있는 모든 것을 채우고 이제 다시 들어가서 누락된 상자에 대해 마음을 다해 노력할 것"이라고 말했습니다. "범위를 좁혔다면 이제 기어를 바꾸고 컴퓨터를 사용하여 올바른 값을 검색할 적기입니다."

Sun의 돌파구는 다음에 해당하는 매트릭스 공간에 대해 이러한 분할을 수행하는 것이 항상 가능하다는 것을 보여주었습니다. p-클래스 2 그룹과 지수 p. 그런 다음 그는 그러한 분할 후 알고리즘 기술의 조합을 통해 $latex n^{{(log,n)}^{5/6}}$ 시간에서 두 공간이 동형인지 여부를 결정할 수 있으며, Tarjan의 $latex n^{{(log,n)}}$ 방법보다 약간 낮습니다. (또한 두 알고리즘 모두 런타임에 큰 영향을 미치지 않는 상수 용어를 포함하며 명확성을 위해 생략했습니다.)

결과는 어떤 속도 범주 그룹 동형이 속하는지 결정하지 않습니다. 여전히 지수와 다항 시간 사이의 어딘가에 있습니다. 그러나 Sun은 그것을 다항식 측면에 약간 더 가깝게 만들었고 그 이상이 가능해야 한다고 믿을 만한 이유가 있습니다. 결국 그의 작업은 컴퓨터 과학자에게 가장 어려운 종류의 그룹에 대한 더 빠른 그룹 동형 알고리즘을 제공하여 모든 종류의 그룹에 대해 유사한 속도 향상이 도달할 수 있는 가능성을 높입니다.

"해결할 수 있다면 p-그룹, 아마 당신은 모든 것을 해결할 수 있습니다.”라고 Grochow는 말했습니다. "아마도."