Teoretyczne informatyka

Obserwacja związana z kryptografią asymetryczną jest taka, że ​​niektóre funkcje są (uważa się) za łatwe do wykonania w jednym kierunku, ale trudne do odwrócenia. Ponadto, jeśli istnieje jakaś informacja „zapadni”, która pozwala na szybkie obliczenie operacji odwrotnej, problem staje się kandydatem do schematu kryptografii klucza publicznego. Klasyczne problemy z zapadniami, …

13 cc.complexity-theory  cr.crypto-security  homomorphic-encryption 

Próbując rozwiązać problem, ostatecznie wyraziłem jego część jako następujący program liczbowy całkowity. Tutaj są dodatnimi liczbami całkowitymi podanymi jako część danych wejściowych. Określony podzbiór zmiennych jest ustawiony na zero, a reszta może przyjmować dodatnie wartości całki:ℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,wℓ,m,n1,n2,…,nℓ,c1,c2,…,cm,w\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},wxijxijx_{ij} Zminimalizować ∑mj=1cj∑ℓi=1xij∑j=1mcj∑i=1ℓxij\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij} Z zastrzeżeniem: ∑mj=1xij=ni∀i∑j=1mxij=ni∀i\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i ∑ℓi=1xij≥w∀j∑i=1ℓxij≥w∀j\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j Chciałbym wiedzieć, czy ten program …

13 reference-request  linear-programming  polynomial-time  integer-programming  integrality-gap 

Ostatnio zastanawiałem się nad wprowadzeniem do algorytmów holograficznych. Natknąłem się na obiekty kombinatoryczne zwane Pfaffians. W tej chwili tak naprawdę niewiele o nich wiem i natknąłem się na zaskakujące zastosowania, które można zastosować. Na przykład dowiedziałem się, że można ich używać do skutecznego liczenia liczby idealnych dopasowań na wykresach płaskich. …

13 reference-request  co.combinatorics  counting-complexity 

Niech będzie klasą grafów z ograniczoną szerokością kliki. Na każdym wykresie w G niektóre krawędzie są skurczone (np. Losowo). Czy teraz szerokość kliki jest nadal ograniczona?solGGsolGG W przypadku, gdy (ogólnie) nie jest już ograniczony, byłbym bardzo zainteresowany kontrprzykładem.

13 graph-theory  co.combinatorics  cliquewidth 

i N L o g T i m e są dwiema najmniejszymi klasami złożoności, jakie mamy. (Należy zauważyć, że w czasie logarytmicznej hierarchia l H jest równe A C 0 i są dwa pierwsze poziom L H ).DLogTimeDLogTime\mathsf{DLogTime}NLogTimeNLogTime\mathsf{NLogTime}LHLH\mathsf{LH}AC0AC0\mathsf{AC}^0LHLH\mathsf{LH} Po zapoznaniu się pytanie , staję się interesuje, czy odstęp pomiędzy tymi …

13 cc.complexity-theory  circuit-complexity 

Oto problem: W niektórych komórkach mamy kwadrat z niektórymi liczbami od 1..N. Trzeba ustalić, czy można go ukończyć na magiczny kwadrat. Przykłady: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION …

13 cc.complexity-theory  np-hardness  np  puzzles 

Podczas eksploracji różnych technik dowodzenia dolnych granic dla algorytmów rozproszonych przyszło mi do głowy, że następujący wariant twierdzenia Ramseya może mieć zastosowania - jeśli to prawda. Podano parametry: kkk , KKK , nnn , a następnie wybrano NNN aby było wystarczająco duże. Terminologia: podzbiór mmm jest podzbiorem rozmiaru mmm . …

13 reference-request  co.combinatorics  ramsey-theory 

Hamiltona Cykl Problem (HC) polega na znalezieniu cykl, który przechodzi przez wszystkie wierzchołki w danym undirected wykresu. Problem komiwojażera (TSP), polega na znalezieniu się cykl, który przechodzi przez wszystkie wierzchołki w danej krawędzi wykresu ważonych minimalizuje całkowitą odległość, mierzoną przez sumę mas krawędzi w cyklu. HC jest szczególnym przypadkiem TSP …

13 cc.complexity-theory  np-hardness  hamiltonian-paths  tsp  graph-classes 

Wiele klas złożoności zdefiniowanych za pomocą maszyn Turinga ma definicje w kategoriach jednorodnych obwodów. Na przykład P można również zdefiniować za pomocą obwodów o jednorodnych rozmiarach wielomianowych, podobnie BPP, NP, BQP itp. Można zdefiniować za pomocą obwodów jednorodnych. Czy istnieje oparta na obwodzie definicja L? Oczywistym pomysłem byłoby dopuszczenie obwodów …

13 cc.complexity-theory  complexity-classes  circuit-complexity 

Szukałem mnożenia macierzy, więc najpierw odwiedziłem algorytmy mnożenia macierzy wiki. W referencjach znalazłem artykuł, który twierdzi, że używa algorytmu O ( n2)l o g( n ) )O(n2)losol(n))O(n^2 log(n)) , chciałbym przeczytać artykuł, ale jest skomplikowany i zajmie zbyt wiele czasu, aby go przeczytać, ale jeśli jest ktoś, kto czyta ten …

13 ds.algorithms  linear-algebra  matrix-product 

Zadałem to pytanie w sprawdzonych krzyżowo pytaniach i odpowiedziach, ale wydaje się, że jest ono bardziej związane z CS niż ze statystykami. Czy możesz podać mi przykłady algorytmów uczenia maszynowego, które uczą się na podstawie właściwości statystycznych zestawu danych, a nie samych indywidualnych obserwacji, tj. Wykorzystują statystyczny model zapytań ?

13 lg.learning  machine-learning 

Istnieją dwa główne typy awarii procesorów w modelach przetwarzania rozproszonego: (1) Awarie awarii: procesor zatrzymuje się i nigdy nie uruchamia się ponownie. (2) Awarie bizantyjskie: procesory zachowują się przeciwnie, złośliwie. Moje pytanie brzmi: Jakie inne rodzaje awarii procesorów, które zostały zbadane, które nie ograniczają się do awarii lub awarii bizantyjskich? …

13 reference-request  dc.distributed-comp 

Niech p ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) jest wielomianem wielu zmiennych współczynnikach nad polem faFF . Multilinearization z ppp , oznaczony przez P , jest wynikiem zastąpienia wielokrotnie każdy x d I o d > 1 o x i . Wynikiem jest oczywiście wielomianowy wielomian.p^p^\hat{p}xrejaxidx_i^dre> 1d>1d > 1xjaxix_i Rozważmy następujący …

13 cc.complexity-theory  polynomials 

Powiedzmy, że mamy jednowarstwową sieć neuronową z przekazywaniem danych z k wejściami i jednym wyjściem. Oblicza funkcję z , dość łatwo zauważyć, że ma ona co najmniej taką samą moc obliczeniową jak A C 0 . Dla zabawy nazwiemy zestaw funkcji obliczalnych przez jednowarstwową sieć neuronową „ N e u …

13 cc.complexity-theory  circuit-complexity  machine-learning  ne.neural-evol 

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, …

13 dc.parallel-comp  process-algebra