Gęstość języka jest funkcją zdefiniowano jako Załóżmy, i są to języki na pewną skończoną alfabetu wielu jeden logspace redukuje się do , a jest w . Funkcje są wielomianowo powiązane, jeśli istnieją wielomiany i takie, że dla wszystkich , id X : N → N d X ( n ) = | { x ∈ X ∣ | x | ≤ n } | . A B A B...
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)))...
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...
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...
Biorąc pod uwagę dowolny prosty niekierowany wykres G, nie jest łatwe ustalenie, czy G ma nietrywialne (nieidentyfikacyjne) automorfizmy. Ale jakie są wyniki w górnej / dolnej granicy tego problemu
Zastanawiam się, czy klasy NPC zdefiniowane przez redukcje wielokrotne i redukcje Turinga są równe. Edycja: Kolejne pytanie, czy redukcje Turinga powodują tylko załamanie klas C i co-C dla niektórych C lub czy istnieje klasa taka jak istnieje problem, który nie występuje w przy redukcji Karp i...
Jaka jest dokładna złożoność czasowa niekierowanego algorytmu przestrzeni logów st-connectivity autorstwa Omer
Podczas studiów licencjackich EE uczestniczyłem w kilku wykładach, które przedstawiały ładną charakterystykę obwodów boolowskich pod względem liczby zagnieżdżonych pętli. Ze złożonością obwody boolowskie są często uważane za sztylety, ale w rzeczywistości cykle sprzętowe są powszechne. Teraz,...
Dla danego wykresu problem separatora pyta, czy istnieje zbiór wierzchołków lub krawędzi o małej liczności (lub wadze), którego usunięcie dzieli G na dwa rozłączne wykresy o w przybliżeniu równych rozmiarach. Nazywa się to problemem separatora wierzchołków, gdy usunięty zestaw jest zestawem...
Załóżmy, że NP = co-NP i wielomian ogranicza długość dowodu niezadowolenia dla instancji 3-CNF . Czy są więc jakieś wyniki w jakiej formie może przyjąć jakiś dowód niezadowolenia dla długości ? Tzn. Ogólnie, czy taki dowód musiałby na przykład wykorzystać pełną moc logiki drugiego rzędu nad...
To, co następuje, może wydawać się głupie (i to prawdopodobnie odzwierciedla moje słabe zrozumienie - więc proszę o wyrozumiałość) Miałem zapytanie dotyczące twierdzenia PCP. Wiemy, że po pierwszych trzech krokach mianowicie. Redukcja stopnia, ekspansja i amplifikacja odstępów , mamy wykres...
Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy...
Dwukomorowe gry na jedną rundę (2P1R) są niezbędnym narzędziem do uzyskania stopnia zbliżenia. Konkretnie, równoległe powtarzanie dwóch rundowych gier z dwiema proverami pozwala zwiększyć rozmiar luki w decyzyjnej wersji problemu aproksymacji. Zobacz wywiad ankiety Ran Raz na CCC 2010, aby uzyskać...
W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami...
Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi: [Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego...
Ponieważ 2 problemy NP-zupełne są z definicji redukowalne względem siebie, więc rozwiązanie jednego z nich można uzyskać za pomocą czarnej skrzynki rozwiązującej drugi, dlaczego nie mają podobnych współczynników aproksymacji (w odniesieniu do ich odpowiedników optymalizacyjnych )? Wydaje mi się, że...
To pytanie było motywowane pytaniem dotyczącym przepływu stosu . Załóżmy, że otrzymujesz zrootowane drzewo (tzn. Jest to root, a węzły mają dzieci itp.) W węzłach (oznaczonych ).n 1 , 2 , … , nT.T.Tnnn1 , 2 , … , n1,2),…,n1, 2, \dots, n Każdy wierzchołek ma powiązaną nieujemną masę całkowitą: .w...
Merlin, który ma nieograniczone zasoby obliczeniowe, chce przekonać Arturowi, że m | ∑p ≤ N, p pierwsza pkm|∑p≤N., p głównypkm|\sum_{p\le N,\ p\text{ prime}}p^k dla ( N, m , k )(N.,m,k)(N,m,k) przy k = O ( logN.)k=O(logN.)k=O(\log N) i m = O ( N) .m=O(N.).m=O(N). Obliczenie tej sumy w prosty...