Pracujemy na rozproszonych komputerach i znaleźliśmy problem złożoności, który sprowadza się do minimalnego problemu obejmującego ścieżkę. Obecnie nie wiemy, jak to rozwiązać. Problem jest następujący: Niech będzie liczbą całkowitą, a będzie wykresem zawierającym wierzchołki . Każdy wierzchołek...
Interesują mnie przykłady konstrukcji teorii złożoności, które są lepsze niż konstrukcje losowe. Jedyny znany mi przykład takiej konstrukcji dotyczy kodów korygujących błędy. Kody geometrii algebraicznej są lepsze w niektórych zakresach parametrów niż kody losowe. Można łatwo skonstruować takie...
W kombinatoryce i informatyce istnieje wiele przykładów, w których możemy analizować problem teoretyczny na wykresach, ale w przypadku analogu hipergrraficznego problemu brakuje naszych narzędzi. Jak myślisz, dlaczego problemy często stają się znacznie trudniejsze w przypadku 3-jednolitych...
Niech będzie językiem bezkontekstowym. Zdefiniować p p c ( L ) za przed i przyrostek zamknięcie L , innymi słowy, p p c ( L ) obejmują L jest prefiks i postfixes i stąd L siebie. Moje pytanie: jeśli L jest pozbawiony kontekstu i ma niejednoznaczną gramatykę, to czy to samo dotyczy p p c ( L )...
f,gf,gf,gf(n)logf(n)=o(g(n))f(n)logf(n)=o(g(n))f(n) \log f(n) = o(g(n))f , g f ( n + 1 ) = o ( g ( n ) )DTIME(f(n))⊊DTIME(g(n))DTIME(f(n))⊊DTIME(g(n)) DTIME(f(n)) \subsetneq DTIME(g(n))f,gf,gf,gf(n+1)=o(g(n))f(n+1)=o(g(n))f(n+1)=o(g(n))jest to NTIME(f(n))⊊NTIME(g(n)).NTIME(f(n))⊊NTIME(g(n))....
Wpis dotyczy: /mathpro/59631/lovasz-theta-function-and-independence-number-of-product-of-simple-odd-cycles Jak dalece Lovasz jest związany ze zdolnością do zerowego błędu regularnych grafów? Czy istnieją przykłady, w których wiadomo, że ograniczenie Lovasz nie jest równe pojemności zerowego błędu...
Program zakresu to liniowo-algebraiczny sposób określania wprowadzonej tutaj funkcji boolowskiej . Ostatnio model ten został użyty do wykazania, że metoda negatywnego przeciwnika zapewnia ścisłą charakterystykę (przynajmniej do ) złożoności kwantowych zapytań.logn/loglognlogn/loglogn\log n/...
Rozważ problem z zestawem dominującym na ogólnych wykresach i niech będzie liczbą wierzchołków na wykresie. Chciwy algorytm aproksymacji daje gwarancję aproksymacji współczynnika , tzn. Możliwe jest znalezienie w czasie wielomianowym rozwiązania takiego, że , gdzie jest rozmiarem minimalnego...
Aby odpowiedzieć „jakie problemy można rozwiązać za pomocą komputera”, opracowaliśmy teorię obliczalności. Czy w przypadku problemów, które można obliczać, istnieje teoria, która pozwala odpowiedzieć na pytanie „czy program otrzymuję najprostszy”? Nie sądzę, aby złożoność obliczeniowa odpowiadała...
Niech GGG być połączony wykres G=(V,E)G=(V,E)G = (V,E) z węzłami V=1…nV=1…nV = 1 \dots n , a krawędzie EEE . Niech wiwiw_i oznacza (całkowitą) wagę wykresu GGG , przy czym ∑iwi=m∑iwi=m\sum_i w_i = m całkowita waga na wykresie. Średnia waga na węzeł wynosi wtedy w¯=m/nw¯=m/n\bar w = m/n . Niech...
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy....
Chociaż znane są wykładnicze separacje między złożonością kwantowych zapytań o ograniczonym ograniczeniu ( Q ( f)Q(f)Q(f) ) a złożonością deterministycznych zapytań ( D ( f)D(f)D(f) ) lub złożonością losowych zapytań o ograniczonym ograniczeniu ( R ( f)R(f)R(f) ), dotyczą one tylko niektórych...
Jestem studentem specjalizującym się w systemach rozproszonych, ale interesuję się również informatyką teoretyczną. Zastanawiałem się, czy istnieje formalna reprezentacja systemu rozproszonego na maszynie Turinga? To znaczy, czy można rozszerzyć (stworzyć wariant) koncepcję maszyny Turinga, aby...
Próby pozwalają na efektywne przechowywanie list elementów. Prefiksy są wspólne, więc zajmuje mało miejsca. Szukam podobnego sposobu skutecznego przechowywania drzew. Chciałbym móc sprawdzać członkostwo i dodawać elementy, wiedząc, czy dane drzewo jest poddrzewem niektórych przechowywanych drzew,...
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa...
Wiemy, że znalezienie wypukłego kadłuba punktów na płaszczyźnie ma dolną granicę w czasie jego działania. Jeśli jednak punkty są podane w kolejności, w jakiej występują wzdłuż prostego wielokąta, który ma te punkty jako wierzchołki, to ich wypukły kadłub można znaleźć w czasie liniowym.nnnΩ ( n...
Chciwość jest terminem nieformalnym, ale może być (nie jestem pewien, dlatego pytam), że w przypadku niektórych problemów chciwość może być sformułowana matematycznie, a zatem można udowodnić, że nie istnieje optymalny algorytm chciwości. czy to
W Bernsteina i Vazirani w przełomowej pracy „Quantum Theory Complexity”, pokazują, że redd wymiarowa przekształcenie unitarne można skutecznie przybliżony przez iloczyn co nazywają „w pobliżu trywialna obroty” i „przesunięcia fazowe niemal trywialne”. „Near-trywialne obrotów” oznaczają wymiarową...
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym,...
Z uwagi na skierowany wykres , a dwa wierzchołki s , t ∈ V . Para prostych ścieżek p 1 , p 2 od s do t jest rozłącznymi krawędziami, jeśli nie dzielą krawędzi.G = ( V, E)G=(V,E)G = (V,E)s , t ∈ V.s,t∈Vs,t \in Vp1, p2)p1,p2p_1,p_2sssttt Za pomocą maksymalnego przepływu łatwo jest zdecydować, czy...