Pytania otagowane jako cc.complexity-theory

P a NP i inne obliczenia ograniczone do zasobów.

2
Dowód użycia asystenta w badaniach teorii złożoności?
Biorąc pod uwagę tematy poruszane na konferencji, takie jak STOC, czy naukowcy zajmujący się algorytmem lub złożonością aktywnie korzystają z COQ lub Isabelle? Jeśli tak, to jak wykorzystują go w swoich badaniach? Zakładam, że większość ludzi nie użyłaby takich narzędzi, ponieważ dowody byłyby zbyt niskie. Czy ktoś używa tych asystentów …
2
Dodaj dopasowanie do ścieżki hamiltonianu, aby zmniejszyć maksymalną odległość między podanymi parami wierzchołków
Jaka jest złożoność następującego problemu? Wejście : aścieżka hamiltonowskaw K nHH.HKnKnK_n podzbiór par wierzchołkówR⊆[n]2R⊆[n]2R \subseteq [n]^2 dodatnia liczba całkowita kkk Pytanie : czy istnieje pasujące , że dla każdego ( v , u ) ∈ R , d G ( v , u ) ≤ k ? (gdzie G = …
3
Niedeterministyczne przyspieszenie obliczeń deterministycznych
Czy niedeterminizm może przyspieszyć obliczenia deterministyczne? Jeśli tak to ile? Przyspieszając obliczenia deterministyczne przez niedeterminizm rozumiem wyniki formy: DTime(f(n))⊆NTime(n)DTime(f(n))⊆NTime(n)\mathsf{DTime}(f(n)) \subseteq \mathsf{NTime}(n) Np. Coś takiego DTime(n2)⊆NTime(n)DTime(n2)⊆NTime(n)\mathsf{DTime}(n^2) \subseteq \mathsf{NTime}(n) Jaki jest najbardziej znany wynik przyspieszenia obliczeń deterministycznych przez niedeterminizm? Co powiesz na ΣPkTime(n)ΣkPTime(n)\mathsf{\Sigma^P_kTime}(n) a nawet ATime(n)ATime(n)\mathsf{ATime}(n) zamiast NTime(n)NTime(n)\mathsf{NTime}(n) ? Załóżmy, że klasy …
1
Monotoniczna złożoność obwodu arytmetycznego elementarnych wielomianów symetrycznych?
W kkk -tej elementarne wielomian symetryczny Snk(x1,…,xn)Skn(x1,…,xn)S_k^n(x_1,\ldots,x_n) jest sumą wszystkich produktów różnych zmiennych. Interesuje mnie złożoność obwodu arytmetycznego monotonicznego tego wielomianu. Prosty algorytm programowania dynamicznego (jak również ryc. 1 poniżej) daje obwód z bramkami .(nk)(nk)\binom{n}{k}kkk(+,×)(+,×)(+,\times)(+,×)(+,×)(+,\times)O(kn)O(kn)O(kn) Pytanie: Czy znana jest dolna granica ? Ω(kn)Ω(kn)\Omega(kn) obwód jest skośna , jeżeli co najmniej …
2
Zwykły kontra TC0
Według Zoo Złożoności , Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1} i wiemy, że RegReg\mathsf{Reg} nie może się liczyć, więc TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg} . Jednakże nie mówi, czy Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0} czy nie. Ponieważ nie znamy NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0} , nie znamy również Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} . Czy jest kandydatem do problemu w , który nie …
2
Nadzbiór wieloczęściowy NP kompletnego języka z nieskończenie wieloma ciągami wyłączonymi z niego
Czy dla dowolnego arbitralnego NP pełnego języka zawsze istnieje nadzbiór czasu policyjnego, którego dopełnienie jest również nieskończone? Na stronie /cs//q/50123/42961 poproszono o trywialną wersję, która nie przewiduje, że nadzbiór ma nieskończone uzupełnienie. Dla celów tej kwestii, można przyjąć, że . Jak wyjaśnił Vor, jeśli wówczas odpowiedź brzmi „Nie”. (Jeśli , …
2
Sprawdzanie równoważności dwóch polytopów
Rozważmy wektor zmiennych i zestaw wiązań liniowych określonych przez A → x ≤ b .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Ponadto rozważ dwa polytopy P1P2={(f1(x⃗ ),⋯,fm(x⃗ ))∣Ax⃗ ≤b}={(g1(x⃗ ),⋯,gm(x⃗ ))∣Ax⃗ ≤b}P1={(f1(x→),⋯,fm(x→))∣Ax→≤b}P2={(g1(x→),⋯,gm(x→))∣Ax→≤b}\begin{align*} P_1&=\{(f_1(\vec{x}), \cdots, f_m(\vec{x}))\mid A\vec{x}\leq b\}\\ P_2&=\{(g_1(\vec{x}), \cdots, g_m(\vec{x}))\mid A\vec{x}\leq b\} \end{align*} gdzie ' ig ' s są odwzorowaniami afinicznymi . Mianowicie …
3
Nietrudne problemy do rozwiązania w stałym czasie?
Stały czas jest absolutnie niskim stopniem złożoności czasu. Można się zastanawiać: czy jest coś nietypowego, co można obliczyć w stałym czasie? Jeśli trzymamy się modelu maszyny Turinga, niewiele można zrobić, ponieważ odpowiedź może zależeć tylko od początkowego odcinka wejścia o stałej długości, ponieważ dalsze części wejścia nie mogą być osiągnięte …
1
Jak drogie może być zniszczenie wszystkich długich ścieżek w DAG?
Uważamy DAG (skierowane wykresy acykliczne) z jednym węzłem źródłowym jeden docelowego węzła ; dozwolone są równoległe krawędzie łączące tę samą parę wierzchołków. - cięcie jest zestaw krawędzi, których usunięcie usunięcie wszystkich - ścieżek dłuższe niż ; krótsze - szlaki, a także wydłużone „wewnętrzny” (te, które nie ścieżki pomiędzy i ), …
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.