Profile cover photo
Profile photo
Jerzy Michał Pawlak
777 followers
777 followers
About
Posts

Post has attachment
Ot problem etyczny. I ostrzeżenie.

W USA policja złapała seryjnego mordercę i gwałciciela, znanego jako "Golden State Killer" (ok, technicznie złapała podejrzanego, ale jest raczej pewne że to ten). Grasował on w Kalifornii w latach 1976-1986, przypisuje mu się co najmniej 12 morderstw. Problemem nie jest to że złapała, a jak. Otóż na miejscu jednego z tych morderstw zabezpieczono jakąś próbkę zawierającą DNA sprawcy (nie znam szczegółów co to dokładnie było). W tamtych czasach to sztuka badania DNA nie była jeszcze na tyle rozwinięta, żeby ją w kryminalistyce wykorzystywać, ale kilka miesięcy temu przeglądając stare nierozwiązane sprawy okazało się, że próbka jest świetnie zachowana i można ją przebadać. W kartotekach policyjnych zgodnych genów nie znaleziono, więc policja udała się do serwisu genealogicznego.

Tu słowo wyjaśnienia: w USA (w Polsce zresztą już też) można zlecić zrobienie swojego profilu DNA. Celem w założeniu jest wykrycie genetycznych skłonności do pewnych chorób, wiedząc o takowych można się jakoś zabezpieczać czy przynajmniej częściej badać. Ale, jak już się ma taki profil DNA, to można go też załadować do serwisu genealogicznego. A ten wyszuka w swojej bazie podobne, mogące należeć do bliższej i dalszej rodziny i je wyświetli. Najwyraźniej jest to w Stanach dość popularne, serwis którego użyli policjanci nazywa się GEDmatch, ale są i inne: MyHeritage, Ancestry... I mają duże miliony zarejestrowanych użytkowników. Są przykłady, że dzięki nim ktoś znalazł rodzeństwo o którym nie miał pojęcia, ktoś inny dowiedział się, że jego rodzice wcale nimi nie są... Ogólnie wydawało się że wszystko fajnie jest.

No więc jako się rzekło, policja wrzuciła dane przestępcy do GEDmatch. Ten ani jego, ani bliskich krewnych wprawdzie nie znalazł, ale znalazł trochę dalszych. Policjanci, startując z nich, zbudowali drzewa genealogiczne do nawet 6 pokoleń wstecz, szukając gdzie te drzewa się przecinają. No i znaleźli człowieka, który pasował, był w odpowiednim wieku i nawet mieszkał niedaleko miejsca popełnienia przestępstw. Dla pewności użyto jakichś wyrzuconych przez niego śmieci żeby zbadać jego DNA, a gdy się okazało zgodne, aresztowano go.

No i właśnie, teraz jest z tym problem, który te serwisy (a i prawodawca) dotąd ignorowali: czy policja może przeszukiwać bazy danych genetycznych bez zgody osób, które do nich swoje dane wrzuciły. Bo w końcu użytkownicy serwisu nie dawali zgody na wykorzystanie ich danych do czegokolwiek innego niż poszukiwanie własnych krewnych. A tu policja się wcięła. Zdania użytkowników serwisu są podzielone, jedni cieszą się że pomogli złapać przestępcę, ale inni są oburzeni. Do tego nie wiadomo, czy w tej legalistycznej Ameryce sąd czasem nie odrzuci tego dowodu, jako zdobytego nielegalnie. Bo policjant, żeby skorzystać z serwisu, musiał nakłamać: zakładając profil w serwisie podał fałszywe dane, a potem musiał odkliknąć oświadczenie, że ładuje swoje DNA, a jeżeli nie swoje, to ma zgodę właściciela.

Okazało się zresztą gdy historia ta wyszła na jaw, że to już druga stara sprawa rozwiązana w podobny sposób. Tylko pierwsza nie zdobyła rozgłosu, bo namierzony sprawca zmarł kilka lat wcześniej w więzieniu, odsiadując wyrok za inne przestępstwo.

W każdym razie pamiętajcie dzieci, ładując swoje dane w internet możecie zaszkodzić nie tylko sobie, ale i swoim krewnym. Nawet takim o których istnieniu nie macie pojęcia...
Add a comment...

Post has attachment
Nie wiem czy podziwiać, czy już się bać... Deep Mind, firma która stworzyła AlphaGo - program do gry w Go, który w ubiegłym roku pokonał wszystkich mistrzów tej gry i został najlepszym graczem w Go na planecie, poszła dalej. Ale jak można pójść dalej gdy się już pokonało ludzi w najtrudniejszej dla komputerów grze strategicznej? Okazuje się, że można.

Jak może niektórzy pamiętają, oryginalny AlphaGo działał na zasadzie nie analizy drzewa ruchów (liczba możliwości ruchu w Go jest olbrzymia, a konsekwencje ruchu mogą się okazać dopiero po kilkudziesięciu innych, więc taki algorytm jest skazany na porażkę), lecz na zasadzie oceny sytuacji na planszy przed i po wykonaniu ruchu. Aby nauczyć program oceniania sytuacji autorzy przetrenowali go najpierw na tysiącach gier rozegranych pomiędzy wysokiej klasy ludzkimi graczami, a potem pozwolili mu grać samemu ze sobą i uczyć się w ten sposób dalej. Po kilku miesiącach takiego uczenia dostali wersję, która potrafiła pokonać każdego człowieka.

I tu autorzy AlphaGo zadali sobie pytanie: a co gdyby pominąć to wstępne uczenie na "ludzkich" grach? Jak poradziłby sobie program gdyby dostał tylko reguły gry i całą strategię musiał wymyślić na nowo? Tak powstał AlphaGo Zero (od zerowej wiedzy początkowej). Wynik był niesamowity: już po 3 dniach takiego uczenia się AlphaGo Zero osiągnął poziom gry AlphaGo Lee, czyli wersji, która pokonała 4:1 legendarnego gracza Lee Sedola, a po 20 przebił najlepszą istniejącą wersję oryginalnego AlphaGo. Wychodzi, że "ludzka" wiedza o strategii była mu tylko balastem.

Ale prawdziwą przyczyną tego wpisu jest kolejny krok wykonany przez Deep Mind. Otóż postanowili spróbować uogólnić program, żeby nie był przywiązany tylko i wyłącznie do gry w Go. Program nazwany AlphaZero potrafi uczyć się także i innych gier planszowych - został uwolniony od pewnych specyficznych dla Go ograniczeń, nie zakłada już symetrii planszy jeżeli gra takowej nie wykazuje i analizuje drzewo ruchów dalej, niż tylko jeden czy dwa ruchy. I czego taki program nauczyć? Oczywiście gry w szachy! Jest to ta gra, której "skomputeryzowaniu" poświęcono chyba najwięcej wysiłku. Jak wiadomo, w szachy komputery dawno już pobiły ludzi i nikt nawet nie próbuje już organizować rozgrywek pomiędzy jednymi a drugimi. No więc AlphaZero dostał reguły gry w szachy, 24 godziny na nauczenie się metodą grania sobie samemu ze sobą (nadal jest w nazwie zero, czyli żadnej wstępnej wiedzy o strategii), po czym został wystawiony w meczu przeciwko mistrzowi świata 2016 - programowi Stockfish. Jest to program działający metodą "klasyczną", czyli brutalnego przeszukiwania drzewa możliwych ruchów, z ręcznie optymalizowanymi regułami oceny pozycji.

Efekt jest porażający. AlphaZero rozniósł konkurenta: na 100 rozegranych partii wygrał 28, a pozostałe zremisował (czyli ani razu nie przegrał). Co więcej, uczynił to grając na sporo słabszej maszynie. Wprawdzie tak bezpośrednio to te maszyny trudno porównać, bo AlphaZero, podobnie jak AlphaGo, działa na specjalizowanym sprzęcie, tzw. Tensor Processing Unit (TPU) produkcji Google. AlphaZero działał w tym meczu na maszynie mającej 4 takie TPU, podczas gdy Stockfish korzystał z klasycznej architektury na 32 CPU. Ale autorzy podają, że AlphaZero analizował około 80 tys. pozycji na sekundę, zaś Stockfish - 70 milionów. Co pokazuje, że program-samouk nie używa po prostu brutalnej siły, jego "procesy myślowe" bliższe są ludzkim.

Bardzo interesujące są pokazane w pracy wykresy z procesu uczenia się gry. Pokazują one jak komputer stopniowo "odkrywa" klasyczne otwarcia szachowe i jak po pewnym czasie "traci zainteresowanie" niektórymi z nich, wyraźnie dochodząc do wniosku, że są słabsze niż inne.

Z ciekawości: AlphaZero można oczywiście nauczyć i gry w Go. Wedy z AlphaGo Zero wygrywa 60:40 - już nie tak przekonująco, ale muszę powiedzieć że trochę to dla mnie zaskakujące. W końcu to zasadniczo ta sama koncepcja, tylko bardziej uogólniona.

W każdym razie: witamy w przyszłości. Komputery już nie potrzebują ludzi żeby się czegoś od nich nauczyć i robić to lepiej - mogą uczyć się całkiem same i wtedy robić to jeszcze lepiej.

Podłączony artykuł to całkiem fajne omówienie, a sama praca jest tutaj: https://arxiv.org/abs/1712.01815.
Add a comment...

Post has attachment
Tematem dnia jest oczywiście detekcja połączenia gwiazd neutronowych. Zgodnie ze zwyczajem panującym w LIGO, nie ma preprintów i wstępnych doniesień, oficjalna informacja o obserwacji pojawia się jednocześnie z publikacją pracy w czasopiśmie naukowym. Tak naprawdę to ten wpis powstał na podstawie dwóch prac (obie open access): pierwsza tutaj https://doi.org/10.1103/PhysRevLett.119.161101 opisuje samą detekcję fali grawitacyjnej. Druga, jednocześnie opublikowana tutaj https://doi.org/10.3847/2041-8213/aa91c9 zawiera podsumowanie obserwacji elektromagnetycznych tego samego źródła.

Zacznijmy od fal grawitacyjnych: sygnał zaobserwowany został we wszystkich trzech detektorach, dwóch amerykańskich LIGO i europejskim VIRGO. Był to najdłuższy z dotąd zaobserwowanych sygnałów, trwał około 100 sekund a częstotliwość zmieniała się w tym czasie od 24 do około 300 Hz. Zarejestrowano w sumie około 3000 obiegów orbity. Moment połączenia zaobserwowany został 17 sierpnia, o 14:41:04.4 czasu uniwersalnego. Był to też "najgłośniejszy" z dotąd zarejestrowanych w LIGO sygnałów, w sensie stosunku sygnał/szum (około 32). Sygnał jest wyraźnie widoczny w obydwu detektorach LIGO, natomiast w VIRGO jest widoczny bardzo słabo (sygnał/szum na poziomie 2). Jest to spowodowane częściowo niższą czułością VIRGO, a częściowo niezbyt dogodną orientacją jego ramion w stosunku do kierunku źródła. Dlatego sygnał z VIRGO był użyty tylko do wyznaczenia położenia źródła na niebie.

Sygnał jest dobrze zgodny z oczekiwanym od połączenia dwóch gwiazd neutronowych. Łączna ich masa wynosiła około 2.74-2.82 mas Słońca (wynik zależy trochę od nieznanej prędkości wirowania gwiazd przed połączeniem). Masy składników są słabiej określone, ale prawdopodobnie są sobie bliskie, cięższa z gwiazd miała masę co najwyżej dwukrotnie wyższą od lżejszej. Wartości te zgadzają się z typowymi obserwowanymi wcześniej w znanych układach podwójnych gwiazd neutronowych. Dlatego tę interpretację przyjęto jako najbardziej prawdopodobną (konkurencyjną hipotezą byłoby pożarcie gwiazdy neutronowej przez czarną dziurę, ale na to masa cięższego składnika wydaje się jednak zbyt mała). Odległość oszacowano na 130 mln lat świetlnych z błędem na poziomie 25%.

Niemal jednocześnie z detektorami fal grawitacyjnych (dokładnie 1.7 sekundy po wyznaczonym przez LIGO momencie połączenia) detektory rozbłysków gamma na pokładach satelitów Fermi i INTEGRAL zarejestrowały tzw. krótki rozbłysk gamma. Już od jakiegoś czasu tę klasę rozbłysków łączono ze sklejaniem się gwiazd neutronowych, ta obserwacja wydaje się być ostatecznym potwierdzeniem tej hipotezy.

Koincydencja pomiędzy detekcją fali grawitacyjnej a rozbłyskiem gamma przyczyniła się walnie do szybkiego poinformowania innych obserwatoriów. Początkowo bowiem algorytm szybkiego wychwytywania sygnału znalazł go tylko w danych detektora Hanford, a LIGO normalnie wysyła powiadomienia tylko przy koincydencji obydwu detektorów. Ale tak bliski czasowo rozbłysk gamma uznano za wystarczające potwierdzenie i już po niecałej pół godzinie rozesłano pierwszy alert do obserwatoriów optycznych na całym świecie. Po około 4 godzinach LIGO/VIRGO było już w stanie wyznaczyć położenie źródła na niebie (z dokładnością raczej marną jak na astronomię optyczną, chociaż fantastyczną jak na astronomię grawitacyjną - wskazany obszar miał rozmiar około 31 stopni kwadratowych). Dzięki temu, że LIGO podało przybliżoną odległość, odpowiednik optyczny udało się zaobserwować 11 godzin po rejestracji fal grawitacyjnych. Znajdował się on w galaktyce NGC 4993 w gwiazdozbiorze Hydry. Pierwszeństwo odkrycia dostał zespół nazywający się 1M2H używający teleskopu Swope w Chile, ale tak naprawdę w ciągu godziny źródło niezależnie od siebie znalazło 6 zespołów. Fotka poniżej pochodzi z teleskopu Hubble'a i pokazuje NGC 4993 z zaznaczonym miejscem rozbłysku.

W sumie w sierpniu i wrześniu obserwacje rozbłysku przeprowadziło 70 teleskopów, w różnych zakresach fal, od radiowych do promieniowania X i gamma. Źródło początkowo świeciło mocno w ultrafiolecie, ale po 1-2 dniach jasność w tym paśmie zaczęła maleć i przechodzić w emisję w podczerwieni. Świecenie w podczerwieni z kolei zaczęło przygasać około tydzień po rozbłysku. Jest to ważne o tyle, że taki przebieg krzywej blasku jest dość nietypowy, więc i źródło nie należało raczej do znanych klas, w szczególności nie wyglądało na supernową ani innego rodzaju gwiazdę zmienną rozbłyskową. Również widmo świecenia pozwalało wykluczyć supernową jako obserwowany obiekt. W widmach obserwowanych tydzień-dwa po rozbłysku widać świecenie ciężkich pierwiastków produkowanych w tzw. procesie r - szybkiego wychwytu wielu neutronów przez jądro atomowe i następującego po nim wielokrotnego rozpadu beta. Potwierdza to z kolei hipotezę, że najcięższe obecne na Ziemi pierwiastki mogą nie pochodzić z eksplozji supernowych, bo tam dominuje innych proces: tzw proces s, w którym neutrony znacznie wolniej "przylepiają" się do lżejszego jądra, dając mu czas na rozpady pomiędzy kolejnymi wychwytami neutronów, a właśnie z połączeń gwiazd neutronowych.

Kilka detektorów neutrin podjęło poszukiwania sygnału zarówno w chwili sygnału od fal grawitacyjnych, jak i później, ale żadnego nadmiaru neutrin z tego kierunku nie zaobserwowano.

I to właściwie tyle co na razie wiadomo, chociaż pewnie czeka nas teraz fala szczegółowych analiz sygnału i prac teoretycznych modelujących obserwowane zdarzenie. Dla mnie ekscytujące jest zwłaszcza to, że wszystkie te obserwatoria potrafią tak sprawnie ze sobą współpracować - pozwala to mieć nadzieję, że już wkrótce będziemy mieli więcej takich obserwacji.
Animated Photo

Post has attachment
I mamy potwierdzenie tego, co w plotkach od półtora miesiąca krążyło. LIGO/VIRGO zobaczyły sygnał połączenia dwóch gwiazd neutronowych. Jednocześnie z tym sygnałem orbitalne obserwatoria promieniowania gamma zarejestrowały krótkotrwały rozbłysk gamma. Położenie tego rozbłysku zgadza się z położeniem zrekonstruowanym z czasów przybycia i relatywnego natężenia sygnałów z LIGO i Virgo. Teleskopy optyczne znalazły we wskazanym miejscu nieba nowy, słabo świecący obiekt.

Na razie mam tylko "press release", zaraz się zabiorę za opublikowany artykuł, ale bardzo mnie też ciekawią wyniki tych obserwacji gamma i optycznych.

#LIGO
GW170817 Press Release
GW170817 Press Release
ligo.caltech.edu
Add a comment...

Post has attachment
LIGO/VIRGO pochwaliły się dziś obserwacją kolejnego sygnału od fali grawitacyjnej wywołanej połączeniem czarnych dziur. To czwarty "czysty" sygnał, i pierwszy widziany w trzech detektorach: obu LIGO w USA i VIRGO we Włoszech. Masy czarnych dziur to około 31 i 25 mas Słońca (znów jakieś ciężkie), odległość 1.8 miliarda lat świetlnych. Sygnał zarejestrowany został 14 sierpnia. Ulepszone VIRGO zostało włączone 1 sierpnia, a 25 sierpnia zbieranie danych się zakończyło, więc można rzec że mieliśmy szczęście że się w tym czasie coś trafiło.

Dzięki dołączeniu trzeciego detektora można trochę dokładniej określić położenie na niebie źródła sygnału (trochę to dobre określenie, dokładność nie jest zachwycająca). I można też spróbować coś powiedzieć o polaryzacji, chociaż i tu jest to tylko takie z grubsza sprawdzenie, że nie jest niezgodne z teorią.

Ciekaw jestem czy te plotki co się miesiąc temu rozeszły, że LIGO/VIRGO zobaczyły połączenie gwiazd neutronowych, to dotyczyły tego sygnału, czy też kolaboracja ma jeszcze coś nie opublikowanego w zanadrzu.
Add a comment...

Post has shared content
Wikipedia jest wykorzystywana w "prawdziwej" pracy naukowej. Taki wniosek zawiera praca autorstwa dwóch amerykańskich naukowców. Uzyskali oni taki wynik przeprowadzając bardzo pomysłowy eksperyment.

Trudno tak wprost sprawdzić czy autor jakiejś pracy czerpał wiedzę z Wikipedii, ponieważ praktycznie nie pojawia się ona wśród odnośników w pracach. I jest bardzo dobry powód dlaczego się nie pojawia: odnośniki powinny być zawsze do źródeł pierwotnych, czyli tych, w których dany wynik pierwszy raz się pojawił. Tymczasem Wikipedia jest niejako z definicji źródłem wtórnym: publikowanie w niej pracy oryginalnej jest wręcz zakazane, a idealnie każda informacja w niej zamieszczona powinna mieć odnośniki do odpowiednich oryginalnych źródeł.

Aby sprawdzić wpływ Wikipedii autorzy przeprowadzili następujący eksperyment: kilku doktorantów, na ich zamówienie, napisało kilkadziesiąt artykułów do Wikipedii na tematy związane z chemią. Tak przez wszystkie jej działy, organiczna, nieorganiczna, specyficzne reakcje, związki... Warunek był taki, że artykuł musiał być nowy (znaczy nie mógł wcześniej istnieć na Wikipedii artykuł na ten sam temat) a zagadnienia powinny być tak z poziomu akademickiego. Z tych kilkudziesięciu artykułów autorzy połowę opublikowali w Wikipedii, a drugą połowę schowali do szuflady, jako próbkę kontrolną. Publikacja miała miejsce na początku roku 2015.

Pod koniec roku 2016 autorzy ściągnęli sobie treść artykułów naukowych opublikowanych w poświęconych chemii czasopismach wydawanych przez Elseviera (który wydaje wiele czasopism, od mocno niszowych do bardzo prestiżowych). I uruchomili algorytm badający podobieństwo użytego słownictwa pomiędzy każdą parą artykułów z Wikipedii i z czasopism. I podobieństwo jest istotnie widoczne: artykuły ukazujące się po publikacji na Wikipedii częściej używają tego samego jak ona słownictwa. W grupie kontrolnej, artykułów nie opublikowanych na Wikipedii, podobieństwo jest słabsze i znacznie szybciej zanika z czasem. Autorzy posuwają się do takiego oszacowania, że na każde 300 słów artykułu naukowego Wikipedia ma wpływ na jedno. Widać, że autorzy prac czytali artykuły z Wiki i coś im z nich w głowach wyraźnie zostało.

"Nature" w linkowanym artykule donosi o tym troszkę w duchu "ha-ha przyłapani", ponieważ w USA (nie wiem, czy u nas też) uczelnie zniechęcają studentów do korzystania z Wikipedii, motywując to niskim poziomem zaufania do informacji w niej publikowanej. Czyli studentom zakazują, a sami czytają. Ale moim zdaniem, jak się trochę zastanowić, to ma to swój sens: naukowcy korzystają prawdopodobnie z Wikipedii jak z artykułów przeglądowych: aby szybko zorientować się w nowym dla siebie temacie i znaleźć odnośniki pozwalające im zapoznać się z nim głębiej i dotrzeć do pierwotnych źródeł. W wypadku studentów istnieje podejrzenie graniczące z pewnością, że dla większości Wikipedia byłaby pierwszym i ostatnim źródłem do którego zajrzeli. A dobrze by było żeby jednak nauczyli się też weryfikować informacje i szukać literatury, bo kiedyś może im przyjść pracować nad czymś, czego w Wikipedii jeszcze nie ma.

W każdym razie wracając do omawianej pracy - autorzy wyciągają wniosek, że Wikipedia odgrywa istotną rolę w propagowaniu wiedzy nie tylko wśród "szerokiej publiczności". ale także w środowisku naukowym. I sugerują nawet, że agencje finansujące badania naukowe powinny wymagać by, po publikacji wyników w czasopiśmie naukowym, ich autorzy zamieszczali też krótkie notki w Wikipedii na ten temat.

#wikipedia
Add a comment...

Post has attachment
Lubię filmiki z serii MinutePhysics, chociaż rzadko znajduję w nich coś naprawdę nowego, co by mnie zastanowiło. Ale ten, trwający co prawda dużo dłużej niż inne, jest prawdziwą perełką - bardzo pięknie pokazuje na czym polegają nierówności Bella i dlaczego mechaniki kwantowej nie można zastąpić teorią z "ukrytymi parametrami". A wszystko przy pomocy prostych filtrów polaryzacyjnych - eksperymentu który każdy może zrobić w domu. Nie przyszło mi nigdy do głowy, że to można tak prosto wytłumaczyć.

Uprzedzam, że niestety jest w języku obcym i, na razie przynajmniej, tłumaczeń nie widać.
Add a comment...

Post has attachment
Sondzie Cassini zostało już mniej niż 15 godzin istnienia. Jutro, krótko przed 14 naszego czasu, spłonie w atmosferze Saturna - planety którą okrążała i badała od 13 lat. W kwietniu NASA skierowała sondę na orbitę przechodzącą pomiędzy wewnętrznym pierścieniem a planetą. Z każdym obiegiem orbita nieco się zacieśniała, przy ostatnich przelotach Cassini zawadzał już lekko o atmosferę Saturna, tym razem wejdzie w nią na tyle głęboko, że tego nie przeżyje.

Kilka godzin przed tym wyłączone zostaną kamery - NASA opublikuje online ostatnie przesłane obrazy (surowe, bez żadnej obróbki) wcześnie rano naszego czasu (saturn.jpl.nasa.gov, gdyby ktoś szukał). Do końca ma działać spektrometr masowy, analizujący skład atmosfery.

Trochę żal, Cassini to jedna z bardziej udanych misji i przyniósł ogromne bogactwo danych o Saturnie, jego księżycach i pierścieniach (i osadził na powierzchni Tytana lądownik Huygens). Ale sonda dłużej już by nie dała rady funkcjonować, przede wszystkim dlatego, że wyczerpało się praktycznie paliwo w silnikach manewrowych, a bez niego nie da się kontrolować orbity i położenia. Aby uniknąć możliwej kolizji martwej sondy z którymś z księżyców Saturna i zanieczyszczenia jego powierzchni, NASA zdecydowała się zakończyć misję kontrolowanym spaleniem w atmosferze planety.

NASA urządza transmisję na żywo z ostatnich minut, ale nie spodziewam się niczego bardzo ciekawego - będzie po prostu czekanie aż zniknie sygnał. Jeżeli ktoś ma ochotę, to w podłączonym artykule są linki.
Add a comment...

Post has attachment
Znów popełniam podwójne aż wykroczenie przeciwko zasadom tej społeczności: nie dość że piszę o pracy formalnie nie zrecenzowanej, to jeszcze do tego jej całej nie przeczytałem. A nie przeczytałem, bo się na tym nie znam. Na moją obronę: bardzo mało kto się zna, wyczytawszy że taka praca się ukazała w arXiv natychmiast pobiegłem przeglądać wpisy znanych mi matematyków, prawie każdy o tym napisał, i każdy zadeklarował, że nie jest w stanie merytorycznie skomentować, bo to nie jego działka i się nie zna.

Idzie o pracę Norberta Bluma z Uniwersytetu w Bonn, dostępną w arXiv: https://arxiv.org/abs/1708.03486, która ma według autora zawierać dowód, że P≠NP. Wielu czytelników pewnie słyszało o problemie P vs NP i wie przynajmniej z grubsza o co chodzi. Tych, którzy nigdy nie słyszeli, zapewniam, że wbrew pozorom nie jest to wcale trywialne stwierdzenie. A co więcej, ma doniosłe konsekwencje praktyczne. Problem P vs NP jest jednym z siedmiu "problemów milenijnych", czyli najważniejszych nierozwiązanych problemów matematycznych z 2000 roku. Jak na razie rozwiązania doczekał się jeden z problemów z tej listy, ten ma szansę być drugim.

O co w skrócie chodzi w P vs NP: otóż chodzi o analizę czasu rozwiązywania pewnych problemów przez komputer. Codziennie dajemy komputerom do rozwiązania mnóstwo zadań obliczeniowych. Jedne z nich są "łatwe" i rozwiązywane w mgnieniu oka, nawet nie zauważymy kiedy. Inne są "trudne" i komputer musi spędzić nad nimi zauważalnie długi czas (niekiedy nawet lata). Teoria złożoności obliczeniowej zajmuje się właśnie pytaniem jak długo trwa rozwiązanie danego problemu przy pomocy komputera, a dokładniej tym jak złożoność obliczeń zależy od wielkości danych wejściowych. Z punktu widzenia tej teorii problem obliczeniowy jest prosty, jeżeli ilość obliczeń może nawet jest i duża, ale rośnie nie szybciej niż pewna potęga wielkości danych wejściowych. Przykłady: posortowanie listy liczb od najmniejszej do największej. Czas potrzebny na tę czynność rośnie troszkę szybciej niż rozmiar listy: jeżeli na posortowanie tysiąca liczb komputer potrzebuje, powiedzmy 10 ms, to na posortowanie dwóch tysięcy będzie potrzebował trochę ponad 20 ms, na na posortowanie stu tysięcy około półtorej sekundy. Czas rozwiązywania rośnie więc oczywiście z ilością danych, ale nie jakoś dramatycznie i z odrobiną cierpliwości jesteśmy w stanie posortować niemal dowolnie długą listę. Zbiór takich "prostych" problemów oznaczany jest literą P (od "polynomial" – bo czas zależy od rozmiaru danych potęgowo).

Nie wszystkie problemy są jednak takie proste: większość ciekawych problemów jest obliczeniowo "trudna", co znaczy że czas obliczeń rośnie bardzo szybko, wykładniczo albo i szybciej, z wielkością danych wejściowych. Weźmy takie słynne zadanie komiwojażera: mamy listę miast, zadanie polega na tym, aby wyjechać ze wskazanego, odwiedzić każde z nich i wrócić do punktu wyjścia. Pytanie brzmi: w jakiej kolejności mamy odwiedzać miasta by przejechać jak najmniej kilometrów? Dokąd miast jest niewiele, jesteśmy w stanie po prostu sprawdzić wszystkie możliwości. Ale liczba możliwości (czyli różnych kolejności odwiedzania) rośnie bardzo szybko z liczbą miast i praktycznie już dla dwudziestu miast rozwiązanie tą metodą robi się beznadziejne. Ludzie wymyślili sposoby na rozwiązanie tego problemu bez przeszukiwania wszystkich kombinacji, ale niestety wszystkie mają tę własność, że czas obliczeń szybko rośnie z liczbą miast. Tak, że realistycznie nasze możliwości kończą się na kilkunastu tysiącach.

Wśród tych "trudnych" problemów jest jednak taka bardzo ciekawa klasa problemów, które trudno rozwiązać, ale łatwo rozwiązanie sprawdzić. Weźmy rozkład dużej liczby na czynniki pierwsze: dla liczb złożonych z kilkunastu cyfr robi się to dość szybko, ale czas obliczeń z każdą dodatkową cyfrą rośnie kilkukrotnie, tak że rozkład na czynniki pierwsze liczby mającej tysiąc cyfr jest zadaniem praktycznie beznadziejnym dla dzisiejszych komputerów (chyba że trafi nam się liczba mająca wiele niewielkich czynników pierwszych). Ale jeżeli ktoś da nam listę kilku liczb twierdząc, że to właśnie są czynniki pierwsze naszej liczby, to sprawdzenie tego jest bardzo proste - wystarczy te liczby przez siebie pomnożyć. Mnożenie liczb, nawet bardzo dużych, jest problemem P. Takie problemy, które być może są "trudne" w powyżej wyjaśnionym sensie, ale sprawdzenie rozwiązania jest proste, nazwane zostały problemami NP.

Oczywiście jest możliwość że taki "trudny" problem tak naprawdę jest prosty, tylko po prostu nie wymyśliliśmy odpowiedniego algorytmu jego rozwiązywania. A najbardziej podejrzane są właśnie problemy NP. Wydaje się, że skoro tak łatwo sprawdzić rozwiązanie, to powinno się dać i łatwo rozwiązać. I to jest właśnie sedno problemu P vs NP. Czy problemy NP w rzeczywistości są proste, czyli czy P=NP. Nikt tego nie potrafił dotąd udowodnić, ale też nikt nie potrafił udowodnić że odwrotnie, niektóre przynajmniej problemy NP nie mają prostego rozwiązania.

Teraz dlaczego to takie ważne: otóż gdyby okazało się, że P=NP (czyli wszystkie problemy NP mają rozwiązanie w czasie wielomianowym), to wystarczyłoby znaleźć rozwiązanie jednego problemu NP (ściślej, jednego problemu z takiej podklasy problemów NP, nazwanej problemami NP-zupełnymi), a mielibyśmy automatycznie rozwiązanie dla nich wszystkich. Nie "wiedzielibyśmy że istnieje", tylko mielibyśmy je. To oznaczałoby gigantyczny postęp informatyki i możliwość rozwiązania mnóstwa ważnych zadań z dziedziny optymalizacji, ekonomii, biologii, fizyki... Z drugiej strony oznaczałoby to śmierć współczesnej kryptografii, która opiera się na istnieniu problemów NP: trudnych do rozwiązania, łatwych do sprawdzenia. P=NP znaczyłoby, że możemy natychmiast uznać za złamane i wyrzucić do kosza wszystkie klucze publiczne i podpisy cyfrowe.

Dowód, że P≠NP byłby może mniej podniecający, ale też jest bardzo ważny, bo oznaczałby że możemy przestać tracić czas na poszukiwanie łatwych rozwiązań przynajmniej dla problemów z klasy NP-zupełnych. Mamy pewność, że takowe nie istnieją.

No więc wracając do tej pracy: byłaby jak widać bardzo ważna, pytanie tylko czy jest poprawna. Jak to ładnie napisał John Baez, większość prac twierdzących, że rozwiązały któryś z najtrudniejszych problemów matematycznych, okazuje się błędna. Z drugiej strony, w większości z nich błędy są znajdowane "szybko", bo na sprawdzanie rzuca się natychmiast cały tłum najlepszych matematyków świata. No, chyba że mamy do czynienia z jakimś monstrum, typu dowód Mochizukiego hipotezy abc, wyłożony na 500 stronach, którego nikt na razie nie potrafi zrozumieć. Ale ta praca ma rozsądną długość i buduje generalnie na wcześniejszych, znanych rezultatach. Na razie chyba nikt nie wskazał jednoznacznie błędu w dowodzie, chociaż jest kilka "podejrzanych" punktów. Dyskusja w internecie trwa, czekamy jak się sytuacja rozwinie.

Aby nie zostawiać czytelników w poczuciu beznadziei (skoro P≠NP, to znaczy pewnych problemów nigdy nie rozwiążemy) – otóż wszystkie te twierdzenia zakładają, że obliczenia wykonywane są przez deterministyczną maszynę Turinga. Oznacza to, że istnieje luka którą możemy wykorzystać: wszystko co powyżej napisane nie dotyczy na przykład komputerów kwantowych, które takowymi maszynami nie są. Więc jest jeszcze nadzieja, że będziemy w stanie "szybko" znaleźć rozkład dowolnie dużej liczby na czynniki pierwsze, tyle że musimy kompletnie zmienić technologię w której próbujemy to robić.

Rysunek poniżej, pożyczony z Wikipedii, pokazuje zależności pomiędzy różnymi klasami problemów dla przypadków P≠NP i P=NP. Nie wiem, czy coś wyjaśnia, ale wszyscy piszący w internecie o tej pracy wydają się go zamieszczać, więc nie chcę się wyłamywać :)
Wait while more posts are being loaded