Teoretyczne informatyka

W Załączniku B do Zwiększania i różnicowej prywatności autorstwa Dwork i wsp. Autorzy podają następujący wynik bez dowodu i nazywają go nierównością Azumy: Niech być rzeczywista zmiennymi losowymi takimi, że dla każdego ,C1,…,CkC1,…,CkC_1, \dots, C_ki∈[k]i∈[k]i \in [k] Pr[|Ci|≤α]=1Pr[|Ci|≤α]=1\Pr[|C_i| \leq \alpha] = 1 i dla każdego (c1,…,ci−1)∈Supp(C1,…,Ci−1)(c1,…,ci−1)∈Supp(C1,…,Ci−1)(c_1, \dots, c_{i - 1}) …

12 pr.probability 

Rozważam język wszystkich zadowalających formuł logicznych zdań, SAT (aby upewnić się, że ma to skończony alfabet, będziemy kodować litery zdań w odpowiedni sposób [edytuj: odpowiedzi wskazały, że odpowiedź na pytanie może nie być solidna pod różne kodowania, więc trzeba być bardziej szczegółowym - patrz moje wnioski poniżej] ). Moje proste …

12 cc.complexity-theory  circuit-complexity  sat  context-free 

Szukam pracy ankietowej na temat ważnych pojęć w dziedzinie automatów kwantowych. Znalazłem teorię automatów kwantowych - recenzję Hirvensalo, ale brzmi to zbyt zwięźle, by zrozumieć ten temat. Czy istnieje dość kompleksowa ankieta na temat automatów kwantowych? Czy mógłbyś również wskazać mi niezbędną literaturę na ten temat?

12 reference-request  quantum-computing  automata-theory 

Powiedzmy, że wykres ma właściwość M, jeśli jego wierzchołki można uporządkować v 1 , v 2 , … v n w taki sposób, że wykres H i indukowany przez wierzchołki { v 1 , … , v i } ma d i s t H i ( v j , …

12 reference-request  graph-theory 

Niech oznacza minimalny rozmiar (niemonotonowego) arytmetycznego obwodu obliczającego dany wielomianowy wielomian i oznaczają minimalny rozmiar ( obwodu logicznego obliczającego wersję logiczną z zdefiniowane przez: A(f)A(f)A(f)(+,×,−)(+,×,−)(+,\times,-)f(x1,…,xn)=∑e∈Ece∏i=1nxeii,f(x1,…,xn)=∑e∈Ece∏i=1nxiei, f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,, B(f)B(f)B(f)(∨,∧,¬)(∨,∧,¬)(\lor,\land,\neg) fbfbf_bffffb(x1,…,xn)=⋁e∈E ⋀i:ei≠0xi.fb(x1,…,xn)=⋁e∈E ⋀i:ei≠0xi. f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,. Czy znane są wielomiany dla których jest mniejsze niż ? fffB(f)B(f)B(f)A(f)A(f)A(f) Jeśli …

12 cc.complexity-theory  circuit-complexity  lower-bounds  arithmetic-circuits 

Greibach pokazowo zdefiniował język , tzw niedeterministycznych wersję z , tak że każdy CFL odwrotna morficznego obraz . Czy istnieje podobne stwierdzenie dotyczące DCFL, być może z dopuszczalnymi ograniczeniami morfizmów?HHHD2D2D_2HHH (Patrz np. M. Autebert, J. Berstel i L. Boasson. Języki bezkontaktowe i automaty wypychające. W red. R. Rozenberg i A. …

12 fl.formal-languages  open-problem  context-free  nondeterminism  hard-instances 

Biorąc pod uwagę ciąg , okładka palindromu jest sekwencją słów tak że i takie, że każdy jest palindromem.w=σ1σ2…σnw=σ1σ2…σnw=\sigma_1\sigma_2\ldots\sigma_np1p2⋯pmp1p2⋯pmp_1p_2\cdots p_mpipip_ip1p2⋯pm=wp1p2⋯pm=wp_1p_2\cdots p_m = wpipip_i Jak trudno jest znaleźć minimalną wielkość palindromu? (wydaje się to wykonalne przez programowanie dynamiczne, ale nie jestem pewien, czy to działa). Czy problem staje się trudniejszy, jeśli podany …

12 ds.algorithms  dynamic-programming  string-matching  covering-problems 

dodoC jest prostokątem równoległym do osi. do1, … , Cndo1,…,donC_1,\dots,C_ndo1∪ ⋯ ∪ C.n⊊ C.do1∪⋯∪don⊊doC_1\cup\dots\cup C_n \subsetneq C Prostokąta zachowaniem podziału na jest partycja , tak że The są parami-Wnętrze rozłączne równoległoosiowym prostokąty, a każdy : , tj. każdy istniejący prostokąt jest zawarty w unikalnym nowym prostokącie, takim jak ten:dodoCdo= E1∪ …

12 cg.comp-geom 

Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo współczynnikaN.O(e649√(logN)13(loglogN)23)O(e649(log⁡N)13(log⁡log⁡N)23)O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}}\Big)NNN Szukałem informacji o złożoności najgorszych przypadków w tym randomizowanym algorytmie. Nie mogę jednak znaleźć informacji. (1) Jaka jest …

12 reference-request  derandomization  factoring  average-case-complexity  worst-case 

Zastanawiam się, co by się stało, gdyby w definicji (wielomianowa hierarchia, patrz np. Tutaj ) rola zostałaby zastąpiona przez ?PHPHPHNPNPNPRPRPRP Wydaje się, że można jeszcze zbudować hierarchię, tak samo jak jest zbudowany, tylko za pomocą wszędzie zamiast i zamiast . Nazwijmy to Randomized Polynomial Hierarchy ( ).PHPHPHRPRPRPNPNPNPcoRPcoRPcoRPcoNPcoNPcoNPRPHRPHRPH Moje pierwsze przypuszczenie …

12 cc.complexity-theory  randomized-algorithms  randomness 

Jak mogę rozwiązać następującą relację powtarzalności? fa( n ) = f( n - 1 ) + f( n - logn )fa(n)=fa(n-1)+fa(n-log⁡n) f(n) = f(n-1) + f(n - \log n)

12 recursion 

Jestem głównym matematykiem zainteresowanym TCS. Chcę samemu przestudiować algorytmy i ich złożoność w celu rozwiązania grupowych problemów teoretycznych, takich jak znajdowanie porządku elementów, wyliczanie zbioru, wyszukiwanie generatora, testowanie, czy dany podzbiór generuje grupę. Jaką książkę powinienem przeczytać?

12 ds.algorithms  reference-request  gr.group-theory  books 

Redukcja karp jest wielomianową obliczalną w czasie wielokrotnością redukcji między dwoma problemami obliczeniowymi. Wiele redukcji Karp jest w rzeczywistości funkcjami jeden-jeden. Rodzi to pytanie, czy każda redukcja Karp jest iniekcyjna (funkcja jeden do jednego). Czy istnieje naturalny problem z całkowitym którym wiadomo, że jest całkowity tylko przy zmniejszeniu Karp o …

12 cc.complexity-theory 

'Biorąc pod uwagę , czy jest , ' jest -kompletny. x , y ∈ N a x 2 + b y = c N Pa,b,c∈Na,b,c∈Na,b,c\in\Bbb Nx,y∈Nx,y∈Nx,y\in\Bbb Nax2+by=cax2+by=cax^2+by=cNPNP\mathsf{NP} Do której klasy złożoności należy „Biorąc pod uwagę , czy istnieje , '? x , y ∈ N a x 2 + b …

12 ds.algorithms  complexity-classes  reductions  nt.number-theory  np-complete 

Wiadomo, że dodanie randomizacji błędu ograniczonego do PSPACE nie dodaje mocy. Oznacza to, że BPPSAPCE = PSPACE. Nie wiadomo, czy P = BPP, ale wiadomo, że .B P.P.⊆ Σ2)∩ Π2)BPP⊆Σ2∩Π2BPP\subseteq \Sigma_2\cap \Pi_2 Jest zatem możliwe (choć przypuszcza się, że jest to fałsz), że dodanie prawdopodobieństwa do P dodaje mocy ekspresyjnej. …

12 randomness  derandomization  polynomial-hierarchy