Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

8
Najlepsze górne granice na SAT
W innym wątku Joe Fitzsimons zapytał o „najlepsze obecne dolne granice 3SAT”. Chciałbym pójść w drugą stronę: jakie są najlepsze obecne górne granice 3SAT? Innymi słowy, jaka jest złożoność czasowa najbardziej wydajnego solvera SAT? W szczególności, czy można sobie wyobrazić algorytm subwykładniczy (a jednak super-wielomianowy) dla SAT?
4
Czy znalezienie minimalnego wyrażenia regularnego jest problemem NP-zupełnym?
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 dokładnej terminologii, ale uzgodnijmy pewną klasę dozwolonych wyrażeń. Zamiast ręcznie tworzyć …
12
Zastosowania teorii reprezentacji grupy symetrycznej
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 grupowych. Przedstawienie SnSnS_n jest homomorfizmem z SnSnS_n ogólnej grupy liniowego odwracalnych n×nn×nn \times n …
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ę …
16
Wyniki fizyki w TCS?
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ś głównych obszarów? Moja motywacja jest bardzo prosta: jestem fizykiem teoretycznym, który przybył …
10
Prawdziwe komputery mają tylko skończoną liczbę stanów, więc jakie jest znaczenie maszyn Turinga dla prawdziwych komputerów?
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 do prawdziwych komputerów? Dlaczego model automatów skończonych nie wystarczy?
8
Co robisz, gdy nie możesz zrobić postępu w sprawie problemu, nad którym pracowałeś?
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, będzie znacznie trudniejsze niż myślałem. Tak bardzo się rozczarowałem, …
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 …
4
Dlaczego nie udało nam się opracować jednolitej teorii złożoności obliczeń rozproszonych?
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 (asynchronia, synchronizacja, synchronizacja częściowa), różne prymitywy komunikacyjne (przekazywanie wiadomości w stosunku do pamięci współużytkowanej, transmisja …
8
Rygor prowadzący do wglądu
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 rygorystyczne w informatyce teoretycznej niż w wielu częściach ciągłej matematyki, …
1
Znaczenie prac jednego autora?
Jestem doktorantem czwartego roku informatyki teoretycznej. Chciałbym zostać w środowisku akademickim, więc myślę o tym, jak najlepiej rozwinąć swoją karierę. Oczywiście najlepszym sposobem na zrobienie tego jest napisanie wielu dobrych prac, ale inne pytanie brzmi, czy powinienem starać się, aby więcej z tych prac było jednym autorem. Do tej pory …
3
Jak znaleźć ciekawe problemy badawcze
Mimo kilku lat zajęć wciąż nie mogę się zdecydować na temat badań. Przeglądałem artykuły z różnych dziedzin i rozmawiałem z profesorami i zaczynam myśleć, że to niewłaściwe podejście. Czytałem, że pomaga znaleźć interesujący problem (bez względu na obszar), a następnie pracować nad tym. Podręczniki wspominają o znanych nierozwiązanych, ale nie …
3
Konsekwencje quasi-wielomianowego algorytmu czasowego dla problemu izomorfizmu grafowego
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ę załamie.2O(nlogn√)2O(nlog⁡n)2^{O(\sqrt{n \log n})}NPNP\mathsf{NP} Jakie byłyby teoretyczne konsekwencje złożoności quasi-wielomianowego algorytmu czasowego dla problemu grafowego izomorfizmu? Czy …
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.