Pytania otagowane jako cc.complexity-theory

W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie O ( n √nnn i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.O(nlogn−−−−√),O(nlog⁡n),O(n \sqrt{\log n}), Jeśli jest poprawny, byłoby to, moim zdaniem, znaczące, przynajmniej teoretycznie. Przedstawienie głównego argumentu jest jednak nieco …

12 cc.complexity-theory  ds.algorithms  sorting 

Wyobraźmy sobie, że mamy dwa zestawy rozmiarów punktów . Jaka jest (czasowa) złożoność testowania, jeśli różnią się one tylko rotacją? : istnieje macierz rotacji taka, że ?mmmX,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^nOOT=OTO=IOOT=OTO=IOO^T=O^TO=IX=OYX=OYX=OY Istnieje tutaj problem reprezentowania rzeczywistych wartości - dla uproszczenia załóżmy, że dla każdej współrzędnej istnieje (krótki) wzór algebraiczny, tak że koszt podstawowych …

12 cc.complexity-theory  complexity-classes  graph-isomorphism  computational-geometry  high-dimensional-geometry 

Twierdzenie o hierarchii czasu stwierdza, że ​​maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …

12 cc.complexity-theory  complexity-classes  turing-machines  space-bounded  time-hierarchy 

Gęstość języka jest funkcją zdefiniowano jako Załóżmy, i są to języki na pewną skończoną alfabetu wielu jeden logspace redukuje się do , a jest w . Funkcje są wielomianowo powiązane, jeśli istnieją wielomiany i takie, że dla wszystkich , id X : N → N d X ( n ) …

12 cc.complexity-theory  reductions  structural-complexity 

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 

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 

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 

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 

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 

oznacza N P ⊆ P / P O l y , który z kolei ma wpływ interesujące jak załamania wielomianu hierarchii.P/poly=NP/polyP/poly=NP/polyP/poly = NP/polyNP⊆P/polyNP⊆P/polyNP \subseteq P/poly Czy są interesujące implikacje dla ?P/poly≠NP/polyP/poly≠NP/polyP/poly \neq NP/poly

12 cc.complexity-theory  conditional-results  advice-and-nonuniformity 

Szukam listy o znanej lub nieznanej złożoności różnych problemów teoretycznych / algebraicznych. Na przykład, GCD w jest otwarty,N.do1NC1NC^1 faktoring w jest otwarty,P.PP obliczanie kohomologii snopów to -hard# P#P\#P , Arora i Barak stwierdzają, że wariant faktoringu jest -Complete (choć nie jest jasne, na podstawie dyskusji na NP-zupełnym wariantu faktoringu. ),N.P.NPNP …

12 cc.complexity-theory  big-list  algebra  open-problem 

Naturalna bariera dowodowa Razborova i Rudicha mówi, że przy wiarygodnych założeniach kryptograficznych nie można mieć nadziei na oddzielenie NP od P / poli poprzez znalezienie kombinatorycznych właściwości funkcji, które są konstruktywne, duże i użyteczne. Istnieje kilka dobrze znanych wyników, które potrafią ominąć barierę. Istnieje również kilka artykułów omawiających możliwe luki …

12 cc.complexity-theory  circuit-complexity 

Niech będzie funkcją logiczną o czułości s ( f ) i czułości bloku b s ( f ) .fafafs ( f)s(fa)s(f)b s ( f)bs(fa)bs(f) Hipoteza domniemania czułości według bloku czułości stwierdza, że ​​istnieje takie, że ∀ f , b s ( f ) ≤ s ( f ) c .c …

12 cc.complexity-theory  big-picture  boolean-functions  survey 

Strona wikipedii na PSPACE wspomina, że ​​włączenie nie jest znane jako ścisłe (niestety bez odnośników).NL⊂PHNL⊂PHNL\subset PH P1: Co z i - czy są one znane jako ścisłe?L⊂PHL⊂PHL\subset PHL⊂P#PL⊂P#PL\subset P^{\#P} P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie wiadomo, czy włączenie jest ścisłe?CCCP#PP#PP^{\#P}L⊂CL⊂CL\subset C P3: Czy …

12 cc.complexity-theory  complexity-classes  logspace 

Wejściowego, to świat i rodzina podzbiorów , powiedzmy, . Zakładamy, że w podzbiory może obejmować , czyli .UUUUUUF⊆2UF⊆2U{\cal F} \subseteq 2^UFF{\cal F}UUU⋃E∈FE=U⋃E∈FE=U\bigcup_{E\in {\cal F}}E=U Przyrostowe sekwencja Pokrycie jest ciągiem podzbiorów w , powiedzmy, , który spełniafaF{\cal F}ZA= { E1, E2), … , E| ZA|}A={E1,E2,…,E|A|}{\cal A}=\{E_1,E_2,\ldots,E_{|{\cal A}|}\} 1) ,∀ E∈ A, …

12 cc.complexity-theory  ds.algorithms  approximation-algorithms  optimization  set-cover