Twierdzenie o hierarchii czasu stwierdza, że maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n)))...
Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź...
Klop, van Oostrom i de Vrijer mają papier na rachunku lambda z wzorami. http://www.sciencedirect.com/science/article/pii/S0304397508000571 W pewnym sensie wzór jest drzewem zmiennych - choć myślę o nim jako o zagnieżdżonej krotce zmiennych, na przykład ((x, y), z), (t, s)). W artykule wykazali,...
W Załączniku B do Zwiększania i różnicowej prywatności autorstwa Dwork i wsp. Autorzy podają następujący wynik bez dowodu i nazywają go nierównością Azumy: Niech być rzeczywista zmiennymi losowymi takimi, że dla każdego ,C1,…,CkC1,…,CkC_1, \dots, C_ki∈[k]i∈[k]i \in [k]...
Kto jako pierwszy pokazał, że dany język jest w NP, jeśli certyfikat dla tego języka można zweryfikować w czasie wielomianowym? Czy mamy dokument, który formalnie to potwierdza? Kiedy społeczność TCS zaczęła kłaść nacisk na niedeterminizm na rzecz weryfikowalności? Nie mogę znaleźć dla tego dobrego...
Chcę być bardzo konkretny. Czy ktoś wie o odrzuceniu lub dowodzie następującej propozycji: ∃ p ∈ Z [ x ] , n , k , C∈ N ,∃p∈Z[x],n,k,C∈N,\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N}, ∀ G , H∈ S.T.R Udo[ Σsolr a p h] ( m i n ( | G | , | H| )=n,G≄H)...
Z góry przepraszamy za to miękkie pytanie, które nie ma zamkniętej, poprawnej odpowiedzi. To chyba najlepsze forum do zadawania moich pytań. Jestem studentem trzeciego roku w grupie teoretycznej 15 najlepszych szkół w USA. Jak dotąd radziłem sobie całkiem nieźle. Mam do tej pory pierwszą pracę...
Załóżmy, że masz dwa deterministyczne automaty wypychające, które rozpoznają języki i B , i chcesz ustalić, czy istnieje regularny język R, taki jak A ⊆ R i R ∩ B = ∅ . Zasadniczo wyzwanie polega na ustaleniu, czy istnieje DFA, który może rozpoznać, który z dwóch języków pochodzi z danego łańcucha,...
W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie O ( n √nnn i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.O(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Jeśli...
Są badacze wykazujący, że bit wymazywania musi zużywać energię, czy teraz są jakieś badania dotyczące średniego zużycia energii algorytmu o złożoności obliczeniowej ? Wydaje mi się, że złożoność obliczeniowa F ( n ) jest skorelowana ze średnim zużyciem energii, mam nadzieję, że mogę tu znaleźć...
Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ?mmmX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Istnieje tutaj problem reprezentowania...
Niedawno próbowałem zaimplementować Cedille-Core Aarona , minimalistyczny język programowania zdolny do udowodnienia twierdzeń matematycznych na temat własnych terminów. Udowodniłem również indukcję dla typów danych zakodowanych na λ, co wyjaśniło, dlaczego jego rozszerzenia byłyby konieczne. Nie...
Czy istnieje Maszyna Turinga, która może zadecydować, czy prawie wszystkie inne Maszyny Turinga zatrzymają się? Załóżmy, że mamy jakieś wyliczenie maszyn Turinga i pewne pojęcie o „rozmiarze” zbioru liczb naturalnych, a my definiujemy:N →{ Mja}N→{Mi}\mathbb{N} \rightarrow \{M_i\}∥ ⋅∥‖⋅‖\| \cdot...
Poza środowiskiem akademickim, które jest wyraźnie domem teoretyków, zastanawiam się nad pracami przemysłowymi związanymi z informatyką teoretyczną, tymi, które wymagają czystego tła matematycznego. Twoje zdrowie
Rozważ funkcję obliczoną przez obwód logiczny z wejściami o rozmiarze na podstawie (z indegree 2 dla bram ).C n s ( n ) = p o l y ( n ) { X O R , A N D , N O T } X O R , A N DfaffdoCCnnns ( n ) = p o l y ( n )s(n)=poly(n)s(n) = \mathsf{poly}(n){ X O R , A N D , N O T
Niech C4C4C_4 będzie cyklem z czterema wierzchołkami. Aby uzyskać dowolny wykres GGG z nnn wierzchołkami i krawędziami m, powiedz m>nn−−√m>nnm>n\sqrt n , ileistniejeC4C4C_4? Czy jest na to dolna
Jestem studentem trzeciego roku na uniwersytecie „20 najlepszych”, który pracuje nad złożoną złożonością (dużo zabawy z 3-SUM, OV i zwykłymi popularnymi przypuszczeniami dotyczącymi twardości). W ciągu ostatniego roku byłem dość produktywny i otrzymałem 3 zaakceptowane prace i dwie przesłane prace....
Dobrze wiadomo, że uzupełnienie jest pozbawione kontekstu. Ale co z dopełnieniem ?{ww∣w∈Σ∗}{ww∣w∈Σ∗}\{ ww \mid w\in \Sigma^*\}{www∣w∈Σ∗}{www∣w∈Σ∗}\{ www \mid w\in
Czytam stąd dowód i natknąłem się na problem techniczny (ale kluczowy). Wiem, że jest to dość specyficzne i kontekst jest problematyczny, ale sam nie mogłem tego pojąć. Na stronach 51 i 55, po przedstawieniu „standardowych” weryfikatorów, przechodzą do modyfikacji weryfikatorów w celu sprawdzenia...
Załóżmy, że jeden ma losowy (BPP) algorytm ZAAA przy użyciu rrr bitów przypadkowości. Istnieją naturalne sposoby na zwiększenie prawdopodobieństwa sukcesu do 1 - δ1−δ1-\delta dla każdego wybranego δ> 0δ>0\delta>0 Niezależne przebiegi + większość głosów: przebieg ZAAA niezależnie T.= Θ (...