Pytania otagowane jako reference-request

Zaczynam badać możliwość polegania na rozwiązaniu SAT w celu rozwiązania problemu optymalizacji, który mnie interesuje, i obecnie szukam ankiety, która zawierałaby przykłady „sprytnych” przekształceń w warianty SAT (tj. Przekształcenia, które wynikają w problemie o rozsądnej wielkości, ponieważ nie jestem zainteresowany udowodnieniem wyników twardości, ale faktycznym rozwiązaniem problemu), w przybliżeniu w …

13 ds.algorithms  reference-request  sat  optimization 

To, co nazywam liczeniem, to problem polegający na znalezieniu liczby rozwiązań funkcji. Dokładniej, biorąc pod uwagę funkcję fa: N→ { 0 , 1 }f:N→{0,1}f:N\to \{0,1\} (niekoniecznie czarna skrzynka), przybliżone # { x ∈ N∣ f( x ) = 1 } = | fa- 1( 1 ) |#{x∈N∣f(x)=1}=|f−1(1)|\#\{x\in N\mid f(x)= 1\}= …

13 ds.algorithms  reference-request  counting-complexity  time-complexity 

Stały parametr i przybliżenie to zupełnie inne podejścia do rozwiązywania trudnych problemów. Mają inną motywację. Przybliżenie szuka szybszego wyniku dzięki przybliżonemu rozwiązaniu. Naprawiono parametr szuka dokładnego rozwiązania ze złożonością czasową pod względem wykładniczej lub jakiejś funkcji k i funkcji wielomianowej n, gdzie n jest wielkością wejściową, a k jest parametrem. …

13 cc.complexity-theory  reference-request  approximation-algorithms  fixed-parameter-tractable 

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki:ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},wxijxijx_{ij} Zminimalizować ∑mj=1cj∑ℓi=1xij∑j=1mcj∑i=1ℓxij\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij} Z zastrzeżeniem: ∑mj=1xij=ni∀i∑j=1mxij=ni∀i\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i ∑ℓi=1xij≥w∀j∑i=1ℓxij≥w∀j\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j Chciałbym wiedzieć, czy ten program …

13 reference-request  linear-programming  polynomial-time  integer-programming  integrality-gap 

Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować. Na przykład dowiedziałem się, że można ich używać do skutecznego liczenia liczby idealnych dopasowań na wykresach płaskich. …

13 reference-request  co.combinatorics  counting-complexity 

Podczas eksploracji różnych technik dowodzenia dolnych granic dla algorytmów rozproszonych przyszło mi do głowy, że następujący wariant twierdzenia Ramseya może mieć zastosowania - jeśli to prawda. Podano parametry: kkk , KKK , nnn , a następnie wybrano NNN aby było wystarczająco duże. Terminologia: podzbiór mmm jest podzbiorem rozmiaru mmm . …

13 reference-request  co.combinatorics  ramsey-theory 

Istnieją dwa główne typy awarii procesorów w modelach przetwarzania rozproszonego: (1) Awarie awarii: procesor zatrzymuje się i nigdy nie uruchamia się ponownie. (2) Awarie bizantyjskie: procesory zachowują się przeciwnie, złośliwie. Moje pytanie brzmi: Jakie inne rodzaje awarii procesorów, które zostały zbadane, które nie ograniczają się do awarii lub awarii bizantyjskich? …

13 reference-request  dc.distributed-comp 

Problem plotkowania w systemach rozproszonych jest następujący. Mamy wykres GGG z nnn wierzchołkami. Każdy wierzchołek ma komunikat który należy wysłać do wszystkich węzłów.vvvmvmvm_v Moje pytanie dotyczy teraz modelu sieci ad-hoc (zakładamy, że węzeł nie ma żadnej wcześniejszej wiedzy na temat topologii sieci, jej stopni wejściowych i wyjściowych oraz zestawu sąsiadów. …

13 reference-request  dc.distributed-comp 

Wiadomo, że określenie, czy dany triangulowany 3-kolektor jest 3-kulą, znajduje się w NP, dzięki pracy Saula Schleimera w 2004 r .: „Rozpoznanie sfery leży w NP” arXiv: math / 0407047v1 [mat.GT] . Zastanawiam się, czy ustalono, że jest to kompletne NP w ciągu ostatnich pięciu czy sześciu lat? Analogiczne problemy, …

13 cc.complexity-theory  reference-request  open-problem  topology 

Tło: W uczeniu maszynowym często pracujemy z modelami graficznymi reprezentującymi funkcje gęstości prawdopodobieństwa o wysokim wymiarze. Jeśli odrzucimy ograniczenie, które gęstość całkuje (sumuje) do 1, otrzymujemy nienormalizowaną funkcję energii o strukturze grafowej . Załóżmy, że mamy taką funkcję energetyczną zdefiniowaną na wykresie . Na każdy wierzchołek wykresu przypada jedna zmienna …

13 reference-request  machine-learning  lg.learning  boolean-functions 

Mówi się, że dwa drzewa wyszukiwania binarnego są liniowo równoważne, jeśli zgadzają się w swoich wędrówkach w kolejności. Poniższe twierdzenie wyjaśnia, dlaczego rotacje drzew są tak fundamentalne: Niech A i B będą binarnymi drzewami wyszukiwania. Zatem A i B są liniowo równoważne wtedy i tylko wtedy, gdy są połączone sekwencją …

13 reference-request  ds.data-structures 

Łatwo jest zweryfikować, że biorąc pod uwagę wymiarową siatkę punktów całkowitych , przy regularnym sąsiedztwie można znaleźć separator o rozmiarze (wystarczy wybrać dowolny środkowy hiperpłaszczyzna i usuń wszystkie jego wierzchołki). Nie jest też zbyt trudne (ale zdecydowanie nie natychmiastowe) sprawdzenie, czy każdy separator musi mieć rozmiar \ Omega (n ^ …

13 reference-request  cg.comp-geom  lower-bounds 

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 hierarchia przestrzeni logicznej się zawala, co oznacza, że (definicja ograniczonej naprzemiennej maszyny Turinga i tego, co jest hierarchię …

13 cc.complexity-theory  reference-request  space-bounded  alternating-hierarchy 

Szerokość i szerokość ścieżki są popularnymi parametrami, mierzącymi odpowiednio bliskość wykresu do drzewa lub ścieżki. Rzeczywiście wydaje się, że szerokość jest tak popularna, że ​​pojawia się w wielu artykułach, książkach i notatkach z wykładów, które dają (nawet bardzo delikatne) wprowadzenie do algorytmicznych aspektów szerokości (patrz np. Książka Downey & Fellows). …

13 reference-request  graph-algorithms  parameterized-complexity 

Czy wiadomo, czy problem z ustawieniem wierzchołka sprzężenia zwrotnego na niekierowanych grafach płaskich o ograniczonym stopniu jest twardy?NPNP\mathsf{NP}

13 cc.complexity-theory  reference-request  graph-algorithms  np-hardness