Pytania otagowane jako dc.parallel-comp

Pytania teoretyczne w obliczeniach równoległych

10
Aktualne modele równoległe do obliczeń
Lata osiemdziesiąte dały początek modelom obliczeń równoległych PRAM i BSP . Wygląda na to, że okres świetności obu modeli przypadał na przełom lat 80. i 90. Czy obszary te są nadal aktywne w zakresie badań algorytmów równoległych? Czy istnieją nowsze, bardziej wyrafinowane modele do obliczeń równoległych? Czy ogólne modele są …
6
Równoległe generatory liczb pseudolosowych
Pytanie to dotyczy przede wszystkim praktycznego problemu z inżynierią oprogramowania, ale z ciekawością dowiedziałbym się, czy teoretycy mogliby uzyskać wgląd w ten problem. Mówiąc prościej, mam symulację Monte Carlo, która korzysta z generatora liczb pseudolosowych i chciałbym go zrównoleglić, aby 1000 komputerów działało równolegle z tą samą symulacją. Dlatego potrzebuję …
3
Badanie algorytmów / złożoności algebry liniowej
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. NCfapFp\mathbb{F}_pN.doNCNC Czy znasz dobrą ostatnią ankietę lub książkę na temat złożoności …
5
Deterministyczny algorytm równoległy do ​​idealnego dopasowania na ogólnych wykresach?
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 C.NC\mathsf{NC}N C.NC\mathsf{NC} Znakomite dopasowanie problemem jest to jeden …
1
Czy rozwiązywanie układów równań modulo w dla złożone?
Interesuje mnie złożoność rozwiązywania równań liniowych modulo k , dla dowolnego k (i ze szczególnym zainteresowaniem mocami pierwotnymi), w szczególności: Problem. Czy dla danego układu równań liniowych w nieznanych modulo istnieją jakieś rozwiązania?n kmmmnnnkkk W streszczeniu swojego artykułu Struktura i znaczenie klas logspace-MOD w klasach Mod k L , Buntrock, …
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 
2
Status w dolnych granicach obwodu dla obwodów głębokości ograniczonych przez polilog
Złożoność obwodu złożoności jest jednym z głównych obszarów badań w ramach teorii złożoności obwodu. Ten temat ma swoje początki w wynikach takich jak „funkcja parzystości nie jest w ” i „funkcja mod nie jest obliczana przez ”, gdzie jest klasą języków rozstrzygalnych na podstawie niejednolitej, stałej głębokości, wielomianu, nieograniczonego wachlarza …
1
Problemy w NC nie są znane z NC2
Czy istnieją interesujące problemy, które występują w ale nie są znane w N C 2 ? W artykule „taksonomii problemów z szybkim Równoległe algorytmy” Kucharz wspomina, że MIS był znany tylko w N C 5 , ale od tego czasu została sprowadzona do N C 2 . Zastanawiam się, czy …
1
Czy istnieje algorytm kwantowy NC do obliczania GCD?
Z uwagi na jedno z moich pytań dotyczących MathOverflow mam wrażenie, że kwestia dotycząca GCD będąc w vs. P jest zbliżona do kwestii dotyczącej Integer faktoryzacji Będąc w P vs. N P .NCNC\mathsf{NC}PP\mathsf{P}PP\mathsf{P}NPNP\mathsf{NP} Czy istnieje coś takiego jak „quantum algorytm” dla GCD jak jest kwantowa wielomian czas ( B Q …
1
Algorytmy równoległe dla osiągalności w ukierunkowanych grafach płaskich
Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie pomocą procesorów O ( m + n ) .O(logn)O(logn)O({\log}n)O(m+n)O(m+n)O(m+n) Jaki jest najbardziej znany algorytm równoległy dla łączności st w ukierunkowanych grafach płaskich? Podaj czas działania, deterministyczny / losowy algorytm i zastosowany model PRAM (zakładając, …
2
Kiedy proces spawnuje inny proces
Moje doświadczenie dotyczy teorii / logiki złożoności (gdzie przez większość czasu jest tylko jeden proces) oraz przetwarzania rozproszonego (gdzie jest procesów, a jeden lub więcej może zawieść z czasem). Jednak chcę teraz móc powiedzieć coś o procesie odradzania / tworzenia / wydzielania innego procesu. Czy istnieje rygor w obliczeniach równoległych, …
3
Algorytmy równoległe dla ukierunkowanej łączności st
Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie z procesorami . Jaki jest najbardziej znany algorytm równoległy dla ukierunkowanej łączności st ? Podaj czas działania, deterministyczny / randomizowany algorytm i zastosowany model PRAM (zakładając, że liczba procesorów jest wielomianowa). Czy istnieją jakieś …
1
W jakim stopniu zdolność obliczeniowa trudnych zadań pomaga w rozwiązywaniu łatwych zadań
Krótko mówiąc, pytanie brzmi: w jakim stopniu zdolność obliczeniowa do trudnych zadań naprawdę pomaga w rozwiązywaniu łatwych zadań. (Mogą istnieć różne sposoby uczynienia tego pytania interesującym i nietrywialnym, a oto jedna z takich prób). Pytanie 1: Rozważ obwód rozwiązywania SAT dla formuły z n zmiennymi. (Lub do znalezienia cyklu hamiltonowskiego …
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.