Właśnie czytam rachunek lambda, żeby go „poznać”. Widzę to jako alternatywną formę obliczeń w przeciwieństwie do maszyny Turinga. Jest to interesujący sposób robienia rzeczy z funkcjami / redukcjami (z grubsza mówiąc). Niektóre pytania wciąż mnie dręczą: Jaki jest sens rachunku lambda? Po co...
Przepraszam za chwytliwy tytuł. Chcę zrozumieć, co należy zrobić, aby obalić tezę Turinga? Gdzieś czytam, że jest to matematycznie niemożliwe! Dlaczego? Turing, Rosser itp. Użyli różnych terminów, aby rozróżnić: „co można obliczyć” i „co można obliczyć za pomocą maszyny Turinga”. Definicja...
Jaka jest najśmieszniejsza opublikowana praca związana z TCS? Podaj tylko te, które mają być śmieszne. Preferowane są prace, które zostały stworzone z myślą o inteligentnym humorze (zamiast, powiedzmy, opublikowanym zbiorem krótkich dowcipów dotyczących teorii złożoności). Akceptowane są również...
Obecnie jestem studentem, który w tym roku musi ukończyć studia. Po ukończeniu studiów rozważam pracę w kierunku magistra / doktora TCS. Zacząłem się zastanawiać, jakie dziedziny matematyki są uważane za pomocne w TCS, zwłaszcza (klasyczna) teoria złożoności. Jakie dziedziny uważasz za niezbędne...
Jest to „pytanie historyczne” bardziej niż pytanie badawcze, ale czy klasyczne sprowadzenie do ustalania porządku w algorytmie Shora dla faktoryzacji zostało początkowo odkryte przez Petera Shora, czy też było wcześniej znane? Czy istnieje artykuł opisujący redukcję, która poprzedza Shora, czy jest...
W świetle ogłoszenia pierwszego na świecie programowalnego układu kwantowego , zastanawiałem się, jakie byłoby oprogramowanie dla komputera wykorzystującego splątanie kwantowe. Jeden z pierwszych programów, które napisałem, był podobny for i = 1 to 10 print i next i Czy ktoś może podać przykład...
To pytanie może nie pasować tutaj, ale nie mogłem znaleźć lepszego miejsca do zadawania pytań (zostało zamknięte w SO). Trudno mi zrozumieć prace badawcze z zakresu informatyki. Oczywiście tematy są skomplikowane. Ale po tym, jak rozumiem artykuł, zwykle mogę komuś to powiedzieć w prostszy sposób...
Proszę wymienić przykłady, w których twierdzenie matematyki, które normalnie nie było uważane za stosowane w informatyce, zostało po raz pierwszy wykorzystane do udowodnienia wyniku w informatyce. Najlepszymi przykładami są te, w których połączenie nie było oczywiste, ale kiedy zostało odkryte,...
W odpowiedzi na wcześniejsze pytanie wspomniałem o powszechnym, ale fałszywym przekonaniu, że eliminacja „gaussowska” przebiega w czasie . Chociaż oczywiste jest, że algorytm wykorzystuje operacje arytmetyczne , nieostrożna implementacja może tworzyć liczby z wykładniczo wieloma bitami. Jako prosty...
Jestem praktykiem oprogramowania i piszę ankietę na temat struktur algebraicznych do badań osobistych i staram się przedstawić przykłady wykorzystania tych struktur w informatyce teoretycznej (oraz, w mniejszym stopniu, w innych dziedzinach informatyki) . W ramach teorii grup natknąłem się na...
Matematycy czasem martwią się o aksjomat wyboru (AC) i aksjomat determinacji (AD). Aksjomat wyboru : Biorąc pod uwagę dowolny zbiór z niepustych zestawach jest funkcja , które, biorąc pod uwagę zestaw w , zwraca element z .CC{\cal C}fffSSSCC{\cal C}SSS Aksjomat Determinacji : Niech będzie...
Jakie są algorytmy legalnej użyteczności, które są po prostu zbyt skomplikowane, aby je zaimplementować? Wyjaśnię: nie szukam algorytmów takich jak obecny asymptotyczny algorytm optymalnego mnożenia macierzy (Coppersmith-Winograd), który jest rozsądny do wdrożenia, ale ma stałą, która czyni go...
Obecnie rozwiązanie NPNPNP pełnego NP lub PSPACEPSPACEPSPACE jest niewykonalne w ogólnym przypadku dużych nakładów. Jednak oba można rozwiązać w czasie wykładniczym i przestrzeni wielomianowej. Skoro nie jesteśmy w stanie zbudować niedeterministycznych lub „szczęśliwych” komputerów, czy ma to dla...
Pochodząc z matematyki, tak naprawdę nigdy nie nauczyłem się kodować. Zaczynam doktorat z TCS i wiele osób było zaskoczonych tym, jak mało wiedziałem o programowaniu (i ogólnie o komputerze). Mogę pisać algorytmy w pseudo-kodzie, ale tak naprawdę nie znam żadnego języka programowania. Mogę sobie...
Znam wiele wyników wykorzystujących twierdzenie PCP (głównie w algorytmach aproksymacyjnych), ale nigdy nie spotkałem się z jasnym wyjaśnieniem twierdzenia PCP (tj. Że ).N P = P C P (O(log( n ) ) , O ( 1 ) )NP=PCP(O(log(n)),O(1))\mathsf{NP} = \mathsf{PCP}(O(\log(n)),O(1)) Jakie są dobre artykuły...
Zadane pytanie dotyczy tego, czy rozstrzygające jest następujące pytanie: Problem Biorąc pod uwagę liczbę całkowitą i maszynę Turinga która ma być w P, to czy środowisko wykonawcze w odniesieniu do długości wejściowej ?M M O ( n k ) nkkkMMMMMM O(nk)O(nk){O}(n^k)nnn Dopuszczalna jest wąska...
Ostatnie pytanie za pytaniem, czy Huck Bennett PH klasa została zawarta w PP klasy, otrzymał nieco sprzecznych odpowiedzi (wszystko prawda, wydaje się). Z jednej strony podano przeciwnie kilka wyników wyroczni, z drugiej Scott zasugerował, że odpowiedź jest prawdopodobnie pozytywna, ponieważ...
EDYCJA PRZY 10/12/08: Spróbuję zmodyfikować pytanie, aby zainteresować większą liczbą osób dzieleniem się opiniami. POTRZEBUJEMY twoich datków! Ten post jest inspirowany jednym z MO: Przykłady powszechnych fałszywych przekonań w matematyce . Wielkie listy czasami generują ogromną liczbę...
Zaktualizowano poniżej Wszyscy znamy kluczowe znaczenie wzajemnej oceny. Jest to główna forma kontroli jakości i informacji zwrotnej na temat badań. Jednak dla początkującego badacza (takiego jak ja) może to być czasem mylący system / proces. W związku z tym istnieje kilka traktatów na temat...
Często, gdy bierzemy udział w konferencjach TCS, zauważamy kilka drobiazgów, którymi chcielibyśmy się zająć organizatorzy konferencji. A kiedy organizujemy konferencje, już o tym zapomnieliśmy. Stąd pytanie: jakie małe kroki moglibyśmy łatwo podjąć, aby usprawnić konferencje TCS ? Mam nadzieję,...