Ciekawostki naukowe i techniczne

FatBantha

sprzedawca niszowych etosów
Członek Załogi
8 902
25 726
P ≠ NP? Szachowa zagadka sprowadzona do problemu za milion dolarów
03.09.2017 23:17
Lista nierozwiązanych problemów matematyki liczy setki pozycji, a poczesne wśród nich miejsce zajmuje problem P ≠ NP, czyli znalezienie odpowiedzi na pytanie, czy dla każdego zagadnienia, dla którego możliwa jest szybka weryfikacja rozwiązania, możliwe jest również szybkie znalezienie tego rozwiązania. Ostatnie miesiące okazały się bardzo interesujące w tym temacie, przez chwilę pojawiła się nawet perspektywa zgarnięcia millenijnej nagrody – miliona dolarów – za poprawne rozwiązanie. A jednak chyba nic z tego. Coraz bardziej wygląda na to, że P ≠ NP pozostanie problemem, który matematycznymi metodami jest niemożliwy do rozstrzygnięcia, w którym uczeni mogą co najwyżej wygłaszać swoje deklaracje wiary.

Na siłę nie ma czasu?

Możliwość sprowadzenia znalezienia rozwiązania do sprawdzenia rozwiązania ma oczywiście kluczowe znaczenie dla informatyki – przede wszystkim w kryptografii, gdzie polegamy na tym, że pewne operacje są trudne, ich wykonanie wymaga ogromnej mocy obliczeniowej. Ale nie tylko, problem P ≠ NP przewija się przez maszynowe dowodzenie twierdzeń, a także badania operacyjne w ramach teorii decyzji, ma swoje ważne konsekwencje dla filozofii, a nawet biologii. Dlatego też w 2000 roku Instytut Matematyczny Claya, fundacja, która za swój cel postawiła sobie rozwój wiedzy matematycznej, włączyła go na listę siedmiu problemów nagrody millenijnej, za których rozwiązanie wyznaczono po milionie dolarów nagrody.

Najbardziej zrozumiałe chyba dla laików objaśnienie P ≠ NP przedstawia sam Instytut Matematyczny Claya:

Załóżmy, że organizujesz nocleg dla 400 studentów. W akademiku brakuje jednak miejsca dla wszystkich – jest tylko 100 miejsc. W dodatku dziekan przygotował listę par skłóconych ze sobą studentów i zażądał, by w twoim ostatecznym zestawieniu nie znalazła się żadna taka para. To właśnie jest przykład NP-zupełnego problemu: łatwo jest sprawdzić, czy dany zestaw stu studentów przygotowanych przez pomocnika jest satysfakcjonujący (tj. żadna para z jego listy nie pojawia się na liście dziekana), jednak zadanie wygenerowania takiej listy od podstaw jest tak trudne, że praktycznie niemożliwe. Liczba sposobów, na jakie można wybrać zgodnie z tymi wytycznymi 100 studentów z 400 kandydatów jest większa, niż liczba atomów we wszechświecie. Nie ma co liczyć na to, że powstanie komputer zdolny do siłowego rozwiązania problemu, tj. wygenerowania każdej możliwej kombinacji 100 studentów.

Może jednak to tylko problem z wyobraźnią programistów? Czy możliwe jest dla tego problemu stworzenie algorytmu, który rozwiązałby go w jakiś sprytny sposób (równoważny P-problem), szybko sprawdzając możliwe odpowiedzi? Jak do tej pory nikt nie dowiódł, że to jest tak trudne, na jakie to wygląda, tj. że nie ma żadnej sensownej drogi wygenerowania odpowiedzi z pomocą komputera.


Sprzeczne dowody – co miesiąc inny wynik

Dwa tygodnie temu niemiecki informatyk, profesor Norbert Blum (bycie informatykiem oznacza tu pisanie książek w rodzaju Eine Omega(n4/3) untere Schranke für die monotone Schaltkreiskomplexität von n-te Grad Convolution) przedstawił obiecujące rozwiązanie problemu P ≠ NP. Nie pierwsze oczywiście – do września 2016 roku opublikowano 116 prac, których wyniki są, delikatnie mówiąc, rozbieżne – 62 prace dowodzą, że P = NP, 50 że P ≠ NP, jedna, że problem jest nierozstrzygalny, dwie, że jest niedowiedlny. Żadna z tych prac nie wytrzymała próby czasu, w każdej dopatrzono się uchybień.


Z perspektywy teorii złożoności problemy P to klasa tych wszystkich problemów decyzyjnych, które mogą zostać rozwiązane przez deterministyczną maszynę Turinga (czytaj: komputer) w czasie wielomianowym (czytaj: szybko), zależnym od danych na wejściu. Problemy NP to klasa tych wszystkich problemów, których pozytywne rozwiązanie może zostać zweryfikowane w wielomianowym czasie po podaniu na wejściu odpowiedniej informacji.

Tym razem atak na ten twardy do zgryzienia orzech przeprowadzono uogólniając pewne rezultaty z zakresu teorii złożoności, dotyczącej złożoności obwodów – gdzie funkcje boole’owskie są klasyfikowane zgodnie z rozmiarem obwodów z bramek logicznych, które je wyliczają. Uogólnienie przełożyło rozstrzygnięcia dla obwodów monotonicznych (złożonych tylko z bramek AND i OR) tak by działało to także dla ogólnych obwodów (niemonotonicznych), złożonych z bramek AND, OR i NOT. Jeśli uogólnienie byłoby słuszne, to P ≠ NP.

Krytyka przyszła bardzo szybko, jak ktoś czuje się dobry z algebry i teorii złożoności, może zapoznać się z dyskusją na łamach Stack Exchange. Wystarczyła, by Blum przyznał, że dowód jest niepoprawny. Ekspert od informatyki kwantowej z Teksasu, Scott Aaronson, który gotów był postawić 200 tys. dolarów na niepoprawność tego dowodu, napisał na swoim blogu:

Na próżno szukam właściwego sposobu nauczenia świata nerdów, by mniej się ekscytowali takimi twierdzeniami, by reagowali tak jak eksperci – „o nie, tylko nie kolejny” – co nie oznacza, że znasz błąd, lub że nawet wiesz, że jest tu błąd, lecz po prostu znasz historię problemu.

By pomóc nie dość należycie wykształconym nerdom, profesor Aaronson uruchomił więc stronę haspvsnpbeensolved.com, gdzie można podać adres URL artykułu do sprawdzenia, by dowiedzieć się (po konsultacji z kwantowymi wyroczniami, że nie, niczego nie udowodniono.

Złam łamigłówkę, złam szyfr

To oczywiście żart, ale wyniki nie przestają napływać. Niekiedy bardzo osobliwe. Dopiero co w Journal of Artificial Intelligence Research, Ian P. Gent, Christopher Jefferson i Peter Nightingale opublikowali artykuł pt. Complexity of n-Queens Completion, dotyczący klasycznego szachowo-matematycznego problemu n królowych. Rzuca on wyzwanie programistom: kto znajdzie rozwiązanie tej prostej szachowej zagadki, jednocześnie rozwiązać ma problem, za którego rozwiązanie czeka milion dolarów.

Zadanie jest proste do wyjaśnienia: na szachownicy o wymiarach n×n musimy umieścić n królowych tak, by żadna z nich nie atakowała innej – tj. były na różnych liniach, kolumnach i przekątnych. Istnieją siłowe rozwiązania dla n<20 (za wyjątkiem n=2 i n=3), ale gdy n robi się większe, złożoność problemu zaczyna być zabójcza dla najpotężniejszych superkomputery. Dla normalnej szachownicy 8×8 mamy 4 426 165 368 możliwych ustawień ośmiu królowych, ale tylko 92 możliwe rozwiązania. Dlatego też problem n królowych jest używany powszechnie jako benchmark sztucznych inteligencji,


Praca wspomnianych autorów ma wykazać, że problem n królowych i pokrewne problemy są zarazem problemami NP-zupełnymi jak i #P-zupełnymi, to jest takimi, które należą do klasy złożoności #P – obejmującej funkcje pytające nie tyle o istnienie, co o liczbę (np. ile podzbiorów na danej liście liczb całkowitych sumuje się do zera?).

Udowodnienie, że tradycyjna szachowa zagadka jest problemem NP-zupełnym jest o tyle istotne, że dowolny problem NP-zupełny może zostać zreformułowany jako inny problem NP-zupełny. Stworzenie programu, który by szybko (w czasie wielomianowym, a nie wykładniczym) rozwiązywał tę zagadkę szachową byłoby więc w praktyce szybkim złamaniem szyfru RSA, w którym zakłada się, że problem podziału dowolnej liczby na czynniki pierwsze nie jest problemem wielomianowym.

Póki co relacja miedzy złożonością P i NP pozostaje kwestią wyznania wiary matematyków. W 2012 roku przeprowadzono w tej społeczności sondaż. Odpowiedziało 151 osób, 83% uznało, że P ≠ NP, 12% uznało że P=NP, 3% uznało że dowiedzenie tego jest niemożliwe, 5% uznało, że nie wie lub nie chce rozwiązania tego problemu.
 

rawpra

Well-Known Member
2 741
5 402
Od wczoraj każdy może za pomocą smartfona poszukać ciemnej materii
31 sierpnia 2017, 07:16 | Technologia

n-szyja-technologiczna-c0d19b9e4753c21cdd7142ce5da86764.jpg


Od wczoraj każdy zainteresowany Wszechświatem może wziąć udział w niecodziennym eksperymencie kosmicznym. Do udziału w projekcie, którego celem jest odkrycie ciemnej materii, potrzebny jest jedynie smartfon.

Eksperyment jest możliwy dzięki specjalnej aplikacji CREDO Detector, która dostępna będzie od środy na stronie: http://credo.science

Po jej uruchomieniu oraz włączeniu modułu GPS, smartfon zamieni się w detektor i wyśle naukowcom informacje, gdzie i kiedy została zarejestrowana cząstka promieniowania kosmicznego. Te dane będą analizowane w Akademickim Centrum Komputerowym Cyfronet AGH, które na bieżąco będzie informować o postępach w poszukiwaniu śladów ciemnej materii – wyjaśnił autor aplikacji dr inż. Piotr Poznański z Politechniki Krakowskiej.

Aplikacja CREDO Detector będzie miała swoją premierę właśnie w środę, podczas dwudniowego (środa, czwartek) seminarium w Instytucie Fizyki Jądrowej PAN w Krakowie. Na sympozjum fizycy z Polski i zagranicy przedyskutują możliwości i perspektywy projektu CREDO. Środowa sesja jest otwarta dla wszystkich chętnych.

Twórca CREDO Detector zwrócił uwagę, że z aplikacji najlepiej korzystać w nocy, kiedy telefon nie jest wykorzystywany do innych celów.

Testy aplikacji potrwają przez miesiąc. W tym czasie zostanie sprawdzona jej podstawowa funkcjonalność, niezawodność, częstotliwość rejestrowania cząstek promieniowania kosmicznego oraz komunikacja z centrum analizującym dane - powiedział Poznański.

Spodziewa się on, że po wrześniowych testach aplikacja uzyska nowe możliwości i w jesieni zacznie się prawdziwa przygoda naukowa, do której włączać się będą coraz liczniejsi badacze z nurtu tzw. obywatelskiej nauki. Tym bardziej, że naukowcy z projektu CREDO pracują także nad małymi stacjonarnymi detektorami, które można będzie postawić w szkołach, uczelniach, urzędach, domach.

Kluczem do sukcesu jest stworzenie jak najliczniejszej społeczności badaczy. Jeśli projekt ma się udać, uczestników musi być ok. miliona. Oznaczałoby to stworzenie największej współpracy naukowej na świecie– mówił współtwórca projektu CREDO dr Michał Krupiński z Instytutu Fizyki Jądrowej PAN.

Jak dodał, każdy uczestnik projektu będzie mógł sprawdzać na bieżąco, ile cząstek udało mu się wykryć i czy podobne zdarzenia zostały zarejestrowane w innych częściach świata. Wszystkie zebrane dane będą ogólnodostępne. Osoby badające promieniowanie swoimi smartfonami będą również współautorami publikacji naukowych, które powstaną w trakcie realizacji projektu – zwrócił uwagę Krupiński.

Zdaniem uczonych CREDO ma ogromny potencjał badawczy. Oprócz poszukiwań ciemnej materii naukowcy chcą również prowadzić w ramach projektu badania geofizyczne i zweryfikować hipotezę o istnieniu związku pomiędzy zmianami natężenia promieniowania kosmicznego a trzęsieniami ziemi.

Dotychczas nie dysponowaliśmy odpowiednim narzędziem, które pozwoliłoby prowadzić takie badania. Czy wspólnie odkryjemy coś nowego? Jeżeliby się to udało, takie odkrycie z pewnością zasługiwałoby na Nagrodę Nobla – powiedział lider projektu CREDO Piotr Homola.

Międzynarodowy projekt CREDO (Cosmic-Ray Extremely Distributed Observatory, tj. skrajnie rozproszone obserwatorium promieniowania kosmicznego) zainicjowali przed rokiem naukowcy z krakowskich ośrodków: Instytutu Fizyki Jądrowej PAN, Politechniki Krakowskiej, Akademii Górniczo-Hutniczej. Do projektu włączyli się badawcze z Czech, Słowacji, Węgier.

Od ponad pół wieku fizycy i kosmolodzy próbują dociec, czym jest ciemna materia. Tego zagadkowego składnika Wszechświata nie widać, a - jak oceniają naukowcy - ma decydujący wpływ na ewolucję kosmosu. Wszystkie dotychczasowe próby uchwycenia cząstek ciemnej materii kończyły się niepowodzeniem.

http://kopalniawiedzy.pl/smartfon-ciemna-materia-CREDO-Detector,26961
 

tolep

five miles out
8 550
15 439
Feynman, fizyk, puścił nieco pocisków w stronę matematyków

A pod spodem jakiś Rosjanin mocno tam masakruje Feynmana w szczególności, a fizyków w ogóle. Pod tym komentarzem
No hejt na pełnej kurwie się rozpoczyna, a to zdaje się świeży filmik jest.
 

NoahWatson

Well-Known Member
1 297
3 200
Feynman, fizyk, puścił nieco pocisków w stronę matematyków

A pod spodem jakiś Rosjanin mocno tam masakruje Feynmana w szczególności, a fizyków w ogóle. Pod tym komentarzem
No hejt na pełnej kurwie się rozpoczyna, a to zdaje się świeży filmik jest.

Taki same "flame war" można rozpocząć między naukowcami np fizykami (nie ważne czy doświadczalni czy teoretyczni), a inżynierami ;)
 

tolep

five miles out
8 550
15 439
W ogóle jako reprezentant prawicy niepisowskiej i były uczestnik olimpiad matematycznych mam automatycznie ochotę stanąć po stronie tego Rosjanina ale nie, bo matematycy to chuje.

Człowiek wpada na YouTube żeby pooglądać jakiś popularny wykład o mechanice kwantowej, nagle pada pojęcie matematyczne mglisto pamiętane z czasów edukacji. Więc człowiek zagląda do jakze popularnej Wikipediii, bo próbuje sobie przypomnieć to pojęcie w ogólnych zarysach, a tam hasło zaczyna się od:

Niech [jakiś znak przypominający, lecz nie do końca, normalna literę] będzie przestrzenią nad ciałem [jakiś znak podobny, ale nie całkiem, do innej litery] i tak dalej.

Tak to nie będziemy się bawić, panowie matematycy. Bawcie się sami ze sobą. Ma się ochotę wyjść z puszką farby i nabazgrac właśnie to na murze: "MATEMATYCY ZABAWIAJĄ SIĘ SAMI ZE SOBĄ".
 

kompowiec

freetard
2 567
2 622
Tak to nie będziemy się bawić, panowie matematycy. Bawcie się sami ze sobą. Ma się ochotę wyjść z puszką farby i nabazgrac właśnie to na murze: "MATEMATYCY ZABAWIAJĄ SIĘ SAMI ZE SOBĄ".
to idź obejrz sobie kanał popularno-naukowy jak choćby naukowy bełkot a nie płakusiasz że nie rozumiesz ścisłej naukowej terminologii...
 

tolep

five miles out
8 550
15 439
pisałeś na szaucie kiedyś, że głosowałeś na pis

Nigdy. Raz na PO za to, w 2001 bodajże, gdy korwiniści startowali z ostatnich miejsc. Mnie się zazwyczaj w ogóle nie chce iść na wybory nawet na korwinistów głosować, to na PiS bym poszedł? No nie...
 

NoahWatson

Well-Known Member
1 297
3 200

No i po co to? Dać takiemu fizykowi do zaprojektowania urządzenie wraz z procesem technologicznym to się posra, a nie skończy do końca życia projektu. Inżynieria > nauka.
I nie propsuję tu całkiem wiedzy techników, którzy robią wiele rzeczy na oko i na podstawie mglistego doświadczenia osobistego.
Inżynier robi metodycznie, włącza doświadczenia innych, przewiduje, mierzy, liczy, ale jednak pomija mało znaczące zjawiska i dlatego jest w stanie wykonać coś w sensownym czasie, zamiast zastanawiać się jak naukowcy nad jednym, mało istotnym zagadnieniem całe życie i w konsekwencji nie zrobić niczego.
Pomijanie zjawisk nieistotnych i sensowne uproszczanie w modelach zjawisk istotnych, lecz trudnych do dokładnego policzenia to kwintesencja inżynierii i to jest coś, czego fizycy nie umią.
Inżynieria > nauka.
 
OP
OP
kr2y510

kr2y510

konfederata targowicki
12 770
24 700
Dać takiemu fizykowi do zaprojektowania urządzenie wraz z procesem technologicznym to się posra, a nie skończy do końca życia projektu.
Zależy który. Jak potrafi zaprojektować i wykonać eksperyment, budując w tym celu różne urządzenia i adaptując inne, to i z procesem technologicznym da sobie radę. Nic nie stoi na przeszkodzie.
A to że tego akurat nie robi, to inna sprawa.
 

FatBantha

sprzedawca niszowych etosów
Członek Załogi
8 902
25 726
No i po co to? Dać takiemu fizykowi do zaprojektowania urządzenie wraz z procesem technologicznym to się posra, a nie skończy do końca życia projektu. Inżynieria > nauka.
Najszybszy test na eSowość... :)

- Co pan sądzi o pięknie czysto formalnych, abstrakcyjnych rozważań i uogólnień w matematyce?
- Proszę pana, ja pierdolę takie piękno!
 

NoahWatson

Well-Known Member
1 297
3 200
Zależy który. Jak potrafi zaprojektować i wykonać eksperyment, budując w tym celu różne urządzenia i adaptując inne, to i z procesem technologicznym da sobie radę. Nic nie stoi na przeszkodzie.
A to że tego akurat nie robi, to inna sprawa.
Chciałem trochę kontrowersji wprowadzić tylko do tematu ;)
Najszybszy test na eSowość... :)

- Co pan sądzi o pięknie czysto formalnych, abstrakcyjnych rozważań i uogólnień w matematyce?
- Proszę pana, ja pierdolę takie piękno!
Według testów MBTI wychodziła mi literka N, a nie S ;)
Lubię modele, abstrakcyjne rozważanie, tylko nie wszystkie. Lubię te mające zastosowanie w jakiejś sensownej perspektywie czasowej. Dlatego też nie przepadam za podejściem typowych (z mentalności) techników, którzy robią mentalne copy-paste rozwiązań z poprzednich sytuacji, w których się znaleźli bez zastanowienia się czy tutaj pasuje i rozumiem, że do niektóre rzeczy trzeba policzyć albo w inny sposób przewidzieć.
I ogólnie mówiąc ubolewam, że powszechnie znane są tylko dwa rodzaje osób zajmujących się techniką (a przynajmniej ja takie mam wrażenie po edukacji + własnych obserwacjach): super-szczegółowych naukowców i techników, robiących nieprzemyślane, niepoliczone copy-paste na podstawie osobistego, mglistego doświadczenia i skojarzeń.
 

tolep

five miles out
8 550
15 439
Meissner utrzymuje uparcie, po swoim kilkunastoletnim zajmowaniu się teorią strun, że matematyka jest 3 dekady opóźniona w stosunku do fizyki. Podejrzewam że rzeczowej polemiki wprost z tym stwierdzeniem nie znajdę, za to w ramach rozrywki polecam fajny beef między Meissnerem i Bajtlikiem (Demiański tylko otwiera)


Zwłaszcza na prędkosci 1.25 słychac emocje, a poza tym oszczędza się czas.
 

mikioli

Well-Known Member
2 770
5 377
Meissner utrzymuje uparcie, po swoim kilkunastoletnim zajmowaniu się teorią strun, że matematyka jest 3 dekady opóźniona w stosunku do fizyki. Podejrzewam że rzeczowej polemiki wprost z tym stwierdzeniem nie znajdę, za to w ramach rozrywki polecam fajny beef między Meissnerem i Bajtlikiem (Demiański tylko otwiera)


Zwłaszcza na prędkosci 1.25 słychac emocje, a poza tym oszczędza się czas.

Trochę głupie podejście bo to jakby zarzucać technice, że jest 100 lat za literaturą SCI-FI.
 

tolep

five miles out
8 550
15 439
Wlasnie mam za oknem 0 stopni po raz pierwszy od wiosny.

Przeoczyłem jakoś newsa, że efekt Mpemby został wyjaśniony. Z tym że niekoniecznie, bo z tym wyjaśnieniem nie wszyscy się zgadzają...
 

Staszek Alcatraz

Tak jak Pan Janusz powiedział
2 790
8 459
W Meksyku powstanie elektrownia słoneczna z najtańszą energią elektryczną na świecie 1,77 centa/kWh

Prawdopodobnie za 5 lat solary będą opłacalne w naszej szerokosci geograficznej i tansze niż każde inne źródło energii. A w Polsce? W Polsce jak w lesie, kurwa. Pisowcy będą budować coraz droższe nowe elektrownie węglowe wyrzucając pieniądze w błoto, albo jakieś absurdalne farmy wiatrowe na Bałtyku - też kilka razy droższe. Tutaj nikt nie myśli, nie obserwuje co się dzieje na świecie i jakie są trendy.
 
Ostatnia edycja:
Do góry Bottom