Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

5
Historyczne przyczyny przyjęcia maszyny Turinga jako podstawowego modelu obliczeń.
Rozumiem, że model Turinga stał się „standardem” przy opisywaniu obliczeń. Interesuje mnie, dlaczego tak jest - to znaczy, dlaczego model TM stał się szerzej stosowany niż inne teoretycznie równoważne (o ile mi wiadomo) modele, na przykład μ-Recursion Kleene'a lub rachunek lambda (rozumiem to pierwsze pojawiło się dopiero później, a drugie …
22
Jakie znasz hierarchie i / lub twierdzenia dotyczące hierarchii?
Obecnie piszę ankietę na temat twierdzeń hierarchicznych dotyczących TCS. Szukając powiązanych artykułów zauważyłem, że hierarchia jest fundamentalną koncepcją nie tylko w TCS i matematyce, ale w wielu naukach, od teologii i socjologii po biologię i chemię. Widząc, że ilość informacji jest ogromna, mam nadzieję, że mógłbym poprosić o pomoc tę …
12
Gröbner bazuje w TCS?
Czy ktoś wie o ciekawych zastosowaniach baz Gröbnera w teoretycznej informatyce? Podstawy Gröbnera są używane do rozwiązywania wielowymiarowych równań wielomianowych, co jest ogólnie trudnym problemem NP. Zastanawiałem się, czy użyto niektórych możliwych do rozwiązania specjalnych przypadków w celu zapewnienia wydajnych algorytmów / konstrukcji / dowodów w obszarach TCS lub powiązanych …
3
Czy problem faktoryzacji liczb całkowitych jest trudniejszy niż faktoryzacja RSA:
To jest cross-post z math.stackexchange. Niech FACT oznaczają problemu faktoringowej całkowitą: podany znaleźć liczb pierwszych p i ∈ N , a całkowite e I ∈ N , tak, że N = Π k i = 0 p e ı ı .n∈N,n∈N,n \in \mathbb{N},pi∈N,pi∈N,p_i \in \mathbb{N},ei∈N,ei∈N,e_i \in \mathbb{N},n=∏ki=0peii.n=∏i=0kpiei.n = \prod_{i=0}^{k} p_{i}^{e_i}. …
7
Naprawdę generator liczb losowych: obliczanie Turinga?
Szukam ostatecznej odpowiedzi na pytanie, czy generowanie „prawdziwie losowych” liczb jest obliczalne przez Turinga. Nie wiem, jak to dokładnie sformułować. Pytanie StackExchange dotyczące „wydajnych algorytmów do generowania liczb losowych” jest bliskie odpowiedzi na moje pytanie. Charles Stewart mówi w swojej odpowiedzi: „To [losowości Martina-Löfa] nie może być wygenerowane przez maszynę”. …
1
Warunek do nauki GCT
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 „minimalnej wiedzy” do nauki tej teorii? Ta lista zawiera notatki …
9
Referencje dla technik proofingu TCS
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ę, czy jest coś, co traktuje techniki dowodzenia w szerszym …
5
Wyniki w teoretycznej CS niezależnej od ZFC
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 (+ niektóre inne aksjomaty), a dopiero później udowodnione …
7
Co wiemy o możliwych do udowodnienia poprawnych programach?
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 „kompilatorem certyfikującym” (znalazłem go tutaj ): kompilatorem kompilującym język programowania, w którym …
3
Czy istnieje zapasowe / zastępcze zoo złożoności?
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 to, że od dłuższego czasu nie działa. Zastanawiałem się, czy ktoś nadal go …
1
Mnożenie n wielomianów stopnia 1
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 drzewny. Czy możesz zrobić O ( n log n ) …
3
złożoność największego wspólnego dzielnika (gcd)
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ć referencje? W tym pytaniu nie interesują mnie przede wszystkim asymptotyczne …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.