Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest...
Szukam materiału instruktażowego, który obejmuje dowody poprawności kompilatora, najlepiej przy użyciu metod denotacyjnych, na poziomie początkującego studenta. Alternatywnie, czy znasz kilka prostych przykładów kompilatora, których mógłbym zilustrować problemy? (Pierwszym przykładem, który...
Łańcuch dodatek jest ciągiem liczb naturalnych , gdzie x 1 = 1 , a każdy wskaźnik i ≥ 2 mamy x ı = x j + x k kilku wskaźników 1 ≤ j , k < i . Długość łańcucha addycji N ; docelowej sieci addycji x( x1, x2), … , Xn)(x1,x2,…,xn)(x_1, x_2, \dots, x_n)x1= 1x1=1x_1 = 1i ≥ 2i≥2i\ge 2xja= xjot+...
Jakie są znane wyniki znalezienia dokładnej n-wymiarowej podtablicy wewnątrz n-wymiarowej tablicy? W 1D jest to tylko problem dopasowania łańcucha, KMP robi to w czasie liniowym. W 2D ten dokument pokazał, że można to zrobić w czasie liniowym z niewielką dodatkową przestrzenią. Czy ten problem...
Klasycznym problemem w teorii prawdopodobieństwa jest wyrażenie prawdopodobieństwa zdarzenia w kategoriach bardziej specyficznych zdarzeń. W najprostszym przypadku można powiedzieć . Write LET'S za zdarzenie .A B A ∩ BP[A∪B]=P[A]+P[B]−P[A∩B]P[A∪B]=P[A]+P[B]−P[A∩B]P[A \cup B] = P[A] + P[B] - P[A...
Mam dwa historyczne pytania: Kto pierwszy opisał obliczenia niedeterministyczne? Wiem, że Cook opisał problemy z NP-zupełnością i że Edmonds zaproponował, że algorytmy P są algorytmami „wydajnymi” lub „dobrymi”. Przeszukałem ten artykuł w Wikipedii i odszukałem „O złożoności obliczeniowej...
Chociaż twierdzenie Adlemana pokazuje, że , nie znam żadnej literatury badającej możliwe włączenie . Jakie konsekwencje teoretyczne pod względem złożoności miałoby takie włączenie?BPP⊆P/polyBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}BQP⊆P/polyBQP⊆P/poly\mathsf{BQP} \subseteq...
Szukam dobrej ankiety na temat algorytmów i złożoności algebry liniowej (operacje takie jak rank, inverse, wartości własne, ... dla Boolean, oraz liczby całkowite / racjonalne) z naciskiem na równoległość ( hierarchia ) i algorytmy politime. Nie mogłem znaleźć ostatniego....
Załóżmy, że wykres z n wierzchołkami jest przedstawiony jako strumień m krawędzi, ale nad strumieniem dozwolonych jest wiele przejść.solGGnnnmmm Monika Rauch Henzinger, Prabhakar Raghavan i Sridar Rajagopalan zauważyli, że przestrzeń jest niezbędna do ustalenia, czy istnieje ścieżka między dwoma...
W klasie złożoności istnieją pewne domniemania, że NIE występują w klasie , tj. Problemy z deterministycznymi algorytmami równoległymi. Problem maksymalnego przepływu jest jednym z przykładów. I są problemy, WIĘCEJ, że są w , ale dowód jeszcze nie został znaleziony.N C N C.P.P\mathsf{P}N...
Czy przeprowadzono badania nad implementacją konstrukcji ekstraktorów losowości? Wydaje się, że proofy ekstraktora wykorzystują Big-Oh, pozostawiając możliwość dużych, ukrytych stałych, czyniąc implementacje programowe potencjalnie nierealnymi. Trochę kontekstu: jestem zainteresowany...
Wikipedia podaje przykłady problemów, w których liczenie wersji jest trudne, natomiast wersja decyzyjna jest łatwa. Niektóre z nich liczą doskonałe dopasowania, licząc liczbę rozwiązań SAT i liczbę sortowań topologicznych.222 Czy są jeszcze jakieś inne ważne klasy (powiedzmy przykłady z sieci,...
W moich badaniach pojawił się ostatnio następujący interesujący problem: INSTANCJA: Wykres .G ( V, E)G(V,E)G(V, E) ROZWIĄZANIE: Zakończenie akordu nieparzystego cyklu nieparzystego, zdefiniowane jako nadzbiór zestawu krawędzi tak że skompletowany wykres ma właściwość polegającą na tym, że każda...
To pytanie jest podobne do bardziej ogólnego pytania dotyczącego tego, jaki jest właściwy model teoretyczny komputera do projektowania algorytmów i struktur danych. Tutaj pytam konkretnie o obecne komputery o wysokiej wydajności (takie jak te wymienione na liście 500 najlepszych ), a nawet o...
(To pytanie jest trochę „ankietą”). Aktualnie pracuję nad problemem, w którym próbuję podzielić krawędzie turnieju na dwa zestawy, z których oba są wymagane do spełnienia niektórych właściwości strukturalnych. Problem „czuje się” bardzo trudne, a ja w pełni się spodziewać, że będzie...
Czy istnieje przegląd algorytmów obliczania interpolantów? Co z artykułami na temat tylko jednego algorytmu? Najbardziej interesuje mnie przypadek i C = q plus ograniczenie, że interpolant jest tak mały, jak to możliwe. (Znam pracę McMillana z 2005 roku , która opisuje, jak uzyskać interpolanty,...
Jaka jest złożoność czasowa (nie złożoność zapytań) algorytmu Grovera? Wydaje mi się jasne, że jest to ponieważ istnieją iteracje i każda iteracja wymaga użycia operacji odbicia, która z kolei wymaga czasu przy użyciu dowolnego standardowego zestawu bram
Prognozowanie rynku akcji jest trudne! Czy TCS może uczynić ten sentyment bardziej formalnym? Ostatnio zacząłem trochę myśleć o finansach i zastanawiałem się, w jaki sposób wiedza TCS może pomóc. Fundusze hedgingowe i firmy inwestycyjne wydają się cały czas korzystać z handlu algorytmicznego,...
W adiabatycznym obliczeniu kwantowym (AQC) koduje się rozwiązanie problemu optymalizacji w stanie podstawowym [problemu] Hamiltoniana . Aby dojść do tego stanu podstawowego, zaczynasz w łatwym do stanie początkowym (podstawowym) z Hamiltonianem i „wyżarzaniem” ( adiabatycznym) w kierunku , tj.H i H...
Pytanie główne / ogólne Niech LLL będzie językiem. Zdefiniuj języki LiLiL_i pomocą L0=LL0=LL_0 = L i Li={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\} dla i≥1i≥1i \geq 1 . Rozważmy L = ⋃ l i . Tak więc wielokrotnie „osadzić” L w siebie, aby uzyskać L...