Teoretyczne informatyka

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

2
Minimalizowanie automatów akceptujących słowa (tj. Nieskończone słowa)
Jakie jest standardowe podejście do minimalizacji Büchi-Automata (lub także Müller-Automata)? Przeniesienie zwykłej techniki ze słów skończonych, tj. Ustawienie dwóch stanów na równe, jeśli słowa „wyczerpania” stanów, które są akceptowane, są takie same, nie zadziała. Na przykład rozważmy, że Büchi-Automoton akceptuje wszystkie słowa o nieskończonej liczbie a, składające się z dwóch …
1
Izomorfizm Bermana-Hartmanisa dla NP
Korzystając z modelu rzeczywistej pamięci RAM / BSS, mamy klasę NP R (gdzie BSS to model Blum-Shub-Smale komputera z operacjami nad rzeczywistością). Mamy kompletne problemy z NP R. Pytanie zatem, czy istnieje analogia do hipotezy Bermana Hartmanisa dla klasy NP R ? Oczywiście postawione tutaj pytanie zależy od modelu - …
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
Reprezentująca funkcję logiczną przez wielomian
Załóżmy, że mamy funkcję boolowską od . Oczywiste jest, że prawdziwy wielomianowy wielomian p ( x ) taki, że f ( x ) = p ( x ) na x ∈ { 0 , 1 } n może być wieloliniowy. Jakie są ciekawe klasy funkcji boolowskich, dla których minimalny stopień …
1
Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany
Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m …
2
Kiedy wielomianowy GI oznacza wielomianowy (krawędziowy) GI?
Skrzyżowane z MO . Izomorfizm kolorowego wykresu (krawędzi) to GI, który zachowuje kolory (krawędzi, jeśli jest w kolorze krawędzi). Istnieje kilka obniżek przy użyciu transformacji / gadżetów GI (krawędzi) w kolorze do GI. W przypadku GI w kolorze krawędzi najprostsze jest zastąpienie kolorowej krawędzi gadżetem chroniącym GI kodującym kolor (najłatwiejszym …
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 …
1
Czy rachunek afiniczny lambda może rozwiązać każdy problem w P?
W Zaawansowanych tematach w typach i językach programowania w rozdziale o podstrukturalnych systemach typów wspomniano, że „starannie spreparowany” rachunek afiniczny lambda z kombinatorem rekurencyjnym dla list może wpisywać tylko terminy, które mają wielomianowy czas działania (nie przedstawić dowód ze względu na złożoność). Byłoby to bardzo interesujące, gdybyśmy mogli rozwiązać każdy …
1
Ukryta ścieżka w kwadratowych siatkach
Natknąłem się na otwarty problem postawiony przez Davida Eppsteina i jestem zainteresowany jego złożonością. Doszedł do wniosku, że jest kompletny NP. Dane wejściowe: przez macierzy zer i jedynek, sekwencja zer i jedyneknnnnnnn2n2n^2 Pytanie: Czy istnieje ścieżka przez sąsiednie wpisy macierzy, obejmujące każdy wpis macierzy dokładnie raz, a wartości pasują do …
1
Minimalny rozkład równomierny
Biorąc pod uwagę, że dwa wielościany i , i są jeśli istnieją skończone zestawy wielościanów i takie, że i są zgodne dla wszystkich , i . Wiadomo, że jeżeli i są wielokąty o jednakowej powierzchni, takie equidecomposition zawsze występuje i że nie posiada w ogólności dla większych wymiarów . Q …
1
Ostatnie postępy w algorytmach grup permutacji?
Interesują mnie algorytmy dla grup skończonych zaimplementowane w pakiecie GAP. Wydaje się, że wszystkie znane algorytmy w tej dziedzinie dotyczą grup permutacji / grup matryc; dwa podstawowe to Schreier-Sims [1970] i Butler [1979], patrz np. „Algorytmy dla grup permutacyjnych” Alice Niemeyer jako możliwy odnośnik (?) Dlatego zastanawiałem się, czy w …
2
Odwrotność do nierówności Fano?
Nierówność Fano można wyrazić w wielu formach, a jedna szczególnie przydatna wynika (z niewielką modyfikacją) Oded Regev : Niech XXX będzie zmienną losową, a Y=g(X)Y=g(X)Y = g(X) gdzie g(⋅)g(⋅)g(\cdot) jest procesem losowym. Załóżmy, że istnieje procedura fff która dla y=g(x)y=g(x)y = g(x) może zrekonstruować xxx z prawdopodobieństwem ppp . Następnie …
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.