Ogromna współpraca online w celu rozwiązania otwartego problemu w informatyce teoretycznej

W projektach Polymath duża grupa pracuje nad otwartym problemem.

Jakie problemy wydają się działać najlepiej w tych ramach?
Czy są jacyś dobrzy kandydaci na projekt polimorficzny w informatyce teoretycznej?
Czy są jakieś przeszkody, które sprawiają, że projekty Polymath rzadziej odnoszą sukcesy w informatyce teoretycznej w porównaniu z innymi dziedzinami matematyki?

soft-question open-problem research-practice

— Joshua Herman
źródło

Polymath4 już koncentrował się na pytaniu TCS: zaprojektowaniu szybszego algorytmu deterministycznego w celu znalezienia liczby pierwszej w danym zakresie. Polymath3 skupił się na wielomianowej hipotezie Hirscha, która jest ściśle związana z analizą algorytmów simpleksowych. Chodzi mi o to, że TCS to matematyka, a projekt polimorficzny TCS nie musi różnić się od żadnego innego projektu polimorficznego.

— Sasho Nikolov,

świetny pomysł! ale nie pasuje zbyt dobrze do pliku stackexchange fmt. jednak pokoje czatu mogą być naturalnym / skutecznym miejscem do organizowania i zostały już wykorzystane do niektórych z tych celów. od czasu do czasu zdarzały się prace grupowe TCS, np. przy przeglądzie dowodu deolalikar itp. głównym wyzwaniem związanym z nauką online / otwartą wydają się być bodźce, które zidentyfikował Nielsen w swojej doskonałej książce Networked science

— vzn

Myślę, że projekt HoTT z dedykowanym blogiem, kilkoma repozytoriami GitHub, spotkaniami twarzą w twarz (i publicznym założeniem) jest bardziej obiecującym modelem wspólnych badań teoretycznych w dziedzinie informatyki niż projekty Polymath oparte na „supergwiazdach matematyki”.

— Thomas Klimpel,

@ThomasKlimpel Biorąc pod uwagę, że Hott pochodzi od medalisty Fieldsa, i że książka Hott została napisana i sfinansowana przez IAS, trudno jest zrozumieć, w jaki sposób Hott nie jest również „superbohaterem matematyki”.

— Martin Berger,

@ThomasKlimpel Przykro mi, że jestem surowy, ale uważam, że jest to absurdalny komentarz. Z jednej strony porównujesz wysiłek, który wymagał znacznego finansowania i nietrywialnej pracy organizacyjnej, z modelem, który może być natychmiast skonfigurowany przez każdego i zasadniczo nie wiąże się z żadnymi kosztami. Po drugie, lekceważenie „cudownych matematyki” jest niepotrzebne i mylące. Gowers, Tao i Kalai są doskonałymi matematykami, którzy są aktywni online. Kto jeszcze może prowadzić takie rzeczy? (I jak zauważył Martin, Voevodsky jest również medalistą Fields.)

— Sasho Nikolov

Odpowiedzi:

Wydaje się, że projekty Polymath odnoszą sukcesy, gdy następuje przełom, a ktoś próbuje zoptymalizować wynik przełomu lub opracować prostszy lub lepszy dowód. Zobacz https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved . Jako taki, musiałbyś wybrać taki problem w CS. Jedyne, co od razu przychodzi mi na myśl, to poprawa stałej mnożenia macierzy https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication , która obecnie wynosi 2,4 ... Ale szczerze mówiąc, nie jestem pewna, czy ludziom zależy na tym wystarczy pracować nad tym ...

Pytania, dla których spodziewałbym się, że polimath zawodzi żałośnie: P = NP, optymalność online, UGC itp.

— Sariel Har-Peled
źródło

Cóż, jakiś czas temu istniał rodzaj projektu polimath, w którym analizowano ogłoszony dowód P = NP, który okazał się niepoprawny ...

— J.-E.

Mnożenie macierzy stało się ostatnio popularne ...

— Yuval Filmus,

Znalezienie czystszych wersji dowodów twierdzeń PCP może być użytecznym przedsięwzięciem.

— Phylliida,

@ J.-E.Pin: więc projekt był sukcesem!

— cody

najwyraźniej yuval jest zbyt skromny, by cytować własną pracę nad mnożeniem macierzy. jeśli ktoś opublikuje jakiekolwiek komentarze do tego postu (obecnie zero), może rozpocząć tam właśnie cyberprzestępczość. pokazując, że wyzwaniem nie jest wcale infrastruktura techniczna, która istniała od lat, ale (1) brak ekspertów i (2) eksperci w tej dziedzinie stosujący się w inny typowy / konwencjonalny sposób (np. pisanie artykułów, uczestnictwo w konferencjach itp.)

— Wzn

Jeśli zostanie nawiązana masowa współpraca online, powinna ona skoncentrować się na problemach z rozsądną szansą na sukces. Trzy klasyczne problemy konstrukcyjne starożytności znane są jako „kwadratura koła”, „dzielenie kąta” i „podwojenie sześcianu”. Współczesna matematyka rozwiązała wszystkie trzy, ale znacznie ważniejsza była wcześniejsza rewolucja Kartezjusza, która umożliwiła matematyce uwolnienie się z mentalnego więzienia kompasu i prostych konstrukcji. Zauważ, że Grecy używali kompasu i prostej jako praktycznego urządzenia obliczeniowego, o czym świadczy skuteczny schemat aproksymacji epicyklu dla obliczeń z mechaniki niebieskiej.

Wiele przypuszczeń i uogólnień rozwiązanych przypuszczeń z teorii grafów powinno podlegać rozwiązaniom poprzez współpracę. Jednak typowe doświadczenie ze współpracą sugeruje, że zespoły 2-4 członków są znacznie bardziej skuteczne niż zespoły znacznie większe. Przykładem bardzo udanego zespołu w tej dziedzinie są N. Robertson, PD Seymour i R. Thomas, którzy zaatakowali takie problemy, jak silna idealna hipoteza grafowa, uogólnienia twierdzenia o czterech kolorach i domniemane pokrewne wykresy. Czas, jaki upłynął między ogłoszeniem nowych wyników a ich faktyczną publikacją, był niezwykle długi, również dla innych zespołów naukowców w tej samej dziedzinie, co wskazuje, że czysta ilość pracy spowalnia tutaj, tak że współpraca (co już się dzieje) może być korzystna przyspieszyć. (JA'

Obecnie staram się zrozumieć rolę kompletności intuicyjnej logiki w praktycznych zastosowaniach komputerowego obalenia dowodu. Ale jeśli naprawdę planujesz wykonać proofy przez masową współpracę online, to posiadanie solidnego wspomaganego komputerowo systemu odrzucania dowodów może być naprawdę ważne. W końcu, jeśli nie znasz wystarczająco dobrze swoich współpracowników, jak będziesz w stanie ocenić, czy możesz zaufać ich wkładowi, nie marnując znacznej ilości czasu na sprawdzanie wszystkiego, co zrobili? (Mam wrażenie, że matematycy są bardziej przyzwyczajeni do udowodnienia odrzucenia i cieszą się jego pozytywnymi stronami, takimi jak bezpośrednie osobiste opinie, podczas gdy informatycy wykazują mniej rutyny przy tego rodzaju opiniach.) W każdym razie,

— Thomas Klimpel
źródło