W związku z układanką Slither Link zastanawiałem się: Załóżmy, że mam siatkę kwadratowych komórek i chcę znaleźć prosty cykl krawędzi siatki, równomiernie losowy wśród wszystkich możliwych prostych cykli.n × nn×nn\times n Jednym ze sposobów na to byłoby użycie łańcucha Markowa, którego stanami są...
Podczas gry z moim GPS sformułowałem następujący problem. Oto on: Niech będzie grafem ukierunkowanym, tak że jeśli to , tj. jest orientacją leżącego u jego podstaw wykresu niekierowanego. Rozważ następujące operacje:e = ( u , v ) ∈ E ( v , u ) ∉ E GG ( V, E)G(V,E)G(V,E)e = ( u , v ) ∈...
Dużo czytałem o systemach typów i takie i rozumiem z grubsza, dlaczego zostały wprowadzone (w celu rozwiązania paradoksu Russela). Rozumiem też z grubsza ich praktyczne znaczenie w językach programowania i systemach sprawdzających. Nie jestem jednak do końca pewien, czy moje intuicyjne wyobrażenie...
Ponieważ w Lambda Ultimate nie było odpowiedzi , próbuję tutaj jeszcze raz: systemy przepisywania terminów są używane na przykład w automatycznym twierdzeniu potwierdzającym obliczenia symboliczne i oczywiście do zdefiniowania gramatyki formalnej. Istnieje kilka języków programowania opartych na...
Pytanie: Jaka jest najbardziej znana dolna granica rozmiaru formuły dla jawnej funkcji w AC 0 ? Czy istnieje wyraźna funkcja z dolną granicą ?Ω(n2)Ω(n2)\Omega(n^2) Tło: Podobnie jak większość dolnych granic, dolne granice formuł są trudne do osiągnięcia. Interesują mnie dolne granice formuły...
Niedawno czytałem parser Earley i uważam, że jest to jeden z najbardziej eleganckich algorytmów, jakie do tej pory widziałem. Jednak algorytm w tradycyjnym znaczeniu jest rozpoznawaczem, a nie analizatorem składni, co oznacza, że może wykryć, czy łańcuch pasuje do określonego CFG, ale nie...
Rozwiązują SAT są bardzo ważne w algebraicznych ataków , na przykład walksat i minisat . Jednak przy rozwiązywaniu problemów z testami porównawczymi dostępnymi tutaj istnieje ogromna różnica w wydajności między nimi - Walksat jest znacznie szybszy niż minisat dla tych problemów. Dlaczego to? Ta...
Jak stwierdzono w tytule, zastanawiam się nad jakąkolwiek relacją i różnicą między CIC a ITT. Czy ktoś mógłby mi wyjaśnić lub wskazać mi literaturę porównującą te dwa systemy?
W rezultacie przez Robertson Seymour wykazuje algorytm do testowania, czy stałej wykres jest minor . Mam dwa i pół pytania na ten temat:O ( n3))O(n3))O(n^3)solsolGH.H.H 1) Wygląda na to, że od tego czasu wprowadzono ulepszenia tego algorytmu. Jaki jest obecnie najbardziej znany algorytm? 2a) Co...
Czytałem w kilku artykułach, że powszechnie uważa się istnienie funkcji jednokierunkowych . Czy ktoś może wyjaśnić, dlaczego tak jest? Jakie mamy argumenty za poparciem istnienia funkcji
Będę uczestniczył w mojej pierwszej konferencji informatycznej i po przeczytaniu porady, jak ulepszyć konferencje , zauważyłem, że kilka sugestii dotyczyło studentów na pierwszej konferencji. Jakie masz rady dla ucznia uczestniczącego w jego pierwszej konferencji i na czym powinien się...
Załóżmy, że mamy klasę obiektów (np. Wykresy, ciągi) i relację równoważności tych obiektów. W przypadku wykresów może to być izomorfizm wykresów. W przypadku ciągów moglibyśmy zadeklarować dwa równoważne ciągi, jeśli są one wzajemnie anagramami. Jestem zainteresowany obliczeniem przedstawiciela...
Biorąc pod uwagę nieukierunkowany i nieważony wykres a jeszcze całkowita k , co jest złożoność obliczeniowa zestawów zliczania wierzchołków S ⊆ V tak, że | S | = k, a podgrupa G ograniczona do zbioru wierzchołków S dopuszcza idealne dopasowanie? Czy złożoność # P jest kompletna? Czy istnieje...
To pytanie powstaje z czystej ciekawości (pojawiło się podczas myślenia o odtasowaniu łańcucha , ale nie jestem pewien, czy jest rzeczywiście powiązane), więc mam nadzieję, że jest odpowiednie. Istnieje wiele produktów graficznych i interesuje mnie którykolwiek z nich. Jaka jest złożoność...
Tom III sztuki programowania komputerowego Knutha (rozdział 5, werset 3.2) zawiera poniższą tabelę zawierającą dokładną minimalną liczbę porównań wymaganych do wybrania tego najmniejszego elementu z nieposortowanego zestawu wielkości , dla wszystkich . Ta tabela, wraz z dobrze znanymi wyrażeniami...
Co wiadomo na temat złożoności następującego problemu: Biorąc pod uwagę: liczby wymierne x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n . Wyjście: liczby całkowite y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n . Cel: zminimalizować ∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1...
Lemma regularności Szemerediego mówi, że każdy gęsty wykres może być aproksymowany jako połączenie O ( 1 )O(1)O(1) wielu dwustronnych grafów ekspanderów. Dokładniej, istnieje podział większości wierzchołków na zestawy O ( 1 )O(1)O(1) tak że większość par zestawów tworzy dwustronne ekspandery...
Niedawno Ryan Willams udowodnił, że konstruktywność w naturalnym dowodzie jest nieunikniona, aby uzyskać separację klas złożoności: i . T C 0NEXPNEXP\mathsf{NEXP}TC0TC0\mathsf{TC}^{0} Konstruktywność w naturalnym dowodzie jest warunkiem, że wszystkie dowody kombinatoryczne w złożoności obwodu są...
Co wiadomo na temat złożoności obliczeniowej liczb całkowitych faktoringu w ogólnych polach liczbowych? Dokładniej: Nad liczbami całkowitymi reprezentujemy liczby całkowite poprzez ich binarne rozszerzenia. Jakie są analogiczne reprezentacje liczb całkowitych w ogólnych polach liczbowych? Czy...
Mam nadzieję, że nie jest to pytanie niepoprawne politycznie, ale dla doktoranta, który zwykle publikuje w CCC / ITCS / ICALP (a czasami w FOCS / STOC), może być szkodliwe (pod względem kariery zawodowej) publikowanie mniej znaczących prac w mniej prestiżowe konferencje (np. MFCS, FCT, STACS, IPL)?...