Jak uzyskać „intuicję fizyczną” dla wyników w TCS?

Przepraszam, jeśli to pytanie jest trochę niejasne, ale jestem ciekawy, jak odnoszący sukcesy badacze „odczuwają” wyniki w TCS.

Na przykład algebra liniowa może być rozumiana geometrycznie lub w kategoriach jej fizycznych interpretacji (wektory własne można traktować jako „punkty stabilne” w systemie) itp. Intuicyjne jest również, że istnieje protokół IP dla TQBF (jako IP protokół może być zwizualizowany jako rodzaj „gry” między dwiema jednostkami o bardzo różnej mocy obliczeniowej). Uważam jednak, że wiele wyników, nawet bardzo podstawowych w TCS, nie ma tak prostych intuicji (MA AM). Co gorsza, czasami nierafinowane intuicje stają się strasznie ostrożne (2-SAT jest w P, podczas gdy 3-SAT nie jest uważany za w P (w rzeczywistości jest NP-kompletny)). Czy są jakieś „ogólne zasady” dotyczące rozwijania intuicji w TCS?$\subseteq$

Podobnie jak wiele dziedzin naukowych, zbudowanie intuicji może zająć lata, ale wystarczy jeden nowy pomysł, aby ją zniszczyć (i mam nadzieję, że coś miłego zostanie odbudowane na jej miejscu).

Istnieje kilka podstawowych ćwiczeń, których możesz użyć, aby zbudować intuicję dla czytanego papieru i nie możesz go przeniknąć. Oto coś, co wciąż robię od czasu do czasu. Zacznij od dowodu, którego nie rozumiesz, ale naprawdę chciałbyś, co jest bardzo długie. Czytając każdy akapit dowodu, spróbuj napisać zdanie na marginesie własnymi słowami o tym, co według niego mówi akapit. Mam nadzieję, że dowód został napisany wystarczająco dobrze, aby w dowodzie były dobrze zdefiniowane „części” („wykonaj X, a następnie zdefiniuj nową funkcję f, a następnie zastosuj X do f, ...”). Jeśli nie, to podziel zdania ze swoich zdań na własne zdania.

$MA \subseteq AM$, Powiedziałbym coś w stylu „MÓW ARTHUR MÓW WIĘCEJ”. Ale może coś innego w dowodzie wydaje się być „kluczowym” pomysłem dla Ciebie, co jest całkowicie w porządku. To twoja intuicja!)

Myślę, że moja sugestia może być przydatna w przypadku większości matematyki, ale uważam ją za bardzo przydatną w TCS, gdzie wiele dowodów naprawdę sprowadza się do 1-2 naprawdę nowych pomysłów, a reszta to synteza tego pomysłu z tym, co już było znane.

Uważaj na intuicję. Pochodzi z dużym doświadczeniem, często może się mylić i mieć rację w tym samym czasie i nie jest wyjątkowy. Chodzi o to, że każdy wnosi własną intuicję do problemów w oparciu o własne strefy komfortu, potrzeby problemu i ich pochodzenie. Jak zauważa Tsuyoshi, intuicja to naprawdę dużo ciężkiej pracy, która została sublimowana w kilku zwięzłych obrazach mentalnych.

Tak więc moja sugestia brzmiałaby: po prostu pracuj nad problemami, które lubisz, i staraj się rozwijać własne pomysły, nawet jeśli istnieją inne prace. W ten sposób zbudujesz intuicję. A jeśli wynik wydaje się zagadkowy, oznacza to, że jeszcze go nie zrozumiałeś, albo może gdzieś pod nim czai się prostszy wynik, czekający na odkrycie.

Ponieważ liczysz gry jako przykład „intuicji fizycznej”, podczas gdy ja nie widzę nic związanego z fizyką w grach, zakładam, że nie kładziesz nacisku na „fizyczność”, ale na „intuicję”.

Twierdzę, że celem studiów (edukacji lub badań) w informatyce teoretycznej jest rozwijanie intuicji dla abstrakcyjnych pojęć związanych z obliczeniami. Intuicję nabywa się poprzez studiowanie i zapoznanie się z koncepcją. Nie oczekuję, że jest ładny skrót.

Na przykład studenci studiów licencjackich będą zaskoczeni nierozstrzygalnością problemu zatrzymania (prawdopodobnie dlatego, że samo istnienie nierozstrzygalnego języka jest już zaskakujące). Ale poznanie faktu, jego dowodu, niektórych powiązanych wyników i szerokiego zastosowania techniki dowodu sprawia, że ​​ten zaskakujący wynik jest mniej zaskakujący, a w rzeczywistości bardzo naturalny. Uważam, że to samo dotyczy bardziej skomplikowanych wyników.

Jeśli chodzi o konkretny wynik, nie zgadzam się, że dla MA⊆AM nie ma prostej intuicji. (Ostrzeżenie: obecnie badam to i powiązane wyniki i mogę powiedzieć coś niepoprawnego.) W systemie magisterskim Merlin musi udzielić jednej odpowiedzi, która pasuje do większości losowych sekwencji używanych przez Artura. Zmieniamy system tak, że Arthur wysyła kilka (wielomianowo) losowych sekwencji do Merlina, a Merlin musi udzielić jednej odpowiedzi, która pasuje do wszystkich, co wydaje mi się naturalną rzeczą do wypróbowania. Udowodnienie solidności tego systemu AM jest prostą aplikacją związaną z Chernoffem. Nie sądzę, aby cokolwiek w tym wyniku było koncepcyjnie trudne do zrozumienia.

Powiązane marginalnie: Twoje pytanie przypomniało mi piękny wpis na blogu „ Abstrakcja, intuicja i„ błędny samouczek monady ”autorstwa Brenta Yorgeya, w którym wyjaśnił on trudność w komunikowaniu intuicji fikcyjnym nie wyjaśniającym„ Monady to burrito ”. Jeśli powyższe wyjaśnienie, w jaki sposób działa dowód MA doesAM, nie ma żadnego sensu, być może wykażę ten sam błąd. :(

Jeśli spędzasz pięć lat swojego życia studiując czysto teoretyczną koncepcję X (np. Pewien ezoteryczny model obliczeń), to ostatecznie X stanie się naturalną częścią twojego codziennego życia.

Nauczysz się wiedzieć, jak zachowuje się X, jak to jest, jak reaguje na twoje manipulacje oraz w jakiej dzielnicy mieszka. Dowiesz się, kto to odkrył, kiedy i dlaczego oraz co inni zrobili z X, z powodzeniem lub bez powodzenia. Poznasz X tak, jak znasz każdy przedmiot fizyczny, z którym spotykasz się każdego dnia.

Rzeczywiście, możesz znać to znacznie lepiej niż te dziwne, niezdefiniowane, nieprzewidywalne i chaotyczne rzeczy fizyczne ... Ale to długa droga i nie sądzę, że istnieje wiele magicznych skrótów.

Odpowiedzi tutaj obejmują już większość miłych sugestii dotyczących intuicji. Dałbym jeszcze jeden, co przydaje się przy rozwijaniu intuicji podczas pisania na papierze. Sugeruje to mój własny nauczyciel, Hsueh-I Lu, który uznałem za bardzo przydatny.

Ilekroć wynik jest zapisywany, a poprawność wydaje się zweryfikowana, przepisz cały artykuł . Tym razem musimy się zmusić, aby nie używać żadnych słów ani definicji podobnych do poprzednich wersji. To sprawia, że ​​myślimy w zupełnie nowy sposób i rozwijają się nowe intuicje. Ponadto zaburz wszystkie parametry użyte w dokumencie, zobacz, czy jakikolwiek zestaw parametrów różni się od tego, którego użyliśmy pierwotnie, nadal działa. Często pojawiają się błędy podczas przepisywania artykułu. Wymyśl nowe pomysły, aby je pokonać.

Wreszcie, po rundach przepisywania, będziemy mieli przyjemną okrągłą intuicję na temat własnego wyniku i nie będziemy zbyt optymistyczni / pesymistyczni wobec siły nowych pomysłów przedstawionych w artykule, ponieważ jesteśmy próbowani przez kilka razy i jasne jest, że to, co działa, a co nie.

Ta sama metoda działa, jeśli czytasz nowy artykuł i chcesz uzyskać więcej intuicji innych niż podane przez czytanie.

W moim przypadku większość koncepcji TCS, o których myślę, że mam jakąś intuicję, to te, na których poparłem dzięki praktycznym wynikom. Jeśli przez lata ewoluuję i z powodzeniem korzystam z tego samego modelu lub algorytmu, to coraz bardziej doprowadzam mnie do rozproszenia, dopóki nie będę w stanie dowiedzieć się, dlaczego algorytm się powiódł. Jest to szczególnie prawdziwe, jeśli nadszedł czas na przepisanie - chcę wiedzieć, czym jest esencja TCS, aby nie stracić magicznego pyłu podczas refaktoryzacji. Zrozumienie tego wszystkiego zwykle wymaga (dla mnie) głębokiego nurkowania od około 1936 roku i powiązania tego, co zrobiłem z tymi podstawowymi pojęciami. Znajomy doradził mi kiedyś, żebym „pomyślał jak maszyna Turinga”, kiedy byłem na jednym z tych nurkowań, i ta rada utkwiła we mnie.