Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

2
Mały wykres z odstępem między liczbą chromatyczną a liczbą chromatyczną wektorową?
Szukam małego wykresu GGG którego wektorowa liczba chromatyczna jest mniejsza niż liczba chromatyczna, χv(G)&lt;χ(G)χv(G)&lt;χ(G)\chi_v(G)<\chi(G) . ( GGG zawiera wektor chromatycznej liczba qqq , jeśli istnieje zadanie x:V→Rdx:V→Rdx\colon V \rightarrow \mathbf R^d , gdzie intuicyjnie wektory związane z sąsiednimi wierzchołkami są oddalone od siebie Warunkiem jest, ⟨x(v),x(w)⟩≤−1/(q−1)⟨x(v),x(w)⟩≤−1/(q−1)\langle x(v), x(w)\rangle \leq -1/(q-1) …
1
Twierdzenie Schaefera i CSP o nieograniczonej szerokości
Twierdzenie dychotomii Schaefera pokazuje, że każdy problem CSP powyżej można rozwiązać w czasie wielomianowym lub jest on NP-kompletny. Dotyczy to tylko problemów CSP o ograniczonej szerokości, z wyłączeniem na przykład SAT i Horn-SAT. Ogólne problemy CSP o nieograniczonej szerokości mogą być bardzo trudne (nawet nieobliczalne), więc ograniczmy się do problemów, …
1
Stabilność numeryczna metody Simplex
Algorytm simpleksowy jest często traktowany albo w ramach rzeczywistej arytmetyki, albo w świecie dyskretnym z dokładnymi obliczeniami. Wydaje się jednak, że jest najczęściej wdrażany za pomocą arytmetyki zmiennoprzecinkowej. Prowadzi to do pytania, czy algorytm simpleks należy traktować jako algorytm numeryczny, w szczególności w jaki sposób błędy zaokrąglenia wpływają na obliczenia. …
2
Programowanie liczb całkowitych ze stałą liczbą zmiennych
Słynny artykuł H. Lenstry Integer Programowanie z ustaloną liczbą zmiennych z 1983 r. Stwierdza, że ​​programy liczb całkowitych o ustalonej liczbie zmiennych można rozwiązać wielomianem czasowym długości danych. Interpretuję to w następujący sposób. Programowanie liczb całkowitych ogólnie jest nadal NP-kompletne, ale jeśli mój typowy rozmiar problemu (powiedzmy około 10.000 zmiennych, …
1
Minimalne elementy monotonicznego predykatu nad zestawem mocy
Rozważ monotoniczny predykat PPP nad zestawem mocy 2|n|2|n|2^{|n|}(uporządkowane przez włączenie). Przez „monotoniczny” rozumiem: ∀x,y∈2|n|∀x,y∈2|n|\forall x, y \in 2^{|n|}tak, że x ⊂ yx⊂yx \subset y , jeśli P.( x )P(x)P(x) to P.( y)P(y)P(y) . Szukam algorytmu, aby znaleźć wszystkie minimalne elementy P.PP , tj. x ∈ 2| n |x∈2|n|x \in 2^{|n|}takie, …
1
Czy ta klasa wykresów ma nazwę?
Jest sformułowany przez rozszerzenie wykresów progowych . Biorąc pod uwagę wykres progowy gdzie jest kliką, a jest niezależnym zbiorem, moje rozszerzenie jest następujące: Każdy wierzchołek można zastąpić nową kliką tak, że wierzchołki mają to samo sąsiedzi .( C, Ja)(do,ja)(C,I)dodoCjajaIv ∈ Iv∈jav\in IK.vK.vK_vK.vK.vK_vvvv Wydaje mi się, że należało to zbadać, ale …
1
Optymalne solwery NP
Napraw problem wyszukiwania NP-complete, np. Formularz wyszukiwania SAT. Wyszukiwanie Levin zapewnia algorytm do rozwiązywania który jest w pewnym sensie optymalny. Konkretnie, algorytm jest „Wykonanie wszystkich możliwych programów w zazębianie na wejściowego , gdy niektórzy powraca odpowiedzieć testy czy jest to poprawna”. Jest optymalna w tym sensie, że biorąc pod uwagę …
1
Negatywne wyniki w podejściu identycznych cząstek do problemu Isomorphism Graph (GI)
Podjęto próby zaatakowania problemu izomorfizmu grafów za pomocą kwantowego losowego chodzenia twardych rdzeni (symetryczne, ale bez podwójnego zajęcia). Symetryczna moc matrycy przylegania, która wydawała się obiecująca, wykazano jako niekompletne ogólnych wykresów na tym papierze Amir Rahnamai Barghi i Ilia Ponomarenko. Inne podobne podejście zostało również obalone w tym artykule przez …
1
Kombinatoryczne osadzanie wykresu
Tutaj: http://www.planarity.org/Klein_elementary_graph_theory.pdf (w osadzeniach rozdziałów) podano definicję kombinatorycznego osadzania wykresu płaskiego. (z definicją ścian i tak dalej) Choć można go łatwo zastosować do dowolnego wykresu, definiują wykres płaski jako wykres, dla którego obowiązuje formuła Eulera (zakładając, że wykres jest połączony). Zrozumiałe jest, że dla każdego wykresu płaskiego definicja ścian w …
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.