W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję? Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie...
Wydaje mi się, że większość teoretyków złożoności ogólnie uważa następującą zasadę filozoficzną: Jeśli nie możemy wymyślić skuteczny algorytm dla problemu i możemy zmniejszyć problemu A do problemu B , wtedy prawdopodobnie nie jest skuteczny algorytm dla problemu B ,...
Chcę się dowiedzieć o algorytmach algebraicznych i złożoności tysiąca. W szczególności interesuje mnie PIT. Czy istnieje zestaw notatek z wykładów, książek, prac i ankiet dla studentów, którzy przeczytali standardowy podręcznik o teorii, taki jak książka Sipsera lub podręcznik złożoności...
Czytałem artykuł na Wikipedii o problemie ośmiu królowych. Stwierdzono, że nie ma znanego wzoru na dokładną liczbę rozwiązań. Po kilku poszukiwaniach znalazłem artykuł o twardości liczenia problemów z kompletnymi mapowaniami. W tym artykule jest problem, który okazuje się co najwyżej tak trudny jak...
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...
Razborov udowodnił, że dopasowanie funkcji monotonicznej nie występuje w MP . Ale czy możemy obliczyć dopasowanie za pomocą obwodu wielkości wielomianowej z kilkoma negacjami? Czy istnieje obwód P / poli z który oblicza dopasowanie? Jaki jest kompromis między liczbą negacji a rozmiarem...
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
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,...
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...
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...
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...
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...
Czy były prace nad znalezieniem minimalnej liczby elementarnych operacji arytmetycznych potrzebnych do obliczenia wyznacznika macierzy na dla małej i stałej ? Na przykład
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 = ( [ n ] , M ∪ H )...
Niech jest funkcją, która odwzorowuje s -gate obwód C w n bitów i jest n -bitowy ciąg X do C ( X ) . Załóżmy, że obwody są kodowane jako acykliczna sekwencja przypisań k : = g ( i , j ), gdzie i , j , k są etykietami przewodowymi.CircuitEvals,nCircuitEvals,n\mathsf{CircuitEval}_{s,...
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...
Język jest w języku jeśli istnieje maszyna Turinga z logami, która decyduje o języku z wielomianową ilością porad.L/polyL/polyL/poly Zobacz tutaj, aby uzyskać więcej informacji: https://en.wikipedia.org/wiki/L/poly Pytanie Jakie są konsekwencje ?P⊆L/polyP⊆L/polyP \subseteq...
Jaka jest złożoność decyzji, czy przedział liczb naturalnych zawiera liczbę pierwszą? Wariant Sita Eratostenesa daje algorytm , w którym jest długością przedziału, a ukrywa czynniki polilarytmiczne w punkcie początkowym przedziału; czy możemy zrobić lepiej (pod względem samego...
Dzięki Immerman i Szelepcsényi wiadomo, że jeśli f = Ω ( log ) (nawet w przypadku funkcji niemożliwych do zbudowania w przestrzeni).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) W tym samym artykule Immerman stwierdza, że naprzemienna...
Mówiąc wprost: jaka jest zgodność między maszynami Turinga z wyroczniami a rodzinami jednorodnych obwodów z wyroczniami? Jak te ostatnie są zdefiniowane w celu uzyskania tego samego modelu obliczeniowego dla danej maszyny Turinga z Oracle? To może być elementarne pytanie, ale nie jest oczywiste,...