Zastanawiałem się, czy problemy, dla których istnieją algorytmy czasu podliniowego (w wielkości wejściowej), można scharakteryzować jako posiadające określone właściwości. Obejmuje to czas podliniowy (np. Testowanie właściwości, alternatywne pojęcie przybliżenia problemów decyzyjnych), przestrzeń...
Wiemy, że możemy przedstawić dowolny wykres płaski za pomocą zestawu kół w płaszczyźnie, znanego jako wykres monety . Każde koło reprezentuje wierzchołek, a pomiędzy dwoma wierzchołkami znajduje się krawędź wtedy i tylko wtedy, gdy koła „pocałują się” na swojej granicy. Załóżmy, że zamiast tego...
Czy potrafisz modelować wiarygodne transmisje w rachunku różniczkowym? Jeśli tak to jak? Jeśli nie: Czy istnieją podobne algebry procesowe, w których możesz? Co próbowałem: Jeśli nadawca chce wysłać wiadomość do wszystkich do , możesz napisać ! ( i do . Ale w jaki sposób gwarantujesz, że...
Biorąc pod uwagę nieukierowany wykres nnn wierzchołka, jaki jest najbardziej znany środowisko uruchomieniowe dla znalezienia podrozdziału, który jest dwukolorową k × kk×kk\times k ? Czy istnieją szybsze algorytmy parametryzowane niż algorytm polegający na „zgadywaniu” jednej strony biclique i...
Załóżmy, że otrzymujemy macierz i pozwólmy . Jak szybko możemy obliczyć moc A ^ m tej macierzy? m ∈ N 0 A mA ∈ RN.× N.ZA∈RN.×N.A \in \mathbb R^{N\times N}m ∈ N0m∈N.0m \in \mathbb N_0ZAmZAmA^m Kolejną najlepszą rzeczą w porównaniu do obliczania produktów jest zastosowanie szybkiego potęgowania,...
Czytając blog Dicka Liptona, natknąłem się na następujący fakt pod koniec jego posta Bourne Factor : Jeśli dla każdego istnieje relacja formy ( 2 n ) ! = M - 1 Σ k = 0 k b c k k , gdzie m = p O l r ( n ) , a każdy z k , b k i c k są s O l y ( n ) na długości bitowej, a następnie faktoring ma...
π 1 : A × B → A π 2 : A × B → BA×B≜∀α.(A→B→α)→αA×B≜∀α.(A→B→α)→α A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha π1:A×B→Aπ1:A×B→A\pi_1 : A \times B \to Aπ2:A×B→Bπ2:A×B→B\pi_2 : A \times B \to B Nie jest to tak zaskakujące, nawet jeśli naturalny odczyt typu F jest parą z...
Biorąc pod uwagę dwa macierzy i , problem decydowania o istnieniu macierzy permutacji takiej, że jest równoważny (Izomorfizm Grafów). Ale jeśli rozluźnimy aby był tylko odwracalną matrycą, to jaka jest złożoność? Czy istnieją jakieś inne ograniczenia dotyczące odwracalnej macierzy , oprócz tego, że...
Nie wiadomo, czy izomorfizm wykres (GI) do silnie graf regularny (SRGs) jest P . Czy są jakieś wskazówki, że może, ale nie musi, być GI -Complete? Czy w takich przypadkach są jakieś poważne konsekwencje? (Podobne do przekonania, że oznaczenie geograficzne może nie być
Zakładamy, że . Zatem dobrze znany jest następujący fakt:G∈G(n,p),p=lnn+lnlnn+c(n)nG∈G(n,p),p=lnn+lnlnn+c(n)nG\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n} Pr[G has a Hamiltonian cycle]=⎧⎩⎨⎪⎪10e−e−c(c(n)→∞)(c(n)→−∞)(c(n)→c)Pr[G has a Hamiltonian...
W zadaniu pakowania prostokąt, jeden dany zestaw prostokątów i prostokąt, R . Zadaniem jest znalezienie umieszczenie R 1 , ... , r n wewnątrz R takie, że żaden z n prostokąty pokrywają. Ogólnie, orientacja każdego prostokąta r i jest stała. Oznacza to, że prostokąty nie mogą być obracane. W tym...
Niech będą zestawami, które mogą mieć wspólne elementy. Szukam najmniejszego zestawu takiego, że .S1,S2,…,SnS1,S2,…,SnS_1,S_2,\ldots,S_nXXX∀i,X∩Si≠∅∀i,X∩Si≠∅\forall i,\,X\cap S_i \ne \emptyset Czy ten problem ma nazwę? Czy może sprowadza się to do znanego problemu? W moim kontekście opisują...
Załóżmy, że dla każdego istnieje maszyna Turinga M ϵ, która decyduje o języku L w czasie O ( n a + ϵ ) . Czy istnieje jeden algorytm decydujący o L w czasie O ( n a + o ( 1 ) ) ? (Tutaj składnik o ( 1 ) jest mierzony jako n , długość wejściowa.)ϵ>0ϵ>0\epsilon >...
Nie mam wiedzy w zakresie teorii złożoności z udziałem grup, więc przepraszam, jeśli jest to dobrze znany wynik. Pytanie 1. Niech będzie prostym nieukierowanym grafem rzędu . Jaka jest złożoność obliczeniowa (w kategoriach ) ustalania, czy jest przechodnie dla
Mówimy, że funkcja boolowska f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} jest k-kk junta, jeśli fff ma co najwyżej kkk zmiennych wpływających. Niech f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} będzie 2 k-2k2k juntą. Oznaczają odpowiednio zmienne fff o x...
Czytam klasyczny utwór „Twardość kontra losowość” Nisana i Wigdersona. Niech B = { 0 , 1 }b={0,1}B=\{0,1\} , a ustalenie funkcją l : N → Nl:N.→N.l\colon \mathbb{N} \to \mathbb{N} . Określają one rodzinę funkcji G = { Gn: Bl ( n )→ B.n}sol={soln:bl(n)→bn}G = \{G_n : B^{l(n)} \to B^n\} być...
Jaki jest najlepszy wynik deterministyczny dla utrzymania dynamicznego zamknięcia przechodniego na ukierunkowanym wykresie z tylko wstawieniem krawędzi? Przeczytałem kilka artykułów na temat problemu dynamicznego zamykania przechodniego zarówno przy wstawianiu, jak i usuwaniu krawędzi. Czy są...
Przepraszam, jeśli to naiwne pytanie, ale nie mogłem znaleźć uzasadnienia w żadnej z głównych książek, takich jak Bondy-Murty, Diestel czy West. Idealne wykresy mają wiele pięknych właściwości, ale jaki jest jedyny powód, dla którego nazywane są idealnymi? A może to tylko preferencja estetyczna...
Czy są jakieś praktyczne zastosowania dla modeli programowania innych niż von Neumann? Jakie są najczęściej stosowane języki programowania inne niż von
W przypadku problemu, nad którym obecnie pracuję, naturalnie pojawia się rozszerzenie operatora hałasu i byłem ciekawy, czy były wcześniejsze prace. Najpierw pozwól mi zrewidować podstawowy operator hałasu na funkcjach boolowskich o wartościach rzeczywistych. Biorąc pod uwagę funkcję i , st , \...