Jakie są teoretyczne wyjaśnienia praktycznego sukcesu solverów SAT i czy ktoś może dać przegląd i wyjaśnienie w stylu „wikipedii” łącząc je wszystkie? Analogicznie, wygładzona analiza ( wersja arXiv )) dla algorytmu simplex świetnie się tłumaczy, dlaczego działa tak dobrze w praktyce, mimo że w...
Czy są jakieś korzyści z obliczania złożoności czasowej algorytmu za pomocą rachunku lambda? Czy istnieje inny system zaprojektowany do tego celu? Wszelkie referencje będą mile
Gdybyś mógł zmienić nazwę programowania dynamicznego, jak byś to
Mam na myśli następujący problem: Chcę znaleźć wyrażenie regularne, które pasuje do określonego zestawu ciągów (np. Prawidłowe adresy e-mail) i nie pasuje do innych (nieprawidłowe adresy e-mail). Załóżmy, że przez wyrażenie regularne rozumiemy dobrze zdefiniowaną maszynę skończoną, nie znam...
Wydaje się jasne, że na wiele podpól teoretycznej informatyki istotny wpływ wywarły wyniki fizyki teoretycznej. Oto dwa przykłady Obliczenia kwantowe Wyniki mechaniki statystycznej stosowane w analizie złożoności / algorytmach heurystycznych. Więc moje pytanie brzmi: czy brakuje mi jakichś...
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,...
Zainspirowany tym pytaniem, a w szczególności ostatnim akapitem odpowiedzi Or, mam następujące pytanie: Czy znasz jakieś zastosowania teorii reprezentacji grupy symetrycznej w TCS? Grupa symetryczna SnSnS_n jest grupą wszystkich permutacji {1,…,n}{1,…,n}\{1, \ldots, n\} o składzie operacji...
Prawdziwe komputery mają ograniczoną pamięć i tylko skończoną liczbę stanów. Są to w zasadzie skończone automaty. Dlaczego informatycy teoretyczni używają maszyn Turinga (i innych równoważnych modeli) do badania komputerów? Jaki jest sens studiowania tych znacznie silniejszych modeli w odniesieniu...
Na MathOverflow Timothy Gowers zadał pytanie zatytułowane „ Wykazanie, że rygor jest ważny ”. Większość dyskusji dotyczyła przypadków pokazujących wagę dowodu, o których ludzie w CSTheory prawdopodobnie nie muszą być przekonani. Z mojego doświadczenia wynika, że dowody muszą być bardziej...
W 1937 r. Turing opisał maszynę Turinga. Od tego czasu opisano wiele modeli obliczeń, próbując znaleźć model, który jest jak prawdziwy komputer, ale wciąż wystarczająco prosty do projektowania i analizy algorytmów. W rezultacie mamy kilkanaście algorytmów dla np. Problemu SORT dla różnych modeli...
Teoretycznie jestem studentem drugiego roku. Pracowałem nad problemem przez ostatni rok (w teorii grafów / algorytmach). Do wczoraj myślałem, że mam się dobrze (przedłużałem twierdzenie z artykułu). Dziś zdałem sobie sprawę, że popełniłem prosty błąd. Zrozumiałem, że zrobienie tego, co zamierzałem,...
Dziedzina przetwarzania rozproszonego okazała się bardzo krótka w opracowaniu jednej teorii matematycznej opisującej algorytmy rozproszone. Istnieje kilka „modeli” i struktur obliczeń rozproszonych, które po prostu nie są ze sobą kompatybilne. Sama eksplozja różnych właściwości czasowych...
To pytanie dotyczy złożoności obwodu. (Definicje znajdują się na dole). Yao Beigel-Tarui wykazała, że każdy C C 0 rodziny obwód wielkość y jest równoważny rodziny obwodu o rozmiarze s s O l r ( log s ) głębokości dwóch , w którym brama wyjściowa jest funkcją symetryczną, a drugi etap składa od N D...
To pytanie jest z tym związane . Po wielu rozmowach po raz kolejny, w znacznie prostszej formie, wydawało się, że to zupełnie inne pytanie. Klasyczny dowód nierozstrzygalności problemu zatrzymania zależy od wykazania sprzeczności przy próbie nałożenia na siebie hipotetycznego decydenta HALT....
W klasycznym artykule Andrew Chi-Chiha Yao z 1979 r. Nawiązuje do „MO Rabin i AC Yao w przygotowaniu”. Wynika to z tego, że złożoność komunikacji z błędem ograniczonym funkcji równości EQ (czy dwie liczby całkowite z zakresu od do są równe) wynosi .NN_N000N−1N−1N-1O(loglogN)O(loglogN)O(\log\log...
Chciałbym zrozumieć Applicativew kategoriach teorii kategorii. Dokumentacja dla Applicativetwierdzi, że jest to silny funktor LAX monoidal . Po pierwsze, strona Wikipedii o funktorach monoidalnych mówi, że funktor monoidalny jest luźny lub silny . Wydaje mi się więc, że jedno ze źródeł jest...
Moje pytanie jest proste: Jaki jest najgorszy czas z najbardziej znanych algorytm działa dla wyliczania eigendecomposition danego matrycy?n×nn×nn \times n Czy skład eigend redukuje się do mnożenia macierzy, czy w najgorszym przypadku są najlepiej znanymi algorytmami (przez SVD...
Problemem wykres Izomorfizm (Gl) jest prawdopodobnie najbardziej znanym kandydatem na NP pośredniego problemu. Najbardziej znanym algorytmem jest algorytm subwykładniczy z czasem działania . Wiadomo, że GI nie jest -kompletny, chyba że hierarchia wielomianowa się
tło Obliczenia na liczbach rzeczywistych są bardziej skomplikowane niż obliczenia na liczbach naturalnych, ponieważ liczby rzeczywiste są obiektami nieskończonymi i istnieje niezliczona liczba liczb rzeczywistych, dlatego liczb rzeczywistych nie można wiernie przedstawić za pomocą ciągów...
Czy każda funkcja która jest obliczalna w czasie t na maszynie Turinga z pojedynczą taśmą, używając alfabetu wielkości k = O ( 1 ), może być obliczona w czasie O ( t ) na single-taśma maszyna Turinga za pomocą alfabetu wielkości 3 (powiedzmy, 0 , 1 , i puste)?fa: { 0 , 1 }∗→ { 0 , 1...