EDYCJA (v2): Dodano sekcję na końcu tego, co wiem o problemie. EDYCJA (v3): Dodano dyskusję na temat stopnia progowego na końcu. Pytanie To pytanie jest głównie prośbą o referencję. Nie wiem dużo o tym problemie. Chcę wiedzieć, czy wcześniej pracowano nad tym problemem, a jeśli tak, to czy ktoś...
Przypuszczenie o rekonstrukcji mówi, że wykresy (z co najmniej trzema wierzchołkami) są określane jednoznacznie przez ich podgrupy usunięte z wierzchołków. Ta hipoteza ma pięć dekad. Przeszukując odpowiednią literaturę, odkryłem, że następujące klasy grafów są rekonstruowalne: drzewa wykresy...
Biorąc pod uwagę podzbiorów z .nnnS1,…,SnS1,…,SnS_1,\ldots,S_n{1,…,d}{1,…,d}\{1,\ldots,d\} Sprawdź, czy istnieją zestawy z . (Jeśli tak, znajdź przykład, jeśli nie, po prostu powiedz „nie”)Si,SjSi,SjS_i,S_jSi⊊SjSi⊊SjS_i \subsetneq S_j Trywialne rozwiązanie tego problemu polega na przejściu...
Obecnie próbuję znaleźć problemy pełne EXPSPACE (głównie w celu znalezienia inspiracji do redukcji) i jestem zaskoczony małą liczbą nadchodzących wyników. Jak dotąd je znalazłem i mam problem z rozwinięciem listy: uniwersalność (lub inne właściwości) wyrażeń regularnych z potęgowaniem. problemy...
Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do...
Przeczytałem w niezliczonych artykułach, że wyznaczanie stałej Cheegera na wykresie to -hard. To wydaje się być twierdzeniem ludowym, ale nigdy nie znalazłem ani cytatu, ani dowodu na to stwierdzenie. Komu mam to przypisać? W starym artykule (Isoperimetric Numbers of Graphs, J. Comb. Theory B,...
Czy ktoś może zasugerować dobrą i najnowszą ankietę na temat liczenia problemów i / lub problemów, które są #P.
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...
Obecnie bitcoin ma system proof of work (PoW) wykorzystujący SHA256. Inne funkcje skrótu wykorzystują wykresy wykorzystania systemu dowodu pracy, częściowe odwrócenie funkcji skrótu. Czy można zastosować problem decyzyjny w teorii węzłów, taki jak rozpoznawanie węzłów, i uczynić z niego funkcję...
Problem nie wszystkie równe SAT (NAE -SAT), biorąc pod uwagę zbiór klauzul nad zestawem zmiennych boolowskich, tak że każda klauzula zawiera co najwyżej literałów, pyta, czy istnieje przyporządkowanie zmiennych do takich wartości, że każda klauzula zawiera co najmniej jeden prawdziwy i co najmniej...
W przypadku ustalonego skończonego alfabetu język formalny L ponad Σ jest regularny, jeśli istnieje deterministyczny automat skończony (DFA) ponad ΣΣΣ\SigmaLL.LΣΣ\SigmaΣΣ\Sigma który akceptuje dokładnie .LL.L Interesują mnie języki, które są „prawie” regularne w tym sensie, że mogą być...
Dla stałej można określić w czasie liniowym, biorąc pod uwagę wykres wejściowy G , czy jego szerokość wynosi ≤ k . Jednakże, gdy zarówno k jak i G są podane jako dane wejściowe, problem jest trudny NP. ( Źródło ).k∈Nk∈Nk \in \mathbb{N}GGG≤k≤k\leq kkkkGGG Jednak gdy wykres wejściowy jest płaski ,...
Próbuję zrozumieć związek między izomorfizmem grafu a problemem ukrytej podgrupy. Czy jest na to dobre
Niektórzy z was mogli śledzić to pytanie , które zostało zamknięte z powodu braku poziomu badań. Wyciągam więc część pytania, która jest na poziomie badawczym. Oprócz „prostszych” technik, takich jak redukcja do sortowania lub problem z WYŁĄCZENIEM, jakie techniki zostały zastosowane, aby...
Właśnie zdałem sobie sprawę, że zakładam, że odpowiedź na moje pytanie brzmi „tak”, ale nie mam dobrego powodu. Wyobrażam sobie, że może istnieje śmieciarz, który prawdopodobnie wprowadza tylko spowolnienie w najgorszym przypadku. Czy istnieje ostateczne odniesienie, które mogę zacytować? W moim...
Zastanawiałem się, jakie artykuły powinienem przeczytać, aby zrozumieć to pytanie Nieoczekiwane połączenie z innymi dziedzinami matematyki, takimi jak geometria algebraiczna lub wyższa kohomologia. Być może nawet dziedzina matematyki nie została jeszcze rozwinięta. Być może ktoś opracuje...
Czy ktoś zna odniesienia, które precyzyjnie określają związek między algorytmem unifikacji a eliminacją Gaussa? Szczególnie interesuje mnie związek między podstawieniami trójkątnymi a rozkładami LU. Wayne Snyder i Jean Gallier wspominają o tej analogii, przekazując w swojej pracy, Revisited...
To pytanie dotyczy złożoności czasowej algorytmu maksymalnego przepływu Forda-Fulkersona podczas korzystania z DFS w celu znalezienia ścieżek rozszerzających. Istnieje dobrze znany przykład pokazujący, że przy użyciu DFS można potrzebować liniowej liczby iteracji w maksymalnym przepływie, patrz na...
Napinacz jest uogólnieniem wektorów i matryc do większych rozmiarów i stopnia z tensora uogólnia również rzędu macierzy. Mianowicie, ranga tensora jest minimalna liczba rangi jeden tensory tej kwoty . Wektor i macierz są odpowiednio tensorami stopnia 1 i 2.TT.TTT.TT Elementy w pochodzą z pola ....
Podczas majstrowania przy niekanonicznym analizowaniu LR wymyśliłem metodę analizy (z tabelami o nieskończonych rozmiarach, co czyni ją nieco niepraktyczną ), która jest w stanie przeanalizować dokładnie jednoznaczne gramatyki w czasie , i zastanawiałem się, czy można to zrobić lepiej...