Teoretyczne informatyka

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

2
Argumenty za / przeciw hipotezie Kołmogorowa o złożoności obwodu P.
Według (niezweryfikowanego) rachunku historycznego Kołmogorow uważał, że każdy język w ma złożoność obwodów liniowych. (Zobacz wcześniejsze pytanie Hipoteza Kołmogorowa, że ma obwody o rozmiarach liniowych .) Zauważ, że implikuje .PP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq \mathsf{NP} Jednak przypuszczenie Kołmogorowa może się nie powieść. Na przykład Ryan Williams pisze w niedawnym artykule: „Przypuszczenie byłoby zaskakujące, jeśli …
2
„Osadzanie” języka jako takiego
Pytanie główne / ogólne Niech LLL będzie językiem. Zdefiniuj języki LiLiL_i pomocą L0=LL0=LL_0 = L i Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} dla i≥1i≥1i \geq 1 . Rozważmy L = ⋃ l i . Tak więc wielokrotnie „osadzić” L w siebie, aby uzyskać L .L^=⋃LiL^=⋃Li\hat{L} = …
1
Rachunek Lambda dla funkcji odwracalnych (obliczalnych r-Turinga)
Interesuje mnie koncepcja „kompletności r-Turinga”, zdefiniowana przez Axelsena i Glück (2011) . System jest gotowy do r-Turinga, jeśli może obliczyć ten sam zestaw funkcji, co odwracalna maszyna Turinga, bez generowania żadnych „śmieciowych” danych. Jest to to samo, co możliwość obliczenia każdej funkcji, która jest (a) obliczalna i (b) iniekcyjna. Chciałbym …
1
Czy istnieje geometryczny obraz adiabatycznego obliczenia kwantowego?
W adiabatycznym obliczeniu kwantowym (AQC) koduje się rozwiązanie problemu optymalizacji w stanie podstawowym [problemu] Hamiltoniana . Aby dojść do tego stanu podstawowego, zaczynasz w łatwym do stanie początkowym (podstawowym) z Hamiltonianem i „wyżarzaniem” ( adiabatycznym) w kierunku , tj.H i H pH.pHpH_pH.jaHiH_iH.pHpH_p H.( s ) = s H.ja+ ( 1 …
2
„Mały” wykres izomorfizmu
Myśląc o złożoności testowania izomorfizmu wykresów asymetrycznych (patrz moje powiązane pytanie dotyczące cstheory), przyszło mi do głowy pytanie uzupełniające. Załóżmy, że mamy do wielomianu czasu maszynowego Turinga , który na wejściu generuje wykres G M , n z n węzłów.MMM1n1n1^nGM,nGM,nG_{M,n}nnn Możemy zdefiniować problem ΠMΠM\Pi_M : („Małe” GI): Biorąc pod uwagę …
2
Algorytm Runtime of Grover
Jaka jest złożoność czasowa (nie złożoność zapytań) algorytmu Grovera? Wydaje mi się jasne, że jest to ponieważ istnieją iteracje i każda iteracja wymaga użycia operacji odbicia, która z kolei wymaga czasu przy użyciu dowolnego standardowego zestawu bram uniwersalnych.Ω(log(N)N−−√)Ω(log⁡(N)N)\Omega(\log(N) \sqrt{N})Ω(N−−√)Ω(N)\Omega(\sqrt{N})Ω(log(N))Ω(log⁡(N))\Omega(\log(N)) Problem polega na tym, że nie mogę znaleźć ani jednego odniesienia, …
1
Przypuszczenie o dwóch automatach liczników
Chciałbym udowodnić (lub obalić) następującą hipotezę: Przypuszczenie : automaty z dwoma licznikami (2CA) nie mogą zdecydować o następującym języku: n }L={n∣L={n∣L = \{ n \mid trójskładnikowej i binarnej reprezentacji ma zarówno parzystą, jak i nieparzystą długośćnnn}}\} 2CA może łatwo sprawdzić, czy reprezentacja binarna ma parzystą, czy nieparzystą długość (po prostu …
4
Algebra abstrakcyjna dla teoretycznych informatyków
Mam rozsądne wykształcenie matematyczne, ale nigdy nie czułem się w 100% swobodnie z abstrakcyjną algebrą (matematyka grup, pierścieni, pól itp.). Myślę, że było to częściowo tak, jak potrzebowałem, aby zobaczyć aplikacje, a wszystkie, które mogłem znaleźć, dotyczyły fizyki, a nie CS. Ponieważ moim zainteresowaniem jest naprawdę CS, czy są teraz …
3
Jaka jest oczekiwana głębokość losowo wygenerowanego drzewa?
Dawno temu myślałem o tym problemie, ale nie mam o nim pojęcia. Algorytm generujący jest następujący. Zakładamy, że istnieje dyskretnych węzłów ponumerowanych od do . Następnie dla każdego w , nadrzędny ty węzeł w drzewie będzie losowym węzłem w . Iteruj po każdym , aby wynik był losowym drzewem z …
2
Jakie są granice całkowitego programowania funkcjonalnego?
Jakie są ograniczenia całkowitego programowania funkcjonalnego? Nie jest to kompletna metoda Turinga, ale nadal obsługuje dużą część możliwych programów. Czy istnieją ważne konstrukcje, które można napisać w języku kompletnym Turinga, ale nie w języku funkcjonalnym? I czy słuszne jest stwierdzenie, że programy napisane w całkowicie funkcjonalnych językach mogą być całkowicie …
2
Czy problem zestawu wierzchołków sprzężenia zwrotnego można rozwiązać w czasie wielomianowym dla wykresów ograniczonych do 3 stopni?
Sprzężenie zwrotne Zestaw wierzchołków jest NP-kompletny dla ogólnych wykresów. Wiadomo, że jest NP-kompletny dla wykresów ograniczonych do stopnia 8 ze względu na redukcję z pokrycia wierzchołków. Artykuł w Wikipedii mówi, że jest on rozwiązany w czasie wielozakresowym dla grafów związanych ze stopniem 3 i jest NP-kompletny dla grafów związanych ze …
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.