Interesuje mnie klasyczny problem REGULARNE WŁĄCZENIE JĘZYKA. Biorąc pod uwagę wyrażenie regularne , oznaczamy przez L ( E ) powiązany z nim język regularny. (Wyrażenia regularne są na stałej alfabetu Ď z unii operacji, Kleene-gwiazdkowe i konkatenacji).miEEL ( E)L(E)L(E)ΣΣ\Sigma Dane wejściowe:...
Czy w literaturze jest coś zbliżonego do następującego problemu: Biorąc pod uwagę dwuczęściowy wykres ze zrównoważonym dwuczęściowym , czy istnieje idealne dopasowanie w tak że dla każdej 2 krawędzi występuje krawędź lub krawędź (lub oba) w ?G ( V, E)G(V,E)G(V,E){ U, W}{U,W} \{U,W\}M.M M solG G...
„Nazwa największej gry liczbowej” wymaga od dwóch graczy potajemnego zapisania numeru, a zwycięzcą jest osoba, która zapisała większą liczbę. Gra zazwyczaj pozwala graczom zapisywać funkcje ocenione w danym momencie, więc byłoby również do przyjęcia.2)2)2)2)2)2)2)2)2^{2^{2^{2}}} Wartości funkcji...
Problem reprezentowania zmiennych powiązanych w składni, a zwłaszcza podstawiania unikania przechwytywania, jest dobrze znany i ma wiele rozwiązań: zmienne nazwane z równoważnością alfa, wskaźniki de Bruijna, lokalna bezimienność, zbiory nominalne itp. Ale wydaje się, że istnieje inne dość...
W teorii złożoności definicja złożoności czasu i przestrzeni odnosi się do uniwersalnej maszyny Turinga: odpowiednio. liczba kroków przed zatrzymaniem i liczba dotkniętych komórek na taśmie. Biorąc pod uwagę tezę Kościoła-Turinga, powinno być możliwe zdefiniowanie złożoności również pod względem...
Z twierdzenia o hierarchii przestrzeni wiadomo, że jeśli faff można konstruować w przestrzeni, to DSPACE ( 2 f( n )2f(n)2f(n) ) nie jest równe DSPACE ( fa( n ) )f(n))f(n)) . Tutaj przez DSPACE ( fa( n ) )f(n))f(n)) mam na myśli klasę wszystkich problemów, które można rozwiązać w przestrzeni fa( n...
Czytałem o dziedzicznej zamianie na prosty rachunek Lambda i na logiczną strukturę z odrębnymi terminami i typami. Zastanawiam się, czy są jakieś przykłady dziedzicznej substytucji w systemie o typie zależnym i hierarchii wszechświata? tzn. gdzie True:Set0:Set1:Set2True:Set0:Set1:Set2 True : Set_0...
Zestaw słów nad skończonym alfabetem nie zawiera prefiksu, jeśli nie ma dwóch odrębnych słów, w których jedno jest prefiksem drugiego. Pytanie brzmi: Jaka jest złożoność sprawdzania, czy zwykły język podany jako NFA zawiera nieskończony podzbiór bez prefiksów? Odpowiedź (z powodu Michaiła...
Postępy w dziedzinie obliczeń kwantowych doprowadziły do opracowania nowych klasycznych algorytmów. Godne uwagi ostatnie przykłady to inspirowane kwantem algorytmy algebry liniowej: Klasyczny algorytm inspirowany kwantem dla systemów rekomendacji Klasyczne algorytmy inspirowane kwantem do...
Mówi się, że dwie grupy (G,⋅)(G,⋅)(G,\cdot) i (H,×)(H,×)(H, \times) są izomorficzne, jeśli istnieje homomorfizm od GGG do HHH który jest bijectywny. Problem z izomorfizmem grupowym jest następujący: biorąc pod uwagę dwie grupy, sprawdź, czy są izomorficzne, czy nie. Istnieją różne sposoby...
W pracy Stephena Cooka na temat problemu P vs NP [1] stwierdza, że [2]: Teza wykonalności: Naturalny problem ma wykonalny algorytm, jeśli ma algorytm czasu wielomianowego. Moje pytanie brzmi: co dokładnie on (lub ogólnie tak naprawdę, co to znaczy) przez „ naturalny problem”? Mówienie o...
Czy dzielenie i podbijanie FFT może być automatycznie uogólnione na inne transformacje (z Transform, ćwierkanie itp.) Automatycznie? Czy istnieje algorytm, który przyjmuje opis transformacji (nie wiem, jakie informacje byłyby potrzebne) i może wygenerować szybką funkcję podobną do...
W szczególności proszę o zasoby, aby dowiedzieć się o systemach uczenia maszynowego, które mogą aktualizować ich odpowiednie sieci przekonań (lub ich odpowiedniki) podczas pracy. Natknąłem się nawet na kilka, ale nie udało mi się ich dodać do zakładek. Jak można sobie wyobrazić, wyszukiwanie w...
Twierdzenie o strefie mówi, że jeśli dźgniemy układ n linii inną linią, całkowita złożoność jego strefy , zbiór wszystkich ścian 0, 1 i 2 sąsiadujących z nią, wynosi O (n). Rzeczywista stała to mniej więcej 6n, jak podano w różnych podręcznikach, a dowodem jest indukcja z rozsądnie ostrożnym...
Istnieje kilka różnych (prawdopodobnie nierównych) pojęć uniwersalności obliczeniowej (patrz na przykład kilka ostatnich stron http://www.dna.caltech.edu/~woods/download/WoodsNearyTCS07-DRAFT.pdf ) i nie ma zgody między eksperci o tym, które pojęcia są najbardziej poprawne (patrz na przykład...
Niech będzie nieregularnym połączonym wykresem, którego stopień jest ograniczony. Załóżmy, że każdy węzeł zawiera unikalny token.G = ( V, E)G=(V,E)G= (V, E) Chcę równomiernie tasować tokeny między wykresami, używając tylko lokalnych zamian (tj. Wymiany tokenów między dwoma sąsiadującymi węzłami)?...
Wydaje się, że większość literatury dotyczy maszyn z pojedynczymi wyroczniami dla określonych problemów, jednak wydaje się, że istnieje kilka artykułów, które rozważają maszyny z wieloma wyroczniami. Czy istnieje dobra praca lub praca, która zawiera przegląd tego, co wiadomo o takich maszynach? W...
Co dowody na to, że ?c o R P≠ N.P.coRP≠NPcoRP \neq NP jest klasą języków, dla których istnieje probabilistyczna maszyna Turinga, która działa w czasie wielomianowym i zawsze odpowiada Tak na dane wejściowe należące do języka i odpowiada Nie z prawdopodobieństwem co najmniej połowy na dane...
Czy jest możliwe (ukośnik, czy możesz podać przykład) zmniejszenie złożoności obliczeniowej problemu za pomocą algorytmu równoległego, który nie wymaga wielu procesorów w stosunku do wielkości
Przez BPP / linear mam na myśli maszyny BPP z liniową radą, która spełnia obietnicę, gdy otrzyma „prawidłową” radę, a derandomizacja powinna dać nam, powiedzmy, algorytm P / liniowy lub (SUBEXP / liniowy). Jeśli zastosujemy niejednolite założenia, uważam, że klasyczne wyniki powinny zadziałać,...