수학 및 컴퓨터 과학의 일부 계산 문제가 어려울 수 있다는 생각은 놀라운 일이 아닙니다. 사실, 수학적으로 풀 수 없는 것으로 간주되는 모든 종류의 문제가 있습니다. 이 범주 아래에는 잘 이해되지 않는 몇 가지 “더 쉬운” 문제가 있으며 불가능할 수도 있습니다.

MIT 슬론 경영대학원 및 데이터, 시스템 및 사회 연구소의 운영 연구 교수인 David Jamarnik은 덜 연구된 문제의 후자 범주에 관심을 집중합니다. 무작위의– 자연계의 필수 기능. 그와 그의 동료들은 이러한 문제를 분석하기 위한 강력한 도구인 OGP(겹침 간격 속성)를 개발했습니다. Gamarnik은 최근 연구 논문에서 새로운 방법론을 설명했습니다. 국립과학원 회보.

피엔피

50년 전, 이론적 컴퓨터 과학에서 가장 유명한 문제가 공식화되었습니다. P ≠ NP는 답을 비교적 빠르게 확인할 수 있지만 가장 빠른 컴퓨터에서 작업하더라도 해결하는 데 엄청나게 오랜 시간이 걸리는 방대한 데이터 세트와 관련된 문제가 있는지 묻습니다.

P ≠ NP 추측은 아직 입증되지 않았지만 대부분의 컴퓨터 과학자들은 예를 들어 여행하는 세일즈맨 문제를 비롯한 많은 친숙한 문제가 이 불가능할 정도로 어려운 범주에 속한다고 믿습니다. 판매자 예제의 문제는 N개의 다른 도시를 통해 거리 또는 시간 측면에서 최단 경로를 찾는 것입니다. N = 4일 때 작업을 쉽게 관리할 수 있습니다. 고려할 수 있는 경로가 6개뿐이기 때문입니다. 그러나 30개 도시에는 10개 이상의³⁰ 가능한 방법으로 숫자가 기하 급수적으로 증가합니다. 가장 큰 어려움은 파일 디자인에 있습니다 연산 모든 경우에 문제를 신속하게 해결합니다. N의 모든 정수 값에 대해 컴퓨터 과학자는 계산 복잡성 이론을 기반으로 P ≠ NP임을 확인하는 그러한 알고리즘이 없다고 확신합니다.

이러한 난해한 문제의 다른 많은 예가 있습니다. 예를 들어, 수천 개의 행과 수천 개의 열이 있는 거대한 숫자 테이블이 있다고 가정합니다. 가능한 모든 조합 중에서 100개의 항목이 달성 가능한 가장 높은 합을 갖도록 10개의 행과 10개의 열의 정확한 배열을 찾을 수 있습니까? Jamarnik은 “최적화 작업이라고 부릅니다. 왜냐하면 여러분은 항상 가장 큰 것 또는 가장 좋은 것, 즉 가장 큰 숫자의 합, 도시를 통과하는 최상의 경로 등을 찾으려고 하기 때문입니다.”라고 Jamarnik은 말합니다.

컴퓨터 과학자들은 모든 경우에 여행하는 세일즈맨 사가만큼 효율적으로 문제를 해결할 수 있는 빠른 알고리즘을 만들 수 없다는 것을 오랫동안 깨달았습니다. Jamarnik은 “이러한 일은 충분히 이해할 수 있는 이유로 불가능할 것 같습니다.”라고 말합니다. “하지만 실생활에서 자연은 적대적인 관점에서 문제를 일으키지 않습니다. 잘 선택되고 생각할 수 있는 가장 어려운 문제로 당신을 좌절시키려 하지 않습니다.” 사실, 사람들은 일반적으로 더 무작위적이고 덜 관리되는 상황에서 문제에 직면하며, 이것이 Open Government Partnership이 해결하고자 하는 문제입니다.

봉우리와 계곡

열린 정부 파트너십이 무엇인지 이해하려면 먼저 아이디어가 어떻게 시작되었는지 확인하는 것이 도움이 될 수 있습니다. 1970년대부터 물리학자들은 특이한 자기 거동을 갖는 액체와 고체의 특성을 모두 가진 물질인 스핀 유리를 연구해 왔습니다. 스핀 글라스에 대한 연구는 물리학, 수학, 컴퓨터 과학, 재료 과학 및 기타 분야의 문제와 관련된 복잡한 시스템의 일반 이론을 발생시켰습니다. (이 연구는 조르지오 바레시가 2021년 노벨 물리학상을 수상했습니다.)

물리학자들이 직면한 한 가지 혼란스러운 문제는 다양한 방사 유리 구조의 에너지 상태, 특히 가장 낮은 에너지 구성을 예측하는 것입니다. 이 상황은 가장 높은 봉우리를 찾는 것이 목표인 계곡으로 분리된 셀 수 없이 많은 산봉우리의 “풍경”으로 묘사되기도 합니다. 이 경우 가장 높은 피크는 실제로 가장 낮은 에너지 상태를 나타냅니다(대신 이미지를 뒤집고 가장 깊은 구멍을 찾을 수 있음). 이것은 순회 판매원의 딜레마와 유사한 형태의 최적화 문제로 판명되었으며 Jamarnik은 다음과 같이 설명합니다. 건초더미에서 바늘 찾기.

물리학자들은 산을 미리 정해진 특정 높이로 자르고 그 경계선 아래의 모든 것을 무시함으로써 이 그림을 단순화하고 솔루션을 향한 단계를 밟을 수 있음을 보여주었습니다. 그런 다음 균일한 구름 층 위에 눈에 띄는 봉우리 그룹을 남깁니다. 이 봉우리의 각 지점은 원래 문제에 대한 잠재적인 솔루션을 나타냅니다.

2014년 연구 논문에서 Jamarnik과 동료들은 이전에 간과된 것을 지적했습니다. 그들은 어떤 경우에는 각 봉우리의 지름이 다른 봉우리 사이의 거리보다 훨씬 작을 것이라는 사실을 깨달았습니다. 따라서 이 광대한 풍경에서 두 점, 즉 두 가지 가능한 “해결책”을 선택해야 한다면 두 점은 매우 가깝거나(같은 봉우리에서 온 경우) 아주 멀리 떨어져 있습니다(다른 봉우리에서 가져온 경우). . 다시 말해서, 작거나 크거나 같지만 그 사이에는 아무 것도 없는 이러한 거리에 명백한 “간극”이 있을 것입니다. Jamarnik과 동료들은 이 경우 시스템이 OGP에 의해 특징지어진다고 제안했습니다.

“우리는 계산적으로 어려운 임의적 성격의 알려진 모든 문제가 이 속성의 버전을 가지고 있음을 발견했습니다.” 즉, 도식 모델에서 산의 지름은 산 사이의 거리보다 훨씬 더 작습니다. “이것은 알고리즘의 견고성에 대한 보다 정확한 측정을 제공합니다.”

알고리즘 복잡성의 비밀 풀기

OGP의 출현은 연구자들이 특정 문제를 해결하기 위해 빠른 알고리즘을 생성하는 어려움을 평가하는 데 도움이 될 수 있습니다. 그것은 이미 그들이 “수학적으로 [and] 그는 잠재적인 경쟁자로서 많은 종류의 알고리즘을 강력하게 배제했습니다.”라고 Jamarnik은 말합니다. 특히 안정적인 알고리즘(입력이 조금만 변해도 출력이 크게 변하지 않는 알고리즘)은 이러한 종류의 최적화 문제를 해결하지 못한다는 것을 배웠습니다. “이 부정적인 결과는 기존 컴퓨터뿐만 아니라 양자 컴퓨터, 특히 일부 연구자들이 동일한 최적화 문제를 해결하기를 희망했던 소위 “양자 근사 최적화 알고리즘”(QAOA)에도 적용됩니다. 이제 Jamarnik의 결과와 공동 저자의 발견에 따르면 이러한 희망은 기술적으로 어려울 수 있는 QAOA 유형 알고리즘이 성공하려면 많은 작업 계층이 필요하다는 인식으로 인해 누그러졌습니다.

“좋은 소식인지 나쁜 소식인지는 당신의 관점에 달려 있습니다.”라고 그는 말합니다. “알고리즘 복잡성의 비밀을 풀고 확률의 영역에 있는 것과 그렇지 않은 것에 대한 지식을 향상시키는 데 도움이 된다는 점에서 좋은 소식이라고 생각합니다. 이러한 문제가 다음과 같다는 점에서 나쁜 소식입니다. 자연이 만들어도, 무작위로 만들어도 어렵다.” 그는 그 소식이 별로 놀라운 일이 아니라고 덧붙였습니다. “우리 중 많은 사람들이 이것을 항상 예상했지만 이제 우리는 그 주장을 할 수 있는 훨씬 더 견고한 기반을 갖게 되었습니다.”

이것은 무작위 설정에서 이러한 최적화 문제를 해결할 수 있는 빠른 알고리즘이 없음을 증명할 수 있는 연구자에게 여전히 몇 광년을 남겨 둡니다. 그러한 증거를 갖는 것은 P NP 문제에 대한 결정적인 답을 제공할 것입니다. 그는 “만약 우리가 대부분의 시간에 작동하는 알고리즘을 가질 수 없다는 것을 증명할 수 있다면 그것은 우리가 항상 작동하는 알고리즘을 가질 수 없다는 것을 의미합니다.”라고 말합니다.

P NP 문제가 해결되기까지 시간이 얼마나 걸릴지 예측하는 것 자체가 난해한 문제인 것 같습니다. 연구자들이 상황에 대한 더 명확한 관점을 얻기 전에 넘어야 할 봉우리와 넘어야 할 계곡이 많을 것입니다.