Pisząc mały post na temat złożoności gier wideo Nibbler i Snake ; Odkryłem, że oba mogą być modelowane jako problemy z rekonfiguracją na grafach płaskich; i wydaje się mało prawdopodobne, aby takie problemy nie zostały dobrze zbadane w obszarze planowania ruchu (wyobraź sobie na przykład łańcuch...
Łatwo zauważyć, że jeśli to istnieją całkowite N P problemy wyszukiwania, których nie można rozwiązać w czasie wielomianowym (stwórz całkowity problem wyszukiwania, mając zarówno świadków członkostwa, jak i świadków braku członkostwa).N P ∩ c o N P ≠ PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq...
Czy wiemy, że hierarchia się nie zwija ( dla wszystkich d )?TC0TC0\mathsf{TC^0}TC0d⊊TC0d+1TCd0⊊TCd+10\mathsf{TC^0_d} \subsetneq \mathsf{TC^0_{d+1}}ddd Wpis do zoo dla TC0TC0\mathsf{TC^0} wspomina tylko o separacji między głębokością 2 i 3. Czy istnieje również standardowe odniesienie do faktu, że...
Obecnie prowadzę badania nad językiem formalnym, które obejmują klasy języków powyżej zwykłego, ale poniżej kontekstowego. Patrzę na takie rzeczy, jak maszyny zliczające z odwróceniem, maszyny liczące na jednym stosie, deterministyczne CFL itp. Zastanawiam się, czy ktokolwiek wie o dobrej książce...
Próbuję zrozumieć, do której klasy złożoności należy następujący problem: Wykładniczy wielomianowy problem z korzeniem (EPRP) Niech będzie wielomianem o deg ( p ) ≥ 0 ze współczynnikami wyciągniętymi z pola skończonego G F ( q ) z q liczbą pierwszą, a r pierwotnym pierwiastkiem dla tego pola....
Programowanie liniowe jest oczywiście obecnie bardzo dobrze rozumiane. Mamy dużo pracy, która charakteryzuje strukturę wykonalnych rozwiązań i strukturę rozwiązań optymalnych. Mamy silną dualność, algorytmy wielogodzinne itp. Ale co wiadomo na temat minimalnych maksymalnych rozwiązań LP? Lub...
Zadałem to pytanie kilka tygodni temu w Mathoverflow , ale nie otrzymałem odpowiedzi. Tutaj przez siatkę 3D długości bocznej rozumiem wykres G = ( V , E ) z V = { 1 , … , k } 3 i E = { ( ( a , b , c ) , ( x , y , z ) ) ∣ | a - x | + | b - y | + | dokkkG=(V,E)G=(V,E)G=(V,E)V={1,…,k}3V={1,…,k}3V=...
CMSOL to zliczanie logiki monadycznej drugiego rzędu, tj. Logiki grafów, w których domeną jest zestaw wierzchołków i krawędzi, istnieją predykaty dla przylegania wierzchołków i wierzchołków oraz występowania krawędzi i wierzchołków, istnieje kwantyfikacja na krawędziach, wierzchołkach, zestawach...
Co wiadomo na temat następującego problemu? Biorąc pod uwagę zbiór funkcji f : { 0 , 1 } n → { 0 , 1 } , znajdź największą podkolekcję S ⊆ C z zastrzeżeniem ograniczenia, że VC-Wymiar ( S ) ≤ k dla jakiejś liczby całkowitej k .CCCf:{0,1}n→{0,1}f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\}S⊆CS⊆CS...
Szukam dobrego odniesienia do najkrótszych ścieżek wąskich gardeł. W szczególności, biorąc pod uwagę wierzchołki si na grafie bezkierunkowym z wagami krawędzi, potrzebujesz najkrótszej ścieżki od s do t, gdzie długość ścieżki jest maksymalną krawędzią na tej ścieżce. Można to rozwiązać w czasie O...
Czy istnieje ankieta (z artykułu, rozdziału książki, samouczka, linków, ...) semantyki różnych funkcji języka programowania? Początkowo byłem przytłoczony funkcjami D tutaj http://www.digitalmars.com/d/2.0/comparison.html Chciałbym zobaczyć, co mógłbym stąd uzyskać, chociaż zadałem podobne pytanie...
Szukam odniesień bibliograficznych dla następującego algorytmu / problemu: nazwałem go „BiSelect” lub „t-ary Select” lub „Select in Union of Sorted Arrays”, ale myślę, że został wprowadzony wcześniej pod inną nazwą? Problem Rozważ następujący problem: Biorąc pod uwagę kkk rozłożonych tablic...
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...
Unikalny SAT jest dobrze znanym problemem: biorąc pod uwagę wzór CNF , czy to prawda, że F ma dokładnie jeden model?FFFFFF Interesuje mnie problem «Dokładnie SAT»: biorąc pod uwagę wzór F CNF i liczbę całkowitą m > 1 , czy to prawda, że F ma dokładnie m modeli?mmmFFFm>1m>1m>1FFFmmm Oba...
Przeczytałem artykuł Freyda „Algebraicznie kompletne kategorie” w słynnym Como90 i mam dwa pytania dotyczące pojęcia zwartości algebraicznej zdefiniowanej w tym artykule. (Jeśli nie znasz tej definicji, oto ona: Kategoria nazywa się zwartą algebraicznie, jeśli każdy endofunkor ma początkową algebrę...
Języki Dyck definiuje następująca gramatyka S → S S.Dyck(k)Dyck(k)\mathsf{Dyck}(k) nad zbiorem symboli { ( 1 , … , ( k , ) 1 , … , ) k } . Języki intuicyjnie Dyck są językami zbilansowanych nawiasów k innego rodzaju. Na przykład (S→SS|(1S)1|…|(kS)k|ϵS→SS|(1S)1|…|(kS)k|ϵ S \rightarrow SS \,|\, (_1...
Szybkie wyszukiwanie w Internecie doprowadziło mnie do przekonania, że „APXHardness implikuje, że nie ma QPTAS dla problemu, chyba że [jakaś klasa złożoności] jest zawarta w [innej klasie złożoności]” i jest również dobrze znana! Wygląda na to, że wszyscy o tym wiedzą oprócz mnie. Niestety nie...
Biorąc kompozytu Pole numeru sita ogólnie najlepiej znane algorytm faktoryzacji całkowitymi faktoryzacji N . Jest to algorytm randomizowany i otrzymujemy oczekiwaną złożoność O ( e √N∈NN∈NN\in\Bbb NNNNdo
Mam nadzieję, że ktoś wie o tym, więc nie muszę czytać literatury ... Rozważ ciąg liczb . Pomyśl o sekwencji jako interwałach . Oczywiście, oryginalna sekwencja jest bitoniczna, jeśli jakikolwiek punkt na prawdziwej linii dźgnie co najwyżej 2 interwały. Będziemy odnosić się do sekwencji, w której...
MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy...