Daniel Spielman은 2008 년에 Yale University 동료 Gil Kalai에게 자신이 작업하고있는 컴퓨터 과학 문제에 대해 네트워크를 "상충"하는 방법에 대해 노드간에 연결이 적지 만 원래 네트워크의 필수 기능을 유지하는 방법에 대해 이야기했습니다.
.Network Scarsification에는 데이터 압축 및 효율적인 계산에 응용 프로그램이 있지만 Spielman의 특정 문제는 Kalai와 다른 것을 제안했습니다. 그것은 거의 50 년 동안 해결되지 않은 양자 물리학의 기초에 관한 유명한 Kadison-Singer 문제와 관련이있는 것처럼 보였습니다.
수십 년 동안, Kadison-Singer 문제는 수학 수학 및 공학의 12 가지 영역으로 웜을 만들었지 만 아무도 그것을 깨뜨릴 수 없었습니다. 2014 년 설문 조사 기사에서“지난 50 년 동안 가장 재능있는 수학자들의 최선의 노력을 무시했습니다.
컴퓨터 과학자로서 Spielman은 양자 역학이나 Kadison-Singer Problem의 Allied Mathematical Field (c*-andgebras)를 거의 알지 못했습니다. 그러나 주요 기관이 예루살렘 히브리 대학교 인 Kalai가 문제의 많은 동등한 공식 중 하나를 설명했을 때, Spielman은 자신이 그것을 해결하기에 완벽한 위치에있을 수 있음을 깨달았습니다. "이것은 내가 생각하는 것들의 종류의 핵심이 너무나 자연스럽게 보였다"고 그는 말했다. "나는‘그것을 증명할 수 있어야한다고 생각했다.’
대신 5 년이 걸렸습니다. 2013 년, 현재 프린스턴 대학교에서 그의 박사후 아담 마커스 (Adam Marcus)와 그의 대학원생 인 니힐 스리 바스 타바 (Nikhil Srivastava)와 함께 현재 버클리 (Berkeley) 캘리포니아 대학교 (University of California)에서 스필먼 (Spielman)이 마침내 성공했습니다. 수학 커뮤니티를 통해 단어가 빠르게 퍼졌습니다. C*-대수와 다른 많은 분야의 가장 중요한 문제 중 하나가 세 명의 외부인에 의해 해결되었다.
이 분야의 수학자들은 기쁨과 수제의 조합으로 뉴스를 인사했습니다. Casazza와 Tremain이“우리 시대의 주요 성과”라고 불렀던이 솔루션은 문제가 어떻게 해결되고 당황스러운 것처럼 보이는지에 대한 기대를 무시했습니다. 지난 2 년 동안 Kadison-Singer 문제의 전문가들은 증거의 아이디어를 동화시키기 위해 열심히 노력해야했습니다. Spielman, Marcus 및 Srivastava는“우리 중 누구도 들어 본 적이없는이 문제에 많은 도구를 가져 왔습니다. "우리 중 많은 사람들 이이 문제를 좋아했고 그것이 해결되는 것을보기 위해 죽어 가고 있었고, 우리는 그들이 어떻게 해결했는지 이해하는 데 많은 어려움을 겪었습니다."
.로스 앤젤레스 캘리포니아 대학교의 테렌스 타오 (Terence Tao)는“이러한 방법이 왜이 문제를 일으킨 이유에 대해 깊은 직관을 가진 사람들은 이러한 발전을 따르고있는 테렌스 타오 (Terence Tao)는 말했다. 수학자들은 이러한 이질적인 캠프를 연합시키기 위해 여러 워크샵을 개최했지만, 그 증거는 소화하는 데 몇 년이 더 걸릴 수 있다고 Tao는 말했다. "우리는 아직이 마법 도구의 설명서가 없습니다."
그러나 컴퓨터 과학자들은 새로운 기술을 빠르게 활용했습니다. 예를 들어, 작년에 두 명의 연구원 이이 도구를 유명한 여행 판매원 문제를 이해하는 데 큰 도약을 전진시켰다. Kadison-Singer 문제와 관련된 분야에서 일하는 Princeton의 수학자 인 Assaf Naor는 더 많은 발전이있을 것이라고 말했다. "이것은 더 많은 응용 프로그램을 가지고 있지 않기에는 너무 심오합니다."
일반적인 문제
1959 년에 제기 한 Richard Kadison과 Isadore 가수에 대한 질문은 특수 하위 시스템에 해당 상태에 대한 정보가 완료되면 양자 시스템의“상태”에 대해 얼마나 많이 배울 수 있는지 묻습니다. 전설적인 물리학 자 폴 디락 (Paul Dirac)의 비공식적 인 의견에 영감을 얻은 그들의 질문은 베르너 하이젠 베르크의 불확실성 원리를 기반으로한다. 이것은 입자의 위치와 모멘텀과 같은 특정 속성 쌍이 동시에 임의 정밀도로 측정 될 수 없다고 말한다.
.Kadison과 Singer는 동시에 동시에 측정 할 수있는 많은 다른 속성 (또는“관찰 가능”)을 포함하는 하위 시스템에 대해 궁금해했습니다. 그러한 서브 시스템의 상태에 대한 완전한 지식이 있다면, 그들은 전체 시스템의 상태를 추론 할 수 있습니까?
당신이 측정하는 시스템이 연속 선을 따라 움직일 수있는 입자 인 경우, Kadison과 Singer는 대답이 아니오라는 것을 보여주었습니다. 동시에 측정 할 수있는 관측 가능성의 관점에서 동일하게 보이는 많은 다른 양자 상태가있을 수 있습니다. Kadison은 이메일로 전자 메일로 썼다.“이것은 많은 다른 입자들이 동시에 동시에 동시에 같은 위치를 갖는 것처럼 보인다.
Kadison과 Singer의 결과는 입자가 생기는 공간이 연속적인 선이 아니라는 경우 어떤 일이 일어날 지 말하지 않았지만, Kadison이 말한 것처럼 공간이 "세분화 된"경우 일부는 선의 쾌활한 버전입니다. 이것은 Kadison-Singer 문제로 알려진 질문입니다.
Kadison과 Singer는 지속적인 환경에서의 작업을 바탕 으로이 새로운 설정에서 답변은 다시 평행 우주가 있다는 것입니다. 그러나 그들은 장의 본능이 잘못 되었기 때문에 그들의 추측을 추측으로 말하지 않았다. Kadison은“조심스럽게 기뻐요.
카디슨과 가수 - 현재 펜실베이니아 대학교 (University of Pennsylvania)와 매사추세츠 (Massachusetts Institute of Technology) (명예)는 각각 양자 역학의 철학적 기초에 대한 관심이 르네상스에 들어갔을 때 의문을 제기했다. 일부 물리학 자들은 징계에 대한“닥치고 계산”접근법을 홍보했지만, 다른 수학적으로 더 기울어 진 수학적으로 기울어 진 수학적으로 기울어 진 물리학 자들은 카디슨-싱어 문제에 대해 쫓겨 났으며, 이들은 C*-대수에 대한 질문으로 이해되었다.
C*-대수는 Casazza의 말에서“수학에 존재하는 가장 추상적 인 말도 안되는 말도 안되는 말도 안됩니다. "이 지역 외부의 어느 누구도 그것에 대해 많이 알지 못합니다." Kadison-Singer Problem의 처음 20 년 동안, 그것은이 뚫을 수없는 영역에 남아있었습니다.
그 후 1979 년, 현재 펜실베니아 주립 대학의 명예 교수 인 조엘 앤더슨 (Joel Anderson)은 매트릭스가 더 간단한 덩어리로 분류 될 수있는시기에 대한 쉽게 언급 된 질문과 동등하다는 것을 증명함으로써 문제를 대중화했습니다. 행렬은 선형 대수의 핵심 물체로, 선, 평면 및 고차원 공간으로 행동을 포착 할 수있는 수학 현상을 연구하는 데 사용됩니다. 갑자기 Kadison-Singer 문제는 어디에나있었습니다. 그 후 수십 년 동안, 그것은 한 분야에서 중요한 문제로 나타났습니다.
이러한 다른 분야들 사이에 상호 작용을하는 경향이 있었기 때문에 Casazza가 자신의 신호 처리 영역에서 가장 중요한 문제와 동등하다는 것을 알 때까지 Kadison-Singer 문제가 얼마나 유비쿼터스가 된지는 아무도 깨닫지 못했습니다. 문제는 신호 처리가 더 작고 간단한 부품으로 분해 될 수 있는지에 관한 것입니다. Casazza는 Kadison-Singer 문제에 뛰어 들었고 2005 년 Tremain과 두 공동 저자는 수학 및 공학 분야에서 가장 큰 미해결 문제와 동등하다는 것을 보여주는 논문을 썼습니다. 저자들이 보여준 이러한 문제 중 하나에 대한 해결책은 모두를 해결할 것이라고 밝혔다.
그들이 쓴 많은 동등한 공식 중 하나는 몇 년 전에 세인트 루이스의 워싱턴 대학교 Nik Weaver에 의해 고안되었습니다. Weaver의 버전은 문제를 벡터 모음을 원래 컬렉션과 거의 동일한 방향 세트로 포인트하는 두 그룹으로 벡터 모음을 나눌 수 있는지에 대한 자연스러운 질문으로 문제를 증류했습니다. Weaver는 Kadison-Singer 질문의 중심에서“핵심 조합 문제를 야기하는 아름다운 문제”라고 말했다.
그래서 Weaver는 Casazza의 설문 조사에서 언급 한 것 외에도 그의 접근 방식에 대한 회의론을 표현한 다른 논문을 제외하고는 놀랐습니다. 그의 공식은 라디오 침묵과 만나는 것처럼 보였습니다. 그는 아무도 자신의 논문을 눈치 채지 못했다고 생각했지만 실제로는 논문을 해결하기 위해 올바른 사람들의 관심을 끌었습니다.
전기 특성
Spielman은 2008 년 Weaver의 추측에 대해 알게되었을 때 그것이 그의 종류의 문제라는 것을 알았습니다. 네트워크와 벡터 컬렉션 사이를 전환하는 자연스러운 방법이 있으며, Spielman은 이전 몇 년 동안 네트워크를 물리적 대상으로 볼 수 있도록 강력한 새로운 접근 방식을 구축했습니다. 예를 들어 네트워크가 전기 회로로 생각되는 경우, 대체 경로를 찾는 대신 주어진 가장자리를 통해 실행되는 전류의 양은 네트워크에서 그 Edge의 중요성을 측정하는 자연스러운 방법을 제공합니다.
.Spielman은 Kalai가 Kadison-Singer 문제의 다른 형태로 그를 소개 한 후 Weaver의 추측을 발견했으며 네트워크의 단순한 질문과 거의 동일하다는 것을 깨달았습니다. 네트워크의 가장자리를 두 가지 범주로 나눌 수있는 경우 (예를 들어, 빨간색 및 청색 네트워크가 전체 네트워크와 유사한 전기 특성을 가지게됩니다.
이 작업을 항상 할 수있는 것은 아닙니다. 예를 들어, 원래 네트워크가 단일 모서리로 서로 연결되는 고도로 연결된 두 개의 클러스터로 구성되면 해당 에지는 네트워크에서 중요하지 않습니다. 따라서 그 임계 에지가 빨간색으로 표시되면 파란색 네트워크는 전체 네트워크와 유사한 전기적 특성을 가질 수 없습니다. 실제로 파란색 네트워크는 연결되지 않습니다.
위버의 문제는 이것이 네트워크를 유사하지만 작은 네트워크로 나누는 데 유일한 유형의 장애물인지 묻습니다. 다시 말해, 네트워크에서 돌아 다닐 수있는 충분한 방법이 있다면 (개별 모서리가 너무 중요하지 않은 경우 - 네트워크를 비슷한 전기적 특성을 가진 두 개의 서브 네트워크로 분해 할 수 있습니까?
Spielman, Marcus 및 Srivastava는 그 대답이 그렇다고 의심했으며, 그들의 직관은 이전의 네트워크 스파이즈 화에 대한 그들의 이전 작업에서 비롯된 것이 아닙니다. 또한 반음을 찾지 않고 수백만 건의 시뮬레이션을 실행했습니다. 마커스는“우리의 많은 것들이 실험에 의해 주도되었습니다. “20 년 전, 같은 방에 앉아있는 우리 셋은이 문제를 해결하지 못했을 것입니다.”
.시뮬레이션은 문제가 한 번의 걸림돌이 올라 갔음에도 불구하고 그들이 올바른 길을 가고 있다고 확신했습니다. 그리고 그들은 계속 발전을 계속하고 있으며, 그들을 붙잡을만큼 충분히 발전했습니다. 마커스의 박사후 친교 가이 문제를 해결하기 위해 팀의 4 년째 말에 만료되었을 때, 그는 아카데미아를 일시적으로 떠나 뉴 헤이븐을 떠나기보다는 선명하게 현지 스타트 업에 합류하기로 결정했습니다. "나는 일주일에 4 일 동안 회사에서 일한 다음 일주일에 한 번 예일에 갈 것"이라고 그는 말했다.
네트워크의 전기 속성은 네트워크의 "특징적인 다항식"이라는 특수 방정식으로 지배됩니다. 트리오가 이러한 다항식에 대한 컴퓨터 실험을 수행함에 따라, 그들은 방정식에 숨겨진 구조가있는 것처럼 보였다. 그들의 솔루션은 항상 실수였으며 (복소수와 반대로) 놀랍게도 이러한 다항식을 함께 추가하면 항상 동일한 속성을 가진 새로운 다항식을 초래하는 것처럼 보였다. 마커스는“이 다항식들은 우리가 그들에게 신용을 준 것보다 더 많은 일을하고있었습니다. "우리는 그것들을 지식을 전달하는 방법으로 사용했지만 실제로 다항식은 지식 자체를 포함하는 것처럼 보였습니다."
.연구원들은이 기본 구조를 포착하기 위해 소위“인터레이스 된 다항식”으로 작업하는 새로운 기술을 개발했으며, 마침내 2013 년 6 월 17 일, 마커스는 10 년 전 워싱턴 대학의 학부 고문 인 Weaver에게 이메일을 보냈습니다. 마커스는“나는 당신이 나를 기억하기를 바랍니다. "내가 쓰고있는 이유는 우리가… 우리가 당신의 추측을 해결했다고 생각하기 때문입니다 (당신이 보여준 것은 Kadison-Singer와 동일했습니다)." 며칠 안에 팀의 성취에 대한 소식이 블로그에 전파되었습니다.
Naor는 그 이후 철저한 증거는 매우 독창적이라고 말했다. "내가 좋아하는 것은이 신선도의 느낌 일뿐입니다." "그래서 우리는 열린 문제를 해결하고자하는 이유입니다. 누군가가 이전과는 다른 솔루션을 만들 때 드문 사건으로 인해 우리의 관점이 완전히 바뀌 었습니다."
.컴퓨터 과학자들은 이미이 새로운 관점을“비대칭”여행 세일즈맨 문제에 적용했습니다. 여행 판매원 문제에서, 세일즈맨은 여행하는 총 거리를 최소화하기 위해 일련의 도시를 여행해야합니다. 비대칭 버전에는 A에서 B까지의 거리가 B에서 A까지의 거리가 다른 상황 (예 :경로에 일방 통행 거리가 포함 된 경우)이 포함됩니다.
비대칭 문제에 대한 대략적인 솔루션을 찾기위한 가장 잘 알려진 알고리즘은 1970 년으로 거슬러 올라가지 만 근사치가 얼마나 좋은지는 아무도 몰랐습니다. 이제 시애틀에있는 워싱턴 대학교의 캘리포니아 대학교, 버클리 대학교 (University of California, Berkeley)의 Nima Anari, Kadison-Singer Problem의 증거의 아이디어를 사용 하여이 알고리즘은 사람들이 실현 한 것보다 기하 급수적으로 더 잘 수행된다는 것을 보여주었습니다. 새로운 결과는“주요한 주요 진전”이라고 Naor는 말했다
Kadison-Singer 문제의 증거는 수십 개의 화신의 모든 구성이 원칙적으로 수행 될 수 있음을 의미합니다. 양자 지식은 전체 양자 시스템으로 확장 될 수 있으며, 네트워크는 전기적으로 유사한 시스템으로 분해 될 수 있으며, 매트릭스는 더 간단한 청크로 나눌 수 있습니다. 증거는 양자 물리학자가하는 일이 바뀌지는 않지만 신호를 디지털화하는 데 사용되는 벡터의 컬렉션이 더 빨리 처리 될 수있는 작은 프레임으로 분해 될 수 있음을 의미하기 때문에 신호 처리에 응용 프로그램을 가질 수 있습니다. 이 정리는“일부 중요한 엔지니어링 문제에 영향을 줄 수있는 잠재력이 있습니다.”라고 Casazza는 말했습니다.
그러나 원리와 실천 사이에는 큰 걸프가 있습니다. 증거는 이러한 다양한 구성이 존재한다는 것을 입증하지만,이를 수행하는 방법은 말하지 않습니다. 현재 Casazza는“유용한 알고리즘을 증명에서 빼낼 가능성이 없습니다”라고 말합니다. 그러나 이제 수학자들은이 문제가 긍정적 인 답을 가지고 있다는 것을 알고 있기 때문에, 그는 자신의 분야의 수학자들이 실제로 이해할 수 있다는 증거는 말할 것도없이 건설적인 증거가 다가올 것이라고 희망합니다. "우리 모두는 그것이 부정적인 대답을 가지고 있다고 완전히 확신했기 때문에 실제로 우리 중 누구도 그것을 증명하려고 노력하지 않았습니다."
Kadison-Singer 문제가 두드러진 분야의 수학자들은 세 명의 외부인이 들어 와서“그들의”중심 문제를 해결했다는 사실에 대해 겁을 질 수 있지만, 실제로 일어난 일은 아니라고 Marcus는 말했다. "우리가 그러한 문제를 해결하려고 할 수있는 유일한 이유는 그 분야의 사람들이 이미 일어나고있는 모든 경도를 이미 제거했기 때문입니다." “한 조각이 남았고 그 작품은 해결해야 할 기술이있는 문제가 아니 었습니다. 이 문제가 50 년 동안 지속 된 이유는 실제로 두 부분이 어려웠 기 때문이라고 생각합니다.”
.5 년 동안 그는 Kadison-Singer 문제를 해결하는 데 소비했다고 Marcus는 다음과 같이 말했습니다. 그는 Srivastava와 Spielman이 그것을 해결할 수 있었다는 사실은“내가 수학의 미래가되기를 희망하는 것에 대해 무언가를 말할 수있다”고 말했다. 수학자들이 분야에서 아이디어를 수입 할 때,“이것은 정말 흥미로운 지식이 발생한다고 생각할 때입니다.”
