Teoretyczne informatyka

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

3
Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?
W przypadku problemu maksymalnego przepływu wydaje się, że istnieje wiele bardzo wyrafinowanych algorytmów, przy czym co najmniej jeden opracowano dopiero w zeszłym roku. Max przepływy Orlina w czasie O (mn) lub lepiej daje algorytm działający w O (VE). Z drugiej strony algorytmy, które najczęściej widzę, są zaimplementowane (nie twierdzę, że …
6
Czy istnieje naturalny problem natury naturalnej, który jest NP-zupełny?
Dowolną liczbę naturalną można traktować jako sekwencję bitową, więc wprowadzenie liczby naturalnej jest takie samo, jak wprowadzenie sekwencji 0-1, więc oczywiście występują problemy NP-zupełne z wejściami naturalnymi. Ale czy są jakieś naturalne problemy, tzn. Takie, które nie używają kodowania i specjalnej interpretacji cyfr? Na przykład „Czy na pierwsze?” jest takim …
10
Świetne algorytmy, uczenie maszynowe i brak algebry liniowej
Prowadzę kurs zaawansowanych algorytmów i chciałbym uwzględnić niektóre tematy związane z uczeniem maszynowym, które zainteresują moich studentów. W związku z tym chciałbym usłyszeć opinie ludzi na temat najbardziej interesujących / największych wyników algorytmicznych w uczeniu maszynowym. Potencjalnie trudnym ograniczeniem jest to, że uczniowie nie będą mieli żadnej konkretnej wcześniejszej wiedzy …
4
Czy hałaśliwa wersja gry życia Conwaya obsługuje uniwersalne obliczenia?
Cytując Wikipedię , „[Gra życia Conwaya] ma moc uniwersalnej maszyny Turinga: to znaczy wszystko, co można obliczyć algorytmicznie, można obliczyć w ramach Gry życia Conwaya”. Czy takie wyniki obejmują hałaśliwe wersje Gry życia Conwaya? Najprostsza wersja jest taka, że ​​po każdej rundzie każda żywa komórka umiera z małym prawdopodobieństwem a …
2
Czy { } nie jest kontekstowe?
Czy język { } jest bezkontekstowy?zajabjotdok | i≠j,i≠k,j≠k aibjck | i≠j,i≠k,j≠ka^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k Uświadomiłem sobie, że spotkałem prawie wszystkie warianty tego pytania z różnymi warunkami dotyczącymi związku między i, j i k, ale nie tym. Domyślam się, że nie jest pozbawiony kontekstu, …
2
Geneza i zastosowania teorii A vs. teorii B?
W kilku ostatnich pytaniach ( q1 q2 ) omawiano „Teorię A” vs. „Teorię B”, najwyraźniej w celu uchwycenia podziału między nauką logiki i języków programowania a badaniem algorytmów i złożoności. Ta terminologia była dla mnie nowa, a szybkie wyszukiwanie w Internecie nie przyniosło żadnych oczywistych referencji. Czy ktoś wie o …
7
Czy powinniśmy uznać
Wielu ekspertów uważa, że hipoteza jest prawdziwa i wykorzystuje ją w swoich wynikach. Obawiam się, że złożoność silnie zależy od hipotezy .P≠NPP≠NP\mathsf{P} \neq \mathsf{NP}P≠NPP≠NP\mathsf{P} \neq \mathsf{NP} Więc moje pytanie brzmi: Dopóki hipoteza nie zostanie udowodniona, czy można / należy uznać ją za prawo natury, jak wskazano w cytacie ze Strassen? …
2
Hierarchie w NP (przy założeniu, że P! = NP)
Zakładając, że P! = NP, uważam, że wykazano, że istnieją problemy, których nie ma w P, a nie w NP-Complete. Przypuszcza się, że takim problemem jest izomorfizm grafów. Czy są jakieś dowody na istnienie większej liczby takich „warstw” w NP? tzn. Hierarchia złożona z więcej niż trzech klas, rozpoczynająca się …
2
Czy istnieje algorytm wielomianowy do określania, czy rozpiętość zbioru macierzy zawiera macierz permutacji?
Chciałbym znaleźć algorytm wielomianowy, który określa, czy rozpiętość danego zestawu macierzy zawiera macierz permutacji. Jeśli ktoś wie, czy ten problem ma inną klasę złożoności, byłoby to równie pomocne. EDYCJA: Oznacziłem to pytanie za pomocą programowania liniowego, ponieważ mam poważne podejrzenia, że ​​gdyby istniało takie rozwiązanie, byłby to rodzaj algorytmu programowania …
4
Czy istnieją „małe” maszyny, które mogą skutecznie dopasowywać wyrażenia regularne?
Dobrze wiadomo, że wyrażenie regularne może zostać rozpoznane przez niedeterministyczny automat skończony o wielkości proporcjonalnej do wyrażenia regularnego lub przez deterministyczny FA, ​​który jest potencjalnie większy wykładniczo. Ponadto, biorąc pod uwagę ciąg i wyrażenie regularne , NFA może przetestować członkostwo w czasie proporcjonalnym do | s | \ cdot | …
3
Uzasadnienie logarytmu f w twierdzeniu o hierarchii DTIME
Jeśli spojrzymy na twierdzenie o hierarchii DTIME, mamy dziennik z powodu narzutu w symulacji deterministycznej maszyny Turinga przez maszynę uniwersalną: DTIME(flogf)⊊DTIME(f)DTIME(flog⁡f)⊊DTIME(f)DTIME(\frac{f}{\log f}) \subsetneq DTIME(f) Nie mamy tego rodzaju kosztów ogólnych dla NTIME DSPACE. Podstawowe uzasadnienie wynika ze szczegółów dowodu, biorąc pod uwagę różnicę między symulatorami. Moje pytanie jest następujące: bez …
10
Aktualne modele równoległe do obliczeń
Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90. Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń równoległych? Czy ogólne modele są …
2
Czy jakieś algorytmy kwantowe poprawiają klasyczne SAT?
Klasyczne algorytmy mogą rozwiązać 3-SAT w czasie (losowo) lub (deterministycznie). (Odnośnik: najlepsze górne granice na SAT )1,3303 n1,3071n1.3071n1.3071^n1,3303n1.3303n1.3303^n Dla porównania, użycie algorytmu Grovera na komputerze kwantowym i zapewniło rozwiązanie w losowaniu losowym . (Może to nadal wymagać pewnej wiedzy o tym, ile rozwiązań może istnieć, ale nie jestem pewien, jak …
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.