Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

3
Złożoność decydowania, czy macierz jest całkowicie regularna
Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami? Mówiąc bardziej ogólnie, nazwij matrycę całkowicie nieregularną, jeśli wszystkie kwadratowe podmacie wielkości co najwyżej …
4
Dlaczego problem konsensusu jest tak ważny w obliczeniach rozproszonych?
W obliczeniach rozproszonych problem konsensusu wydaje się być jednym z głównych tematów, który przyciągnął intensywne badania. W szczególności artykuł „Niemożność rozproszonego konsensusu z jednym wadliwym procesem” otrzymał nagrodę PODC Influential Paper Award 2001 . Dlaczego więc problem konsensusu jest tak ważny? Co możemy osiągnąć dzięki konsensusowi zarówno w teorii, jak …
2
Obliczanie stałej Cheegera: możliwe dla jakich klas?
Obliczanie stałej Cheegera na wykresie , znanej również jako stała izoperymetryczna (ponieważ jest to zasadniczo minimalny stosunek powierzchni do objętości), jest znana jako NP-zupełna. Ogólnie jest to przybliżone. Chciałbym się dowiedzieć, czy dokładne algorytmy wielomianowe są znane dla specjalnych klas grafów. Na przykład, czy nadal jest kompletny NP dla zwykłych …
4
Złożoność obliczeniowa w finansach ilościowych
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, uczenia maszynowego i sztucznej inteligencji, ale wyniki TCS …
11
Modele losowych wykresów dla rzeczywistych sieci komputerowych
Interesują mnie modele losowych wykresów, które są podobne do wykresów rzeczywistych sieci komputerowych. Nie jestem pewien, czy wspólny dobrze zbadany model ( wierzchołków, każda możliwa krawędź jest wybierana z prawdopodobieństwem ) nadaje się do badania rzeczywistych sieci komputerowych (prawda?).n pG ( n , p )sol(n,p)G(n,p)nnnppp jakie modele losowych wykresów są …
3
Jakie algorytmy są znane z obliczania interpolantów Craiga?
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, unikając kwantyfikatorów.)A=¬p∧qA=¬p∧qA=\lnot p\land qC=qC=qC=q Tło: Interpolacja …
2
Problemy z wydajnym rozwiązaniem, z wyjątkiem niewielkiej części nakładów
Problemem zatrzymania maszyn Turinga jest być może kanoniczny nierozstrzygalny zestaw. Niemniej jednak dowodzimy, że istnieje algorytm decydujący o prawie wszystkich jego wystąpieniach. Problem zatrzymania należy zatem do rosnącej liczby osób wykazujących zjawisko teorii złożoności „czarnej dziury”, w którym trudność niewykonalnego lub nierozstrzygalnego problemu ogranicza się do bardzo małego regionu, czarnej …
5
Czy można sprawdzić, czy liczba obliczalna jest wymierna czy całkowita?
Czy możliwe jest algorytmiczne testowanie, czy liczba obliczalna jest liczbą wymierną czy całkowitą? Innymi słowy, możliwe byłoby dla biblioteki, który implementuje numery obliczalne, aby zapewnić funkcje isIntegerlub isRational? Zgaduję, że nie jest to możliwe i że jest to w jakiś sposób związane z faktem, że nie można sprawdzić, czy dwie …
18 computability  computing-over-reals  lambda-calculus  graph-theory  co.combinatorics  cc.complexity-theory  reference-request  graph-theory  proofs  np-complete  cc.complexity-theory  machine-learning  boolean-functions  combinatory-logic  boolean-formulas  reference-request  approximation-algorithms  optimization  cc.complexity-theory  co.combinatorics  permutations  cc.complexity-theory  cc.complexity-theory  ai.artificial-intel  p-vs-np  relativization  co.combinatorics  permutations  ds.algorithms  algebra  automata-theory  dfa  lo.logic  temporal-logic  linear-temporal-logic  circuit-complexity  lower-bounds  permanent  arithmetic-circuits  determinant  dc.parallel-comp  asymptotics  ds.algorithms  graph-theory  planar-graphs  physics  max-flow  max-flow-min-cut  fl.formal-languages  automata-theory  finite-model-theory  dfa  language-design  soft-question  machine-learning  linear-algebra  db.databases  arithmetic-circuits  ds.algorithms  machine-learning  ds.data-structures  tree  soft-question  security  project-topic  approximation-algorithms  linear-programming  primal-dual  reference-request  graph-theory  graph-algorithms  cr.crypto-security  quantum-computing  gr.group-theory  graph-theory  time-complexity  lower-bounds  matrices  sorting  asymptotics  approximation-algorithms  linear-algebra  matrices  max-cut  graph-theory  graph-algorithms  time-complexity  circuit-complexity  regular-language  graph-algorithms  approximation-algorithms  set-cover  clique  graph-theory  graph-algorithms  approximation-algorithms  clustering  partition-problem  time-complexity  turing-machines  term-rewriting-systems  cc.complexity-theory  time-complexity  nondeterminism 
3
Determinant modulo m
Jakie są znane skuteczne algorytmy do obliczania wyznacznikiem macierzy współczynników całkowitą o ZmZm\mathbb{Z}_m , pierścień reszt modulo mmm . Liczba mmm może nie być liczbą pierwszą, lecz złożoną (więc obliczenia są wykonywane w pierścieniu, a nie w polu). O ile mi wiadomo (czytaj poniżej), większość algorytmów jest modyfikacjami eliminacji Gaussa. …
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.