Przykłady pedanterii w TCS

Larry Wasserman ma niedawny post, w którym mówi o „policji p-value”. Robi interesujący punkt (wszystkie moje podkreślenia) (przesłankę kursywą, którą dodałem, a jego odpowiedź poniżej):

Najczęstszą skargą jest to, że fizycy i dziennikarze nieprawidłowo wyjaśniają znaczenie wartości p. Na przykład, jeśli wartość p wynosi 0,000001, zobaczymy takie stwierdzenia, jak: „istnieje 99,9999% pewność, że sygnał jest prawdziwy”. Czujemy się wówczas zmuszeni do skorygowania stwierdzenia: jeśli nie ma efektu, wtedy istnieje szansa na coś ponieważ lub bardziej ekstremalna wynosi 0,000001.

Słusznie. Ale czy to naprawdę ma znaczenie? Ogólny obraz jest następujący: dowody na to, że efekt jest przytłaczający. Czy to naprawdę ważne, czy sformułowanie jest nieco mylące? Myślę, że wzmacniamy nasz wizerunek jako pedantów, jeśli narzekamy na to.

Co skłoniło mnie do myślenia -

Czy istnieją dobre przykłady pedanterii w TCS? Taki przykład składałby się z

• Twierdzenie to jest powszechnie zgłaszane w popularnej prasie
• Standardowa korekta, na którą ludzie nalegają
• Prawidłowy „duży obraz”, który rejestruje roszczenie, nawet gdy jest nieprecyzyjny.

gdy twierdzenie jest matematycznie błędne, ale „moralnie słuszne”, a poprawka jest technicznie poprawna, ale nie zmienia intuicyjnego zrozumienia.

Na przykład, moim przykładem byłoby:

• Roszczenie - problemy z NP-zupełnym rozwiązaniem wymagają wykładniczego czasu
• Korekta - tak naprawdę nie wiemy, czy można je rozwiązać w czasie wielomianowym
• Duży obraz - problemy z kompletnym NP są trudne

Uwaga: wiem, że na tym forum jest wielu, których głowa eksploduje na myśl twierdzeń, które są błędne, ale „moralnie poprawne” :). Pamiętaj, że są to oświadczenia skierowane do opinii publicznej (gdzie można zezwolić na pewien stopień licencji), a nie oświadczenia złożone w pracy badawczej.

Hm, trudno nawet wymyślić przykłady twierdzeń o TCS, które trafiły do ​​popularnej prasy.

Jedną rzeczą, którą od czasu do czasu widziałem, jest twierdzenie, że faktoring jest trudny do wyjaśnienia w kontekście wyjaśniania kryptografii. Jest to związane z mniej nieszkodliwym błędem twierdzenia, że ​​komputery kwantowe mogą rozwiązać trudne problemy NP, ale ograniczając się do kontekstu kryptografii, jest to błąd stosunkowo łagodny. Chodzi o to, że my (użytkownicy kryptografii) wierzymy, że nie ma skutecznego algorytmu do rozwiązania problemu. Szczególne przypuszczenia, których używamy, aby uzasadnić to twierdzenie, są poza tym istotne.

• roszczenie przez prasę: o rzeczach, które rosną „wykładniczo”, tj. roszczenie O (k ^ n)

• faktycznie prawda: często stała moc O (n ^ k)

• duży obraz: rośnie wystarczająco szybko

• Twierdzenie przez prasę: Pierwszy algorytm wielomianu czasu dla ważnego problemu praktycznego koniecznie zmieni nasze życie, będzie kolejną najlepszą rzeczą po krojonym chlebie itp.

Na przykład weź dowolny artykuł prasowy na temat algorytmu elipsoidalnego od momentu jego odkrycia (świetny opis tej historii: http://www.springerlink.com/content/vh32532p5048062u/ ). Prasa twierdziła, że ​​to nowe wielkie odkrycie matematyczne wpłynie na życie wszystkich, rozwiąże TSP (co okazało się szczególnie ironiczne, biorąc pod uwagę, że niewielu podróżujących sprzedawców było w ZSRR!), Wywróci krypto do góry nogami itp.

Jest też AKS, który w niektórych raportach sugerował nawet rozwiązanie faktoringu lub przynajmniej innowację zmieniającą branżę.

Jestem pewien, że jest o wiele więcej przykładów.

• Właściwie to prawda: czas wielomianowy nie oznacza praktycznego! Przykład: algorytm elipsoidalny, próbkowanie z wielowymiarowych ciał wypukłych. Czas wykładniczy w najgorszym przypadku nie oznacza niepraktycznego. Przykład: algorytm simpleks. Gdy nowy algorytm jest zaledwie pierwszym deterministycznym algorytmem czasu policyjnego dla problemu, ma to jeszcze mniejsze znaczenie w praktyce.

• $\log^5 n$

Popularna prasa często sprawia wrażenie, że głównym, jeśli nie jedynym, powodem, dla którego komputery odnoszą sukcesy w coraz większej liczbie zadań (pokonanie Kasparowa na szachach, pokonanie Jenningsa w Jeopardy itp.), Jest zwiększona moc przetwarzania. Postępy algorytmiczne zwykle nie mają tak dużego uznania.

Jestem jednak ambiwalentny, czy naleganie, aby postępy algorytmiczne miały większą wagę, jest „pedanterią”. Z jednej strony uważam, że ci z nas, którzy są bardziej teoretycznie skłonni, mogą czasem przeceniać znaczenie postępów algorytmicznych i tylko niechętnie przyznają wagę zwiększonej mocy obliczeniowej. Z drugiej strony uważam, że społeczeństwo powinno być lepiej informowane o roli postępów teoretycznych w rozwiązywaniu praktycznych problemów.

Scott Aaronson, choć jest najważniejszym autorytetem, zdaje się regularnie podejmować działania w celu niedokładnego rozczesania włosów. np. jego ostatnia kolumna w artykule NYT „Obliczenia kwantowe obiecują nowe spostrzeżenia, a nie tylko supermachiny” [kursywa dodana]

Większość pisarzy, walcząc o przekształcenie matematyki w przyjazne dla gazety metafory, opisuje komputer kwantowy jako magiczną maszynę, która może przetwarzać każdą możliwą odpowiedź równolegle, zamiast wypróbowywać ją pojedynczo. Podobno może to zrobić, ponieważ w przeciwieństwie do dzisiejszych komputerów, które manipulują bitami, komputer kwantowy manipuluje bitami kwantowymi lub kubitami, które mogą być równe 0 i 1 jednocześnie.

Ale to prymitywny sposób na wizualizację tego, co robi komputer kwantowy, i tęskni za najważniejszą częścią historii. Kiedy mierzysz wydajność komputera kwantowego, widzisz tylko jedną losową odpowiedź - nie listę wszystkich możliwych odpowiedzi. Oczywiście, gdybyś tylko chciał losowej odpowiedzi, mógłbyś wybrać ją sam, bez większych problemów.

jednak metafora kwantowych odpowiedzi komputerowych przetwarzanych równolegle jest szeroko rozpowszechniona i jest rozsądnym pojęciowym uproszczeniem obliczeń QM, do czego odwołuje się wiele podręczników dotyczących obliczeń QM. są prawdopodobnie inne przykłady z teorii / obliczeń QM.

istnieje naturalne napięcie w TCS i innych badaniach teoretycznych w komunikacji z opinią publiczną / mediami, ponieważ czasami kładzie nacisk na krytyczne rozróżnienia / koncepcje w ramach rygorystycznego szkolenia, które nie jest znane ani ważne dla laików. innymi słowy, w wielu przypadkach teoria badań działa przeciwko różnym pojęciowym uproszczeniom, które są uzasadnione dla laików.