Pytania otagowane jako reference-request

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

2
Złożoność homogenizacji łańcucha
Motywacja : Opracowując narzędzia do wersjonowania danych, zaczęliśmy szukać algorytmów do „różnicowania” dwóch zestawów liczb całkowitych, wymyślając sekwencję przekształceń, które przenoszą jeden zestaw liczb całkowitych na drugi. Udało nam się zredukować ten problem do następującego bardzo naturalnego problemu, który wydaje się mieć połączenia do edycji odległości, grupowania przez zamianę i …
1
Złożoność osiągalności w liniowych układach dynamicznych nad polami skończonymi
Niech AAA będzie macierzą nad polem skończonym F2={0,1}F2={0,1}\mathbb{F}_2 = \{0,1\} a xxx , yyy będą wektorami przestrzeni Fn2F2n\mathbb{F}_2^n . Interesuje mnie złożoność obliczeniowa przy podejmowaniu decyzji, czy istnieje t∈Nt∈Nt \in \mathbb{N} takie, że Atx=yAtx=yA^t x = y , tj. Problem osiągalności liniowych układów dynamicznych nad polami skończonymi. Problem ten jest …
1
Wprowadzenie do automatów probabilistycznych
Gdzie mogę znaleźć wprowadzenie do automatów probabilistycznych i co one rozpoznają (niektóre funkcje od słów do )? Czy istnieje standardowy termin określający takie funkcje, które są rozpoznawane przez automaty probabilistyczne, analogiczne do „zwykłych języków”, dla których rozpoznają deterministyczne automaty skończone (DFA)?[ 0 , 1 ][0,1][0,1] Szukam czegoś, co podchodzi do …
2
Algorytm mnożenia wektora macierzy przy użyciu minimalnej liczby dodatków
Rozważ następujący problem: Biorąc pod uwagę macierz , chcemy zoptymalizować liczbę dodatków w algorytmie mnożenia do obliczania .MMMv↦Mvv↦Mvv \mapsto Mv Uważam ten problem za interesujący ze względu na jego związek ze złożonością mnożenia macierzy (ten problem jest ograniczoną wersją mnożenia macierzy). Co wiadomo o tym problemie? Czy są jakieś interesujące …
1
Czy jest rozstrzygalne, czy długość wyjściowa przetwornika jest ograniczona długością wejściową?
Rozważane tutaj przetworniki to te, które Wikipedia nazywa przetwornikami skończonymi . Zachowanie przetwornika , czyli relacja, którą oblicza, jest zapisywane : słowo jest wyjściem dla iff .[ T ] y x x [ T ] yT.TT[ T][T][T]yyyxxxx [ T] yx[T]yx[T]y Pytanie: Czy można rozstrzygnąć następujący problem: Biorąc pod uwagę: Przetwornik …
1
Odniesienie do faktu, że (0 = 1) oznacza fałsz, wymaga wszechświata w MLTT
Jest to dość dobrze znany fakt, że wywodzenie sprzeczności z nierówności (na przykład ) w teorii typu Martina-Loefa wymaga wszechświata.(0=1)→⊥(0=1)→⊥(0=1) \to \bot Dowód jest również dość prosty - w przypadku braku wszechświatów możemy usunąć zależności od dowolnego typu zależnego, aby uzyskać prosty typ jako jego kształt, a więc udowodnienie, że …
3
Wykres teoretyczne ograniczenie do dowodów w teorii złożoności dowodu
Złożoność dowodu jest najbardziej podstawowym obszarem teorii złożoności obliczeniowej. Ostatecznym celem tego obszaru jest udowodnienie , co oznacza, że ​​żaden z proverów nie może dać dowodu na niezadowolenie danej formuły wejściowej. N.P.≠ c o NP.N.P.≠dooN.P.NP\neq coNP Wykres jest jednym z formalnych modeli dowodów. Moje pytanie dotyczy dalszego ograniczenia tego modelu. …
1
Hipoteza Hartmanisa-Stearnsa i obliczalne liczby transcendentalne
W artykule z 1965 r. „ O złożoności algorytmów ” autorstwa Hartmanisa i Stearnsa autorzy przypuszczają, że jeśli maszyna Turinga w czasie rzeczywistym oblicza liczbę rzeczywistą na przykład w podstawie 10, to r jest albo liczbą wymierną, albo liczbą liczba transcendentalna.rrrrrr Czy istnieje obliczalna liczba transcendentalna, która nie jest obliczalna …
1
Jakie są główne problemy badawcze w transakcjach rozproszonych?
Tło: Przetwarzanie transakcji jest tradycyjnym tematem badań w teorii baz danych. Obecnie transakcje rozproszone są popularyzowane przez wielkoskalowe rozproszone systemy pamięci masowej, które zazwyczaj obejmują partycjonowanie danych (zwane także shardingiem) i replikację danych . Jakie są główne problemy badawcze w transakcjach rozproszonych? Czy istnieją dobrze znane teorie i rozwiązania, które …
1
Problem występuje w P tylko wtedy, gdy P! = NP
Czy są jakieś problemy, które można rozwiązać w czasie wielomianowym tylko wtedy, gdy P! = NP, a w innym przypadku rozwiązać (powiedzmy) ?O ( 2n)O(2)n)O(2^n) Prostym przykładem byłoby: Jeśli P! = NP, oblicz test pierwszeństwa dla losowej liczby n-bitowej, w przeciwnym razie oceń losową pozycję najgorszego przypadku w uogólnionych szachach …
2
Jakie jest minimum we wszystkich rozkładach wektorów jednostkowych wariancji iloczynu wektorów?
Usiłuję znaleźć rozkład na losowych wektorów, powiedzmy , na sferze jednowymiarowej (gdzie ), która minimalizuje zastrzeżeniem ograniczenia \ mathbb {E} [x_i ^ Tx_j] = 0 .nnnx1,…,xnx1,…,xnx_1,\ldots, x_nkkkn>kn>kn > kmaxi≠jVar(xTixj)maxi≠jVar(xiTxj)\max_{i\neq j} \mathrm{Var}(x_i^T x_j)E[xTixj]=0E[xiTxj]=0\mathbb{E}[x_i^Tx_j]=0 Próbowałem niektórych dystrybucji i prawie wszystkie mają wariancję . Na przykład zarówno rozkład, w którym każda współrzędna każdego …
2
Dlaczego linearyzowalność jest właściwością bezpieczeństwa i dlaczego zestawy właściwości bezpieczeństwa są zamknięte?
W rozdziale 13 „Obiekty atomowe” książki „Algorytmy rozproszone” Nancy Lynch udowodniono, że linearyzowalność (znana również jako atomowość) jest właściwością bezpieczeństwa. To znaczy, że jego odpowiednia właściwość śledzenia jest niepusta, zamknięta z prefiksem i zamknięta z ograniczeniem , jak zdefiniowano w sekcji 8.5.3. Nieformalnie właściwość bezpieczeństwa jest często interpretowana jako powiedzenie, …
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.