Pytania otagowane jako lower-bounds

Rozważ następujące naturalne pytanie: Biorąc pod uwagę skończony język , jaka jest najmniejsza bezkontekstowa gramatyka generująca ?L.L.LL.L.L Możemy uczynić pytanie bardziej interesującym, określając sekwencję języków , na przykład jest zbiorem wszystkich permutacji : intuicyjnie, CFG dla „musiałby” mieć rozmiar . Jesteśmy więc zainteresowani asymptotycznym rozmiarem najmniejszych CFG dla języków.L.nL.nL_nL.nL.nL_n{ 1 …

14 reference-request  fl.formal-languages  lower-bounds  grammars  context-free 

Czy znane są wyniki, które wykluczają istnienie struktur danych „zbyt dobrych, by były prawdziwe”? Na przykład: czy można dodać funkcjonalność SplitSplitSplit i do struktury danych obsługi zamówień (patrz Dietz i Sleator STOC '87 ) i nadal uzyskiwać operacje czasowe ?JoinJoinJoinO(1)O(1)\mathcal{O}(1) Lub: czy można zaimplementować uporządkowany zestaw z kluczami całkowitymi i …

14 ds.data-structures  big-list  lower-bounds  time-complexity 

Problem #SAT jest kanonicznym problemem # P-zupełnym. Jest to raczej problem funkcji niż problem decyzyjny. Pyta, biorąc pod uwagę wartość logiczną formuła w rachunku zdań, ilu spełniających zadania F ma. Jakie są najlepsze dolne granice na #SAT?fafaFfafaF

14 cc.complexity-theory  lower-bounds  sat  counting-complexity 

Istnieje wiele dobrze znanych C 0 wielkości obwód dolny związanego wyniki w oparciu o losowe ograniczeń i przełączania lematu .AC0AC0\mathsf{AC^0} Czy możemy opracować wynik zamiany lematu, aby udowodnić niższą wielkość dla obwodów TC0TC0\mathsf{TC^0} (podobnie do dolnej granicy dla AC0AC0\mathsf{AC^0} )? Czy jest jakaś nieodłączna przeszkoda w stosowaniu tego podejścia do …

13 cc.complexity-theory  circuit-complexity  lower-bounds  boolean-functions 

Istnieje kilka dowodów na dolną granicę logiczną dla problemu wyjątkowości / odrębności elementu (opartej na drzewach obliczeń algebraicznych lub argumentach przeciwnych), ale szukam takiego, który byłby wystarczająco prosty do zastosowania w pierwszym kursie analizy i projektowania algorytmów. Taki sam „poziom trudności” jak dolna granica sortowania byłby w porządku. Również każde …

13 cc.complexity-theory  lower-bounds  proofs 

Łatwo jest zweryfikować, że biorąc pod uwagę wymiarową siatkę punktów całkowitych , przy regularnym sąsiedztwie można znaleźć separator o rozmiarze (wystarczy wybrać dowolny środkowy hiperpłaszczyzna i usuń wszystkie jego wierzchołki). Nie jest też zbyt trudne (ale zdecydowanie nie natychmiastowe) sprawdzenie, czy każdy separator musi mieć rozmiar \ Omega (n ^ …

13 reference-request  cg.comp-geom  lower-bounds 

Wiadomo, że problem zatrzymania jest niemożliwy do obliczenia. Możliwe jest jednak wykładnicze „kompresowanie” informacji o problemie zatrzymania, tak aby dekompresowanie było możliwe do obliczenia. Dokładniej, można obliczyć na podstawie opisu maszyn Turinga, a n- bitowa porada stanowi odpowiedź na problem zatrzymania dla wszystkich 2 n - 1 maszyn Turinga, przy …

12 computability  lower-bounds  turing-machines  communication-complexity  oracles 

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 

w 1979 r. Hopcroft / Ullman napisał, że L ⊆ P ⊆ NP ⊆ PSpace jest znany, ale L ⊊ PSpace jest jedynym właściwym (i trywialnym) zabezpieczeniem znanym, chociaż wszystkie są przypuszczane, że są odpowiednimi zabezpieczeniami i „tam, gdzie rzeczy nadal istnieją” ~ 4 dekady później . od tego czasu …

12 cc.complexity-theory  reference-request  lower-bounds  p-vs-np  conditional-results 

Jak wykazać, że pewna właściwość nie może być wyrażona w 2-CNF (2-SAT)? Czy są jakieś gry, takie jak gry z kamieniami? Wygląda na to, że klasyczna gra w czarne kamyki i gra w czarno-białe kamyki są do tego nieodpowiednie (są one kompletne w PSPACE, według Hertela i Pitassi, SIAM J …

12 sat  lower-bounds  combinatorial-game-theory 

b a b azaaabbbzaaabbbzaaabbbO ( m logm loglogm )O(mlog⁡mlog⁡log⁡m)O(m\log m\log\log m)mmmΩ ( m log m log log m )max { a , b }max{a,b}\max\{a,b\}Ω ( m logm loglogm )Ω(mlog⁡mlog⁡log⁡m)\Omega(m\log m\log\log m) dolna granica tego problemu? Dziękuję i pozdrawiam, i przepraszam, jeśli to takie naiwne pytanie.

12 time-complexity  lower-bounds  nt.number-theory  primes 

Wagaciągu binarnego to liczba jedynek w ciągu. Co się stanie, jeśli będziemy zainteresowani obliczeniem funkcji monotonicznej na wejściach z kilkoma?x ∈ { 0 , 1 } n| x ||x||x|x ∈ { 0 , 1 }nx∈{0,1}nx\in\{0,1\}^n Wiemy, że podjęcie decyzji, czy wykres ma klasę jest trudne dla obwodów monotonicznych (patrz między …

12 cc.complexity-theory  lower-bounds  circuit-complexity  parameterized-complexity  monotone 

Jakie są standardowe problemy, które możemy zredukować, aby udowodnić dolne granice ?Ω ( n logn )Ω(nlog⁡n)\Omega(n\log n) Oczywiście problemy ze stanem inne niż sortowanie i rozróżnianie elementów.

12 cc.complexity-theory  lower-bounds 

Jest to pytanie uzupełniające do poprzedniego postu Robina Kothari na temat wyników twardości wielomianowej . Interesuje mnie w szczególności sprawdzenie niektórych dowodów twardości dla problemów, które mają z grubsza dolne granice, i mówię z grubsza, aby pozwolić na nieco subkubiczne ulepszenia, grając z rozmiarem słowa (np. 3SUM autorstwa Barab i …

12 graph-theory  cg.comp-geom  lower-bounds 

To pytanie jest inspirowane istniejącym pytaniem, czy stos można symulować przy użyciu dwóch kolejek w zamortyzowanym czasie na operację stosu. Odpowiedź wydaje się nieznana. Oto bardziej szczegółowe pytanie, odpowiadające specjalnemu przypadkowi, w którym najpierw wykonywane są wszystkie operacje PUSH, a następnie wszystkie operacje POP. Jak skutecznie można odwrócić listę N …

12 ds.algorithms  ds.data-structures  lower-bounds  time-complexity  sorting