Pytania otagowane jako cc.complexity-theory

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

1
Czy znana jest złożoność tego problemu ścieżki?
Instancja: Niekierowany wykresGGGz dwoma wyróżnionymi wierzchołkami i liczbą całkowitą .s≠ts≠ts\neq tk≥0k≥0k\geq 0 Pytanie: Czy istnieje ścieżka w , taka, że ​​przecina ona co najwyżej trójkątów? (W przypadku tego problemu mówi się, że ścieżka przecina trójkąt, jeśli ścieżka zawiera co najmniej jedną krawędź od trójkąta).s−ts−ts-tGGGkkk
1
Czy znana jest złożoność tego problemu?
Niech będzie wykresem. Zestaw wierzchołek nazywa krytyczna jeśli i nie wierzchołek w przylega dokładnie jeden wierzchołek w . Problemem jest znalezienie zbiór wierzchołków z co najmniej taką wielkość, że każdego niezbędny zestaw .G = ( V, E)G=(V,E)G=(V,E)X⊆ V.X⊆VX\subseteq VX≠ ∅X≠∅X\neq\emptysetV.∖ XV∖XV\setminus XXXXS.⊆ V.S⊆VS\subseteq VS.∩ X≠ ∅S∩X≠∅S\cap X\neq\emptysetXXX Problem ma następującą …
1
Czysto teoretyczne objaśnienie redukcji z Unique Label Cover do Max-Cut
Studiuję Unique Games Conjecture i słynną redukcję do Max-Cut Khota i in. Ze swojej pracy i innych stron internetowych większość autorów używa (jak dla mnie) niejawnej równoważności między redukcją MAX-CUT a budowaniem konkretnych testów dla długich kodów. Z powodu mojego braku jasności co do tej równoważności staram się podążać tym …
2
Złożoność rozwiązywania równań liniowych
Co wiadomo na temat złożoności rozwiązywania układu równań liniowych na pewnym polu skończonym? Wiem, że istniejeO (n3))O(n3))O(n^3)algorytm (Gauss), który oblicza rozwiązanie, aw przypadku systemów rzadkich istnieją jeszcze lepsze algorytmy. Zastanawiałem się jednak, czy istnieje jakaś teoretyczna charakterystyka złożoności tego problemu. Na przykład jest odpowiedni problem decyzyjny wN C.N.do\mathbf{NC}? Czy jest …
1
Najmniejsza liczba bramek do mnożenia
Jaki jest najlepszy wynik dla liczby bramek w obwodzie pomnożącym dwie liczby całkowite n-bitowe? Oczywista metoda generuje bramki . Istnieją lepsze podejścia z i .θ(n2)θ(n2)\theta(n^2)θ(nlognloglogn)θ(nlog⁡nlog⁡log⁡n)\theta(n\log n \log\log n)θ(nlogn2log∗(n))θ(nlog⁡n2log∗⁡(n))\theta(n\log n2^{\log^*(n)}) Nie mogłem znaleźć żadnej rodziny obwodów boolowskich, która obsługiwałaby mnożenie za pomocą bramek . Zastanawiam się, czy istnieje taka rodzina obwodów.nlognnlog⁡nn\log …
1
Losowe ograniczenia i związek z całkowitym wpływem funkcji boolowskich
Powiedzmy, że mamy funkcję boolowską fa: { - 1 , 1}n→ { - 1 , 1 }f:{−1,1}n→{−1,1}f:\{-1,1\}^n\rightarrow \{-1,1\} i aplikujemy δδ\delta-losowe ograniczenie na faff. Ponadto powiedz, że drzewo decyzyjneT.TT to oblicza faff zmniejsza się O ( 1 )O(1)O(1)w wyniku losowego ograniczenia. Czy to implikuje tofafaf ma bardzo niski wpływ całkowity?
3
Czy istnieje uogólnienie teorii informacji na wielomianowo poznaną informację?
Przepraszam, to trochę „miękkie” pytanie. Teoria informacji nie ma pojęcia złożoności obliczeniowej. Na przykład instancja SAT lub instancja SAT plus bit wskazujący na satysfakcję niosą tę samą ilość informacji. Czy istnieje sposób sformalizowania pojęcia „wielomianowo poznawalny”? Takie ramy mogą definiować na przykład pojęcie dywergencji wielomianowej KL między zmienną losową X …
3
Posadzona klika w G (n, p), zmieniająca się p
W przypadku problemu sadzonej kliki należy odzyskać kkk-klinka posadzona na losowym wykresie Erdosa-Renyi G ( n , p )G(n,p)G(n,p). To było głównie rozpatrywanep =12)p=12p=\frac{1}{2}, w którym to przypadku wiadomo, że można rozwiązać czas wielomianowy, jeśli k &gt;n--√k&gt;nk > \sqrt{n} i przypuszczalnie trudne k &lt;n--√k&lt;nk< \sqrt{n}. Moje pytanie brzmi: co wiadomo …
1
Złożoność rodzaju ślepego?
Wszyscy wiemy, że minimalną złożonością algorytmu sortowania opartego na porównaniu są porównania . Próbuję wykonać sortowanie w ciemno , tzn. Biorąc pod uwagę liczbę wyjdź z obwodu (z bramkami logicznymi, arytmetycznymi i „porównawczymi”), który sortuje listę elementów.Ω ( n logn )Ω(nlog⁡n)\Omega(n \log n)nnnnnn Wstępne obliczanie wszystkich porównań select 2},(n2))(n2)){n \choose …
2
Bariery w oddzielaniu innych klas złożoności
Czy naturalne dowody , relatywizacja i algebriacja wpływają również na separację innych klas złożoności, takich jakL≠NL≠NP≠coNP≠PH≠PSPACEL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE itp? Na przykład bariera naturalnego dowodu powinna wpływać na każdy dowód NP≠CoNPNP≠CoNPNP\neq CoNP ponieważ się rozdzieli P≠NPP≠NPP\neq NP. Jednak związek międzyNPNPNP i CoNPCoNPCoNP wydaje się nie mieć wiele …
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.