Pytania otagowane jako complexity-theory

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

2
Interaktywne dowody dla CoNP
Próbuję zrozumieć interaktywne systemy dowodowe i jako ćwiczenie wypróbowałem następujący problem. Wiemy toP.H.⊆ P.S.P.A C.miPH⊆PSPACEPH \subseteq PSPACE i jaP.= PS.P.A C.miIP=PSPACEIP=PSPACE, więc opracuj (łatwe do zrozumienia) interaktywne systemy próbne dla P.H.PHPH? Interaktywny system proof dla N.P.NPNP jest banalna, ale nie udało mi się nawet uzyskać interaktywnego systemu dowodowego c o …
2
Odnaleźć
Niech będzie językiem wszystkich formuł -CNF , tak aby przynajmniej z klauzul mogły być spełnione.LϵLϵL_\epsilon222φφ\varphi(12+ϵ)(12+ϵ)(\frac{1}{2}+\epsilon)φφ\varphi Muszę udowodnić, że istnieje st is twardy dla każdego .ϵ′ϵ′\epsilon'LϵLϵL_\epsilonNPNP\mathsf{NP}ϵ&lt;ϵ′ϵ&lt;ϵ′\epsilon<\epsilon' Wiemy, że może być przybliżony do presetów klauzul z redukcji . Jak mam to rozwiązać?Max2SatMax2Sat\text{Max}2\text{Sat}55565556\frac{55}{56}Max3SatMax3Sat\text{Max}3\text{Sat}
3
Konkretne zrozumienie różnicy między definicjami PP i BPP
Jestem zdezorientowany co do definicji PP i BPP . Załóżmy, że jest charakterystyczną funkcją języka . M być probabilistyczną Maszyną Turinga. Czy następujące definicje są poprawne:χχ\chiLL\mathcal{L} BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ&gt;0}BPP={L:Pr[χ(x)≠M(x)]≥12+ϵ∀x∈L, ϵ&gt;0}BPP =\{\mathcal{L} :Pr[\chi(x) \ne M(x)] \geq \frac{1}{2} + \epsilon \quad \forall x \in \mathcal{L},\ \epsilon > 0 \} PP={L:Pr[χ(x)≠M(x)]&gt;12}PP={L:Pr[χ(x)≠M(x)]&gt;12}PP =\{\mathcal{L} :Pr[\chi(x) \ne …
1
Minimalny rozcięcie na ważonych ukierunkowanych wykresach acyklicznych z potencjalnie ujemnymi wagami
Wystąpił następujący problem: Biorąc pod uwagę ukierunkowany wykres acykliczny z rzeczywistymi wartościami grubości krawędzi oraz dwoma wierzchołkami s i t, oblicz minimalny st st cut. Dla ogólnych wykresów jest to trudne NP, ponieważ można w prosty sposób zredukować maksymalne cięcie, po prostu odwracając wagi krawędzi (popraw mnie, jeśli się mylę). …
1
Twardość i kierunki redukcji
Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny. Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz 4-kolory, ergo 4-kolory są trudne. Właśnie …
1
Obwody o głębokości 2 z bramkami OR i MOD nie są uniwersalne?
Dobrze wiadomo, że każdą funkcję boolowską można zrealizować za pomocą obwodu boolowskiego o głębokości 2 (ponad zmiennymi, ich negacją i stałymi wartościami) zawierający bramki AND na pierwszym poziomie i jedną pojedynczą bramkę OR na górnym poziomie; jest to po prostu przedstawienie DNF z .f:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\}fff Innym rodzajem bramki, która jest …
1
Dolne granice obliczania funkcji zbioru
Posiadanie zestawu ZAAAz elementów, powiedzmy, że chcę obliczyć funkcję która jest wrażliwa na wszystkie części danych wejściowych, tj. zależy od samego elementu (tzn. można zmienić dowolny element na coś innego, aby uzyskać nowe wejście pierwsza wartość na i są różne).nnnfa( A )f(A)f(A)ZAAAZAAAZA′A′A'faffZAAAZA′A′A' Na przykład może być sumą lub średnią.faff Czy …
3
Logarytmiczna vs podwójna logarytmiczna złożoność czasu
Czy w rzeczywistych aplikacjach jest konkretna korzyść z używania algorytmów zamiast algorytmów ?O (log( log( n ) )O(log⁡(log⁡(n))\mathcal{O}(\log(\log(n))O (log( n ) )O(log⁡(n))\mathcal{O}(\log(n)) Dzieje się tak, gdy na przykład używa się drzew van Emde Boasa zamiast bardziej tradycyjnych implementacji drzewa wyszukiwania binarnego. Ale na przykład, jeśli weźmiemy to w najlepszym przypadku …
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.