Математик е решил 30-годишен проблем на границата между математиката и компютърните науки. Той използва иновативно, елегантно доказателство, което кара неговите колеги да се чудят на неговата простота.
Хао Хуанг, доцент по математика в университета Емори в Атланта, доказа математическа идея, наречена хипотеза на чувствителността, която в невероятно груби думи отправя искане за това колко можете да промените входа на функция, без да променяте изхода (това е нейната чувствителност).
През десетилетията, откакто математиците за първи път предложиха предположението за чувствителност (без да го доказват), теоретичните компютърни учени осъзнаха, че има огромно значение за определянето на най-ефективните начини за обработка на информация.
За доказателството на Хуанг, според други експерти в тази област, е не само това, че Хуанг го е свалил, но и елегантният и пряк начин, по който го е направил. Неговото доказателство не е било проверено официално или публикувано в нито едно математическо списание. Но скоро след като Хуан го пусна в интернет 1 юли, колегите му бързо го приеха като факт.
"Винаги, когато има съобщение по този начин", пише в блога си Университетът на Тексас в Остин теоретичен компютърен учен Скот Арънсън, "~ 99% от случаите или доказателството е грешно, или във всеки случай е твърде сложно за външни лица да го оценят. бързо. Това е един от останалите 1% от случаите. По-скоро съм убеден, че доказателството е правилно. Защо? Защото го прочетох и разбрах. Отне ми около половин час. "
Райън О'Донъл, професор по компютърни науки, който изучава теорията на числата в университета Карнеги Мелън в Питсбърг, посочи, че доказателството на Хуанг може да бъде обобщено в един туитър:
Какво всъщност доказа Хуанг?
За простота си представете 3D куб със страни, които са дълги по 1 единица. Ако поставите този куб в 3D координатна система (което означава, че има измервания в три посоки), един ъгъл ще има координатите (0,0,0), а този до него може да бъде (1,0,0), един над него може да е (0,1,0) и така нататък. Можете да вземете половината ъгли (четири ъгъла), без да имате чифт съседи: (0,0,0), (1,1,0), (1,0,1) и (0,1,1) aren ' t съседи. Можете да покажете това, като погледнете куба, но ние също го знаем, защото всички те са различни с повече от една координата.
Предполагаемостта на чувствителността е да откриете колко съседи имате, когато вземете повече от половината ъгли на кубче с по-голям размер или хиперкуб, каза математикът от Хеврейския университет Гил Калай. Можете да напишете координатите на хиперкуба като низове от 1s и 0s, където броят на размерите е дължината на низа, каза Калай пред Live Science. Например за 4D хиперкуб има 16 различни точки, което означава 16 различни низа от 1s и 0s, които са четирицифрени.
Сега изберете половин плюс 1 отделни точки на хиперкубата (за 4D хиперкуба, това означава, че изберете девет - или 8 + 1 - различни точки от общо 16).
От този по-малък набор намерете смисъла с най-много съседи - какво е това минимум брой съседи, които може да има? (Съседите се различават само с едно число. Например 1111 и 1110 са съседи, защото трябва да смените само една цифра, за да превърнете първата във втората.)
Хуанг доказа, че този ъгъл трябва да има поне толкова съседи, колкото квадратният корен от броя на цифрите - в случая квадратният корен от 4 - което е 2.
За ниски размери можете да разберете, че това е вярно само като проверите. Не е толкова трудно да проверите 16 координати на куба (или "струни") за съседи, например. Но всеки път, когато добавите измерение към куба, броят на струните се удвоява. Така проблемът става по-трудно да се провери много бързо.
Наборът от низове с дължина 30 цифри - координатите към ъглите на 30-измерен куб - има повече от 1 милиард различни низове в него, което означава, че кубът има повече от 1 милиард ъгъла. С низове, които са дълги 200 цифри, има повече от novemdecillion. Това е един милиард милиарда милиарда милиарда, или 1, последван от 60 нули.
Ето защо математиците харесват доказателства: Те показват, че нещо е вярно във всеки случай, а не само лесните.
"Ако н е равно на милион - това означава, че имаме струни с дължина 1 милион - тогава предположението е, че ако вземете 2 ^ 1,000,000-1 и добавите 1, тогава има низ, който има 1000 съседи - квадратният корен на милион, - каза Калай.
Последният голям напредък в предположението за чувствителност е през 1988 г., каза Калай, когато изследователите доказаха, че един низ трябва да има поне логаритъм на н съседи. Това е много по-малък брой; логаритъмът от 1 000 000 е точно 6. Така че доказателството на Хуанг току-що откри, че най-малко 994 други съседи са там.
Елегантно и "мистериозно" доказателство
"Много е загадъчно", каза Калай за доказателството на Хуанг. "Той използва" спектрални методи ", които са много важни методи в много области на математиката. Но той използва спектрални методи по нов начин. Все още е загадъчно, но мисля, че можем да очакваме, че този нов начин за използване на спектрални методи постепенно ще има повече приложения. "
По същество Хуанг концептуализира хиперкуба, използвайки масиви от числа в редове и колони (наречени матрици). Хуанг измисли напълно неочакван начин за манипулиране на матрица с необичайно подреждане -1 и 1, което "магически кара всичко да работи", написа Ааронсън в своя блог.
Хуанг "взе тази матрица и той я модифицира по много гениален и мистериозен начин", каза Калай. "Сякаш имате оркестър и те свирят някаква музика. След това оставяте някои от играчите, не знам, да им стоят на главата и музиката става съвсем различна - нещо подобно."
Тази различна музика се оказа ключът към доказването на хипотезата, каза Калай. Той е загадъчен, каза той, защото въпреки че математиците разбират защо методът е работил в този случай, те не разбират напълно тази нова "музика" или в какви други случаи може да е полезна или интересна.
"В продължение на 30 години нямаше напредък и тогава Хао Хуанг реши този проблем. Той намери много просто доказателство, че отговорът е квадратният корен на н", Каза Калай." Но през тези 30 години ... хората разбраха, че този въпрос е много важен в теорията за изчисленията. "
Доказателството на Хуанг е вълнуващо, защото напредва в областта на компютърните науки, каза Калай. Но също така е забележително, тъй като той въведе нов метод, а математиците все още не са сигурни какво друго може да им позволи новият метод на Хуан.
