Pytania otagowane jako complexity-theory

Pytania związane z (obliczeniową) złożonością rozwiązywania problemów

2
Podzbiór Suma: zredukuj przypadek specjalny do ogólnego
Wikipedia stwierdza problem sumy podzbiorów jako znalezienie podzbioru danego zbioru wielu liczb całkowitych, którego suma wynosi zero. Dalej stwierdza, że ​​jest to równoważne ze znalezieniem podzbioru z sumą sss dla dowolnego danego sss . Sądzę więc, że ponieważ są one równoważne, musi nastąpić zmniejszenie po obu stronach. Jeden od sss …
3
Jak trudno jest znaleźć dyskretny logarytm?
bbbab=cmodNab=cmodNa^b=c \bmod NaaacccNNN Zastanawiam się, w jakich grupach złożoności (np. Dla komputerów klasycznych i kwantowych) to jest i jakie podejścia (tj. Algorytmy) są najlepsze do wykonania tego zadania. Powyższy link do Wikipedii tak naprawdę nie zapewnia bardzo konkretnych środowisk uruchomieniowych. Mam nadzieję na coś bardziej podobnego do najbardziej znanych metod …
3
Problemy w P z znacznie szybszymi algorytmami randomizowanymi
Czy są jakieś problemy w które mają algorytmy losowe przekraczające dolne granice algorytmów deterministycznych? Mówiąc konkretniej, czy znamy jakieś dla którego ? Tutaj \ mathsf {PTIME} (f (n)) oznacza zestaw języków rozstrzygalnych przez losową TM z błędem o stałym ograniczeniu (jedno- lub dwustronny) w krokach f (n) .PP\mathsf{P}kkkDTIME(nk)⊊PTIME(nk)DTIME(nk)⊊PTIME(nk)\mathsf{DTIME}(n^k) \subsetneq \mathsf{PTIME}(n^k)PTIME(f(n))PTIME(f(n))\mathsf{PTIME}(f(n))f(n)f(n)f(n) …
3
POŁOWA KLIQUE - NP Kompletny problem
Zacznę od zauważenia, że jest to problem związany z pracą domową, proszę podać tylko porady i związane z nimi obserwacje, proszę BEZ BEZPOŚREDNIEJ ODPOWIEDZI . Powiedziawszy to, oto problem, na który patrzę: Niech HALF-CLIQUE = { | jest nieukierowanym wykresem posiadającym pełny podsgraf z co najmniej węzłami, gdzie n jest …
2
Problemy, które prawdopodobnie wymagają czasu kwadratowego
Szukam przykładów problemu, który ma dolną granicę ) dla wejścia .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Problem musi mieć następujące właściwości: Ω(n2)Ω(n2)\Omega(n^2) Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy. O(n2)O(n2)O(n^2)Algorytm , jeśli to możliwe, również prosty. Rozmiar wyjściowy (lub mniejszy). Oczywiście każdy problem, który wymaga wydłużonego wyjścia wymagał co …
2
Czy można wykazać twardość NP poprzez redukcje Turinga?
W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na ten temat? Czy istnieją dwa różne pojęcia twardości NP, a nawet …
3
Czy dla każdej funkcji obliczalnej
Czy dla każdej funkcji obliczalnej fff istnieje problem, który można najlepiej rozwiązać w czasie Θ(f(n))Θ(f(n))\Theta(f(n)) czy też istnieje funkcja obliczalna fff tak że każdy problem, który można rozwiązać w O(f(n))O(f(n))O(f(n)) może również być rozwiązany w czasie o(f(n))o(f(n))o(f(n)) ? To pytanie wpadło mi do głowy wczoraj. Zastanawiam się przez chwilę, ale …
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.