Matematyk rozwiązał 30-letni problem na pograniczu matematyki i informatyki. Użył innowacyjnego, eleganckiego dowodu, który sprawia, że jego koledzy zachwycają się jego prostotą.
Hao Huang, adiunkt matematyki na Emory University w Atlancie, udowodnił matematyczny pomysł zwany hipotezą wrażliwości, który, w niewiarygodnie szorstkich kategoriach, twierdzi, jak bardzo możesz zmienić dane wejściowe na funkcję bez zmiany wyniku (to to jego wrażliwość).
W ciągu dziesięcioleci, odkąd matematycy po raz pierwszy zaproponowali hipotezę wrażliwości (bez jej udowodnienia), teoretyczni informatycy zdali sobie sprawę, że ma to ogromne konsekwencje dla określenia najbardziej efektywnych sposobów przetwarzania informacji.
Co jest niezwykłe w dowodzie Huanga, według innych ekspertów w tej dziedzinie, nie tylko to, że Huang go wykonał, ale także elegancki i prosty sposób, w jaki to zrobił. Jego dowód nie został oficjalnie sprawdzony ani opublikowany w żadnym czasopiśmie matematycznym. Ale wkrótce po tym, jak Huang umieścił go w Internecie 1 lipca, jego koledzy szybko zaakceptowali to jako fakt.
„Ilekroć pojawia się takie ogłoszenie”, napisał na swoim blogu teoretyczny informatyk z uniwersytetu w Austin, Scott Aaronson, „w około 99% przypadków dowód jest błędny lub w każdym razie jest zbyt skomplikowany, aby osoby z zewnątrz go oceniały szybko. To jeden z pozostałych 1% przypadków. Jestem raczej pewien, że dowód jest słuszny. Dlaczego? Ponieważ go przeczytałem i zrozumiałem. Zajęło mi to około pół godziny. ”
Ryan O'Donnell, profesor informatyki, który studiuje teorię liczb na Carnegie Mellon University w Pittsburghu, zauważył, że dowód Huanga można streścić w jednym tweecie:
Co faktycznie udowodnił Huang?
Dla uproszczenia wyobraź sobie sześcian 3D o bokach o długości 1 jednostki. Jeśli umieścisz tę kostkę w układzie współrzędnych 3D (co oznacza, że ma pomiary w trzech kierunkach), jeden narożnik będzie miał współrzędne (0,0,0), następny obok niego (1,0,0), to jeden powyżej może być (0,1,0) i tak dalej. Możesz wziąć połowę narożników (cztery narożniki), nie mając żadnej pary sąsiadów: (0,0,0), (1,1,0), (1,0,1) i (0,1,1) nie są t sąsiedzi. Możesz to pokazać, patrząc na sześcian, ale my też to wiemy, ponieważ wszystkie różnią się więcej niż jedną współrzędną.
Hipoteza wrażliwości polega na ustaleniu, ile masz sąsiadów, gdy weźmiesz więcej niż połowę narożnika sześcianu lub hipersześcianu, powiedział matematyk z Uniwersytetu Hebrajskiego Gil Kalai. Możesz napisać współrzędne hipersześcianu jako ciągi 1 i 0, gdzie liczba wymiarów to długość łańcucha, powiedział Kalai Live Science. Na przykład w przypadku hipersześcianu 4D istnieje 16 różnych punktów, co oznacza 16 różnych ciągów 1 i 0 o długości czterech cyfr.
Teraz wybierz połowę plus 1 pojedyncze punkty na hipersześcianie (w przypadku hipersześcianu 4D oznacza to wybranie 9 - lub 8 + 1 - różnych punktów z 16).
Z tego mniejszego zestawu znajdź punkt z największą liczbą sąsiadów - co to jest minimum ile sąsiadów może mieć? (Sąsiedzi różnią się tylko jedną liczbą. Na przykład 1111 i 1110 są sąsiadami, ponieważ wystarczy zamienić tylko jedną cyfrę, aby zamienić pierwszą na drugą.)
Huang udowodnił, że ten narożnik musi mieć co najmniej tyle samo sąsiadów, co pierwiastek kwadratowy z liczby cyfr - w tym przypadku pierwiastek kwadratowy z 4 - czyli 2.
W przypadku niskich wymiarów można to stwierdzić, sprawdzając. Na przykład nie jest trudno sprawdzić 16 współrzędnych na sześcianie (lub „łańcuchach”) dla sąsiadów. Ale za każdym razem, gdy dodajesz wymiar do kostki, liczba łańcuchów podwaja się. Problem staje się więc trudny do sprawdzenia bardzo szybko.
Zestaw ciągów o długości 30 cyfr - współrzędne do narożników 30-wymiarowego sześcianu - zawiera ponad 1 miliard różnych ciągów, co oznacza, że sześcian ma ponad 1 miliard narożników. W przypadku ciągów o długości 200 cyfr istnieje więcej niż miliard novem. To milion miliardów miliardów miliardów miliardów miliardów, a po 1 następuje 60 zer.
Dlatego matematycy lubią dowody: pokazują, że w każdym przypadku coś jest prawdą, nie tylko te łatwe.
"Jeśli n jest równa milionowi - oznacza to, że mamy łańcuchy o długości 1 miliona - wtedy przypuszczam, że jeśli weźmiesz 2 ^ 1 000 000-1 i dodasz 1, to jest łańcuch, który ma 1000 sąsiadów - pierwiastek kwadratowy z miliona, „Powiedział Kalai.
Kalai powiedział, że ostatni duży postęp w domysłach wrażliwości nastąpił w 1988 r., Kiedy naukowcy udowodnili, że jeden łańcuch musi mieć co najmniej logarytm n sąsiedzi To znacznie niższa liczba; logarytm 1 000 000 to tylko 6. Więc dowód Huanga odkrył, że jest tam co najmniej 994 innych sąsiadów.
Elegancki i „tajemniczy” dowód
„To bardzo tajemnicze” - powiedział Kalai o dowodzie Huanga. „Wykorzystuje„ metody spektralne ”, które są bardzo ważnymi metodami w wielu dziedzinach matematyki. Ale wykorzystuje metody spektralne w nowatorski sposób. To wciąż tajemnica, ale myślę, że możemy oczekiwać, że ten nowatorski sposób korzystania z metod spektralnych będzie stopniowo więcej aplikacji ”.
Zasadniczo Huang konceptualizował hipersześcian przy użyciu tablic liczb w wierszach i kolumnach (zwanych macierzami). Huang wymyślił zupełnie nieoczekiwany sposób manipulowania matrycą o nietypowym układzie -1 i 1, który „magicznie sprawia, że wszystko działa”, napisał Aaronson na swoim blogu.
Huang „wziął tę matrycę i zmodyfikował ją w bardzo pomysłowy i tajemniczy sposób” - powiedział Kalai. „To tak, jakbyś miał orkiestrę i grają muzykę, a potem pozwalasz niektórym graczom, nie wiem, stanąć na głowie, a muzyka staje się zupełnie inna - coś takiego”.
Kalai powiedział, że ta inna muzyka okazała się kluczem do udowodnienia przypuszczenia. To tajemnicze, powiedział, ponieważ chociaż matematycy rozumieją, dlaczego metoda zadziałała w tym przypadku, nie do końca rozumieją tę nową „muzykę” lub w jakich innych przypadkach może być przydatna lub interesująca.
„Przez 30 lat nie było postępu, a potem Hao Huang rozwiązał ten problem i znalazł bardzo prosty dowód, że odpowiedź jest pierwiastkiem kwadratowym n", Powiedział Kalai." Ale w ciągu tych 30 lat ... ludzie zdali sobie sprawę, że to pytanie jest bardzo ważne w teorii komputerów ".
Kalai powiedział, że dowód Huanga jest ekscytujący, ponieważ rozwija on dziedzinę informatyki. Jest to również godne uwagi, ponieważ wprowadziło nowatorską metodę, a matematycy wciąż nie są pewni, co jeszcze może pozwolić nowa metoda Huanga.
