Wydaje się, że Teoria Złożoności Geometrycznej wymaga dużej wiedzy na temat czystej matematyki, takiej jak geometria algebraiczna, teoria reprezentacji. Chociaż jestem studentem CS i NIE mam zajęć z bardzo abstrakcyjnej i czystej matematyki, interesuje mnie ten program. Czy istnieje lista...
Czy są jakieś odniesienia (online lub w formie książkowej), które organizują i omawiają twierdzenia TCS techniką dowodową? Garey i Johnson robią to dla różnych rodzajów konstrukcji widżetów potrzebnych do potwierdzenia kompletności NP (szczególnie w rozdziale 3 ich książki), ale zastanawiam się,...
Coraz większa złożoność programów komputerowych i coraz ważniejsza pozycja komputerów w naszym społeczeństwie sprawia, że zastanawiam się, dlaczego nadal nie używamy zbiorowo języków programowania, w których musisz formalnie udowodnić, że kod działa poprawnie. Uważam, że termin ten jest...
Zadam dość niejasne pytanie, ponieważ granica między informatyką teoretyczną a matematyką nie zawsze jest łatwa do rozróżnienia. PYTANIE: Czy znasz jakieś interesujące wyniki w CS, które są albo niezależne od ZFC (tj. Standardowa teoria zbiorów), albo które zostały pierwotnie udowodnione w ZFC (+...
Szereg problemów geometrycznych jest łatwych, gdy rozważa się je w , ale są NP-kompletne w R d dla d ≥ 2 (w tym jeden z moich ulubionych problemów, pokrywa dysku jednostki).R1R1R^1RdRdR^dd≥2d≥2d\geq2 Czy ktoś wie o problemie, który jest polytime rozwiązywalne dla i R 2 , ale NP-zupełny dla R d , d...
To pytanie nietechniczne, ale z pewnością istotne dla społeczności TCS. Jeśli zostanie to uznane za niewłaściwe, możesz je zamknąć. Witryna Zoo Complexity Zoo (http://qwiki.stanford.edu/index.php/Complexity_Zoo) z pewnością od lat cieszy się dużą popularnością wśród społeczności TCS. Wygląda na...
Ogólnie wiemy, że złożoność testowania, czy funkcja przyjmuje określoną wartość na danym wejściu, jest łatwiejsza niż ocena funkcji na tym wejściu. Na przykład: Ocena stałej nieujemnej liczby całkowitej jest # P-trudna, ale powiedzenie, czy taka stała jest zerowa czy niezerowa jest w P...
Problem polega na obliczeniu wielomianu . Załóżmy, że wszystkie współczynniki mieszczą się w słowie maszynowym, tzn. Można nimi manipulować w czasie jednostkowym.(a1x+b1)×⋯×(anx+bn)(a1x+b1)×⋯×(anx+bn)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Możesz zrobić czas , stosując FFT w sposób...
Rozważ następujący problem zliczania (lub związany z tym problem decyzyjny): Biorąc pod uwagę dwie dodatnie liczby całkowite zakodowane w systemie binarnym, oblicz ich największy wspólny dzielnik (gcd). Jaka jest najmniejsza klasa złożoności, w której występuje ten problem? Czy możesz podać...
Patrzenie na pytania przez obiektyw algorytmiczny (tj. Z punktu widzenia algorytmu lub złożoności) stało się przydatne w dyscyplinach poza „standardową dziedziną” informatyki. W szczególności CS wywarł wpływ na biologię poprzez biologię obliczeniową, na fizykę poprzez kwantowe przetwarzanie...
Potrzebuję skończonej książki z teorią automatów z wieloma przykładami, które mogę wykorzystać do samodzielnej nauki i przygotowania się do
Chociaż zdałem kilka kursów z teorii prawdopodobieństwa, zarówno w szkole średniej, jak i na uniwersytecie, trudno mi czytać artykuły TCS, jeśli chodzi o prawdopodobieństwo. Wydaje się, że autorzy artykułów TCS są bardzo dobrze zaznajomieni z prawdopodobieństwem. Magicznie działają ze wzorami...
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez...
Czytałem „ Semantykę z aplikacjami ” Nielsona i Nielsona i bardzo podoba mi się ten temat. Chciałbym mieć jeszcze jedną książkę na temat semantyki języka programowania - ale naprawdę mogę dostać tylko jedną. Rzuciłem okiem na książkę Turbak / Gifford , ale jest ona zbyt długa; Myślałem, że Winskel...
Nie wydaje się, żeby to było znane - ale czy są jakieś interesujące dolne granice złożoności mnożenia macierzy w modelu obliczeń kwantowych? Czy mamy intuicję, że możemy pokonać złożoność algorytmu Coppersmith-Winograd za pomocą komputerów
Metody wielomianowe , powiedzmy twierdzenie kombinatoryczne Nullstellensatz i twierdzenie Chevalleya-Ostrzegania, są potężnymi narzędziami w kombinatywnej addytywności. Reprezentując problem z właściwymi wielomianami, mogą zagwarantować istnienie rozwiązania lub liczbę rozwiązań wielomianów....
W swojej książce Boolean Function Complexity Stasys Jukna wspomina (strona 564), że Kołmogorow wierzył, że każdy język w P ma obwody o wielkości liniowej. Nie ma wzmianki o referencjach i nie mogłem znaleźć niczego online. Czy ktoś wie o tym
Znam tylko dwa dowody lematu Schwartza – Zippela. Pierwszy (bardziej powszechny) dowód został opisany we wpisie na Wikipedii . Drugi dowód odkryła Dana Moshkovitz. Czy są jakieś inne dowody, które wykorzystują zasadniczo różne pomysły?
Właśnie nauczyłem losowego algorytmu skrótu Karger-Stein w mojej klasie algorytmów dla absolwentów. To prawdziwy klejnot algorytmiczny , więc nie mogę tego nie uczyć, ale zawsze denerwuje mnie, ponieważ nie znam innych zastosowań głównej techniki. (Trudno więc przypisać pracę domową, która...
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy...