Teoretyczne informatyka

Ostatnio otrzymuję odrzucenie moich artykułów z czasopism (tj. TALG) z tego powodu, że nie mam znaczącej różnicy między wersją czasopisma a wersją postępowania (tj. SODA). Głównym powodem, dla którego przesyłam do czasopisma, jest jego dokładny proces recenzji. Poza tym, limit 20 stron SODA to więcej niż wszystko, co chcę powiedzieć. …

23 soft-question  research-practice  conferences  journals 

Widoczna jest redukcja z CLIQUE na k-Color, ponieważ oba są NP-Complete. W rzeczywistości mogę go zbudować, tworząc redukcję z CLIQUE do 3-SAT z redukcją z 3-SAT do k-Color. Zastanawiam się, czy istnieje rozsądna bezpośrednia redukcja między tymi problemami. Powiedzmy, redukcję, którą mógłbym wyjaśnić przyjacielowi dość krótko, bez potrzeby opisywania języka …

23 cc.complexity-theory  graph-theory  np-hardness  reductions 

W obliczeniach kwantowych często interesują nas przypadki, w których grupa specjalnych operatorów unitarnych, G, dla jakiegoś systemu d-wymiarowego daje dokładnie całą grupę SU (d), a nawet tylko przybliżenie zapewniane przez gęstą osłonę SU (d). Grupa skończonego rzędu, taka jak grupa Clifforda dla układu d-wymiarowego C (d), nie zapewni gęstej osłony. …

23 quantum-computing 

W obecnej formie to pytanie nie pasuje do naszego formatu pytań i odpowiedzi. Oczekujemy, że odpowiedzi poparte będą faktami, referencjami lub wiedzą fachową, ale to pytanie prawdopodobnie będzie wymagało debaty, argumentów, ankiet lub rozszerzonej dyskusji. Jeśli uważasz, że to pytanie można poprawić i ewentualnie ponownie otworzyć, odwiedź centrum pomocy w …

23 soft-question  big-list  paper-review 

Czy ktoś może zasugerować dobrą i najnowszą ankietę na temat liczenia problemów i / lub problemów, które są #P.

23 cc.complexity-theory  reference-request  counting-complexity 

W praktyce, dla języka, który można ostatecznie skompilować / przekształcić w instrukcje na poziomie systemu, czy konieczne jest, aby była to gramatyka bezkontekstowa? np .: Czy wszystkie języki programowania / skryptów są wolne od kontekstu? Java oparta jest na CFG, ale czy w rzeczywistości wszystkie języki programowania są oparte na …

23 pl.programming-languages  context-free 

To pytanie zostało przeniesione z Cross Validated, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 8 lat temu . Mam dość unikalny problem do rozwiązania i mam nadzieję, że ktoś tutaj da mi wgląd w to, jak najlepiej go rozwiązać. Problem: Załóżmy, że lista N liczb …

23 cr.crypto-security  dc.distributed-comp  st.statistics  privacy 

Komputery kwantowe są bardzo dobre do dystrybucji próbkowania, których nie wiemy jak próbkować przy użyciu klasycznych komputerów. Na przykład, jeśli f jest funkcją logiczną (od do ), którą można obliczyć w czasie wielomianowym, to za pomocą komputerów kwantowych możemy skutecznie próbkować zgodnie z rozkładem opisanym przez Rozwinięcie Fouriera f. (Nie …

23 quantum-computing  cg.comp-geom  optimization 

Co wiadomo o złożoności znalezienia minimalnych obwodów, które obliczają SAT do długości ? nnn Bardziej formalnie: jaka jest złożoność funkcji, która, biorąc pod uwagę jako wejście, generuje minimalny obwód taki, że dla dowolnej formuły z , ?1n1n1^{n}CCCφφ\varphi|φ|≤n|φ|≤n|\varphi| \leq nC(φ)=SAT(φ)C(φ)=SAT(φ)C(\varphi) = SAT(\varphi) (Szczególnie interesują mnie dolne granice). Naiwny deterministyczny algorytm (oblicz …

23 cc.complexity-theory  sat 

Prawdopodobnie najczęstszym zastosowaniem typów liniowych w PL jest użycie ich do nadania języków, które kontrolują aliasing (tzn. Wartość liniowa ma mniej więcej jeden wskaźnik). Ale istnieje niewielkie niedopasowanie między tym użytkowaniem a typowymi denotacyjnymi modelami logiki liniowej. IIRC, Benton wykazał, że jeśli kartezjańska zamknięta kategoria ma silną przemienną monadę, to …

23 pl.programming-languages  ct.category-theory  imperative-programming  denotational-semantics  linear-logic 

Interesuje mnie problem pakowania identycznych kopii (2-wymiarowych) prostokątów w wypukły (2-wymiarowy) wielokąt bez nakładania się. W moim problemie nie wolno obracać prostokątów i można założyć, że są one ustawione równolegle do osi. Właśnie podano wymiary prostokąta i wierzchołki wielokąta i zapytano, ile identycznych kopii prostokąta można upakować w wielokącie. Uważam, …

23 reference-request  np-hardness  cg.comp-geom  optimization  packing 

Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …

23 cc.complexity-theory  ds.algorithms  graph-theory  space-bounded  treewidth 

To pytanie jest związane z odpowiedzią, którą opublikowałem w odpowiedzi na inne pytanie. Problemem z 3 partycjami jest następujący problem: Instancja : dodatnie liczby całkowite a 1 ,…, a n , gdzie n = 3m, a suma n liczb całkowitych jest równa mB, tak że każda a i spełnia B …

23 cc.complexity-theory  np-hardness 

mmmnnnm≫nm≫nm \gg nXiXiX_iiiiXmaxXmaxX_\maxXminXminX_\minXsec−maxXsec−maxX_{\mathrm{sec-max}}Xi−Xj∼N(0,2m/n)Xi−Xj∼N(0,2m/n)X_i - X_j \sim N(0,2m/n)|Xi−Xj|=Θ(m/n−−−−√)|Xi−Xj|=Θ(m/n)|X_i - X_j| = \Theta(\sqrt{m/n}) i,ji,ji,jXmax−Xmin=O(mlogn/n−−−−−−−−√)Xmax−Xmin=O(mlog⁡n/n)X_{\max} - X_{\min} = O(\sqrt{m\log n/n})n/2n/2n/2 pary rozłącznych pojemników. Ten (nie do końca formalny) argument prowadzi nas do oczekiwania, że ​​różnica między XmaxXmaxX_{\max} aXminXminX_{\min} to Θ(mlogn/n−−−−−−−−√)Θ(mlog⁡n/n)\Theta(\sqrt{m\log n/n}) z dużym prawdopodobieństwem. Interesuje mnie różnica między XmaxXmaxX_\max a Xsec−maxXsec−maxX_{\mathrm{sec-max}} . Przedstawiony …

23 reference-request  pr.probability 

Gdzie mogę znaleźć wykresy dotyczące rzeczywistych problemów? Dwa znane mi repozytoria: Kolekcja rzadkich matryc University of Florida Bodlaender's TreewidthLib

23 graph-theory  big-list  co.combinatorics  data-sets