Przykłady pedanterii w TCS

15

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.

ds.algorithms soft-question big-list

— Suresh Venkat
źródło

1

Nie jesteś tego pewien, ale czy „prawdziwa przypadkowość” może się kwalifikować? Ludzie często twierdzą, że coś jest (naprawdę) losowe, podczas gdy w rzeczywistości nie wiemy. Ponieważ ciągu jest nieobliczalny, nie możemy zweryfikować twierdzenia o losowości. Niemniej jednak w praktyce wiele źródeł generowania losowości jest często wystarczająco losowych.

K (x)

$K(x)$

x

$x$

— Juho,

To ciekawy pomysł, ale czy w popularnej prasie mówi się o prawdziwej przypadkowości?

— Suresh Venkat,

Myślę, że to trochę subiektywne - może tyle, ile popularna prasa mówi o kompletności NP? Ale tak, wydaje mi się, że losowość pojawia się w różnych kontekstach, ale zwykle nie ma rozróżnienia między pseudolosowością a (prawdziwą) losowością.

— Juho,

17

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.

— Aaron Roth
źródło

12

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

— kena
źródło

To miło. Też o tym myślałem.

— Suresh Venkat,

8

Tak naprawdę trzymam jeden z nich na mojej stronie: cg.scs.carleton.ca/~morin/misc/nortel

— Pat Morin

1

Poza tym, to NIE miało znaczenia :)

— Suresh Venkat,

4

wykładniczy przybiera znaczenie wszystkiego, co rośnie w sposób nieliniowy

— maniak zapadkowy

Słowo „wykładniczy” jest jednym z najbardziej nadużywanych. Oto kilka przykładów, które widziałem: „Liczba bramek strzelonych przez [niektórych piłkarzy] rośnie wykładniczo z każdego sezonu do następnego” , „Udało mi się wykładniczo poprawić swoje podejście do pracy w zespole lata ” , „ Liczba kanałów dostępnych za pośrednictwem telewizji satelitarnej jest wykładnicza ” .

— Giorgio Camerani

11

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$

— Sasho Nikolov
źródło

6

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.

— Timothy Chow
źródło

Myślę, że można argumentować, że „pedanteria” jest trafna. Wiele osób nie zna różnicy między sprzętem a oprogramowaniem (przynajmniej dla mnie naprawdę zaskakująca ilość). Dla niewtajemniczonych, skąd dokładnie pochodzi ulepszenie, można je zaklasyfikować jako pedanteria, chociaż wiemy, że istnieją ogromne różnice strukturalne i koncepcyjne.

— SamM

-7

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.

— vzn
źródło

9

Musisz podać odpowiedź w odpowiednim formacie :). Ale tak naprawdę uważam, że twoja odpowiedź nie jest właściwa. Ponieważ argument „komputer kwantowy może wypróbowywać wszystkie przypadki równolegle”, argument jest błędny na ważne sposoby i nie jest pomocny jako intuicja. Nie sądzę więc, by istniała wyższa „prawda moralna”

— Suresh Venkat,

5

Zgadzam się z @SureshVenkat, że komputer kwantowy przetwarzający wszystkie możliwości równolegle jest tak blisko prawdy moralnej, jak komputer probabilistyczny przetwarzający wszystkie możliwości równolegle. Jest całkowicie bezużyteczny dla intuicji i nie ma „prawdziwej” rzeczy, którą przybliża.

— Artem Kaznatcheev

4

Kiedy natrafiam na ludzi, którzy twierdzą, że QC może rozwiązać wszystkie możliwe dane wejściowe do problemu, zwykle odpowiadam: „OK, w porządku. Dostajesz jedną odpowiedź. Losowo. W jaki sposób upewniasz się, że to prawdopodobnie ta właściwa?”

— John Moeller

@ArtemKAznatcheev: Zdecydowanie powiedziałbym, że w tym uproszczeniu jest coś znaczącego. W obliczeniach kwantowych (w przeciwieństwie do obliczeń probabilistycznych) składowe stanu odpowiadające różnym możliwościom mogą (poprzez dalsze operacje liniowe) anulować się lub w inny sposób „zakłócać”. Zgadzam się, że ta intuicja nie idzie zbyt daleko w kierunku tego, co naprawdę się dzieje, ale idzie trochę dalej, a ja nie widziałem jeszcze żadnej drogi, by przejść dalej bez wchodzenia w rzeczywistą algebrę liniową, która dla większości czytelnicy byliby kompletnym wyłącznikiem.

— PLL

4

@PLL: w niedeterministycznej maszynie gałęzie też nie przeszkadzają. Chociaż więc podejrzewamy, że BQP jest ściśle większy niż BPP, to sprawia, że porównywanie komputera kwantowego z niedeterministyczną maszyną Turinga jest dokładnie niewłaściwym rodzajem porównania. Możesz spróbować zrobić (wciąż dość niechlujny) porównanie z Parity-P lub Gap-P, ale jakoś nie sądzę, aby to w ogóle pomogło ci przekazać, co komputery kwantowe robią bardzo dużo.

— Niel de Beaudrap,