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ń...
Czy ktoś odważy się wyjaśnić, jaki jest związek tych kierunków studiów, czy może nawet bardziej konkretną odpowiedź na poziomie problemów? Który obejmuje, który obejmuje niektóre powszechnie akceptowane formulacje. Jeśli dobrze to zrozumiałem, przechodząc z SAT do SMT, po prostu wchodzisz w pole...
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...
Biorąc pod uwagę liczbę całkowitą długości n bitów, jak trudne jest wyprowadzenie liczby czynników pierwszych (lub alternatywnie liczby czynników) N ?N.NNnnnN.NN Gdybyśmy znali podstawową faktoryzację , byłoby to łatwe. Gdybyśmy jednak znali liczbę czynników pierwszych lub liczbę czynników...
Ograniczonym nondeterminism łączy funkcję z klasy języków akceptowanych przez deterministycznych maszyny Turinga zasobach ograniczona, w celu utworzenia nowej klasy - . Ta klasa składa się z tych języków, które są akceptowane przez jakąś niedeterministyczną maszynę Turinga przestrzegającą tych...
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
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...
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...
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...
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 /...
Pewne paradoksy matematyczne i logiczne można prawdopodobnie automatycznie zastosować do komputerów, ale czy istnieją jakieś paradoksy odkryte w samej informatyce? Przez paradoksy rozumiem sprzeczne z intuicją wyniki, które wyglądają jak
Jakie byłyby paskudne konsekwencje NP = PSPACE? Dziwi mnie, że nie znalazłem nic na ten temat, biorąc pod uwagę, że zajęcia te należą do najbardziej znanych. W szczególności, czy miałoby to jakiekolwiek konsekwencje dla klas
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...
Zdefiniuj ioioio - jako klasę języków taką, że istnieje język i dla nieskończenie wielu , i zgadzają się we wszystkich przypadkach długości n . (To jest klasa języków, które można „rozwiązywać nieskończenie często, w podwykonawczym czasie”).SUBEXPSUBEXPSUBEXPL ′ ∈ ∩ ε >...
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...
Powszechnie wiadomo, że losowy spacer w dwuwymiarowej siatce powróci do początku z prawdopodobieństwem 1. Wiadomo również, że ten sam losowy spacer w TRZY wymiarach ma prawdopodobieństwo mniej niż 1 powrotu do początku . Moje pytanie brzmi: Czy jest coś pomiędzy? Załóżmy na przykład, że moja...
Czy są jakieś (funkcjonalne?) Języki programowania, w których wszystkie funkcje mają formę kanoniczną? Oznacza to, że dowolne dwie funkcje, które zwracają te same wartości dla całego zestawu danych wejściowych, są reprezentowane w ten sam sposób, np. Jeśli f (x) zwrócił x + 1, a g (x) zwrócił x +...
W jednym zdaniu: czy istnienie hierarchii dla oznaczałoby jakiekolwiek wyniki derandomizacji?BPTIMEbP.T.jaM.mi\mathsf{BPTIME} Powiązane, ale niejasne pytanie brzmi: czy istnienie hierarchii dla implikuje jakieś trudne dolne granice? Czy rozwiązanie tego problemu uderza w znaną barierę w teorii...
Jestem początkującym pracującym nad metodami potwierdzającymi równoważność programu. Przeczytałem kilka artykułów na temat definiowania relacji logicznych lub symulacji, aby udowodnić, że dwa programy są równoważne. Ale jestem dość zdezorientowany co do tych dwóch technik. Wiem tylko, że relacje...
Łatwo zauważyć, że izomorfizm wykresu (GI) występuje w NP. Poważnym otwartym problemem jest to, czy GI jest w CoNP. Czy są potencjalni kandydaci właściwości grafów, które można wykorzystać jako certyfikaty CoNP dla GI? Jakieś przypuszczenia, które sugerują, że ? Jakie są implikacje...