Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: DSPACE(f(n))DSPACE(f(n))\textbf{DSPACE}(f(n)) lub NSPACE(f(n))NSPACE(f(n))\textbf{NSPACE}(f(n)) . Wydaje się, że we wczesnej teorii złożoności odniesiono...
Niedawno odkryłem kwadratową dolną granicę złożoności problemu w modelu drzewa decyzyjnego i zastanawiam się, czy ten wynik można częściowo uogólnić na model maszyny o swobodnym dostępie. Przez częściowo , to znaczy uogólnienie do ubijania programów o określonym czasie / przestrzeni kompromis. Na...
Czytając artykuł „ Teoria aplikacyjna dla FPH ”, można natknąć się na następujący fragment: Biorąc pod uwagę teorie charakteryzujące klasy złożoności obliczeniowej, istnieją trzy różne podejścia: w jednym funkcje, które można zdefiniować w teorii, są „automatycznie” w ramach pewnej klasy...
Załóżmy, że mamy do czynienia z językiem programowania obsługującym typy liniowe (terminy typu liniowego mogą być użyte najwyżej raz, że tak powiem). Pozwala to na traktowanie niektórych efektów obliczeniowych (takich jak mutacja, a nawet zmiana rodzaju operandu) w sposób problematyczny dla...
Jak wszyscy wiedzą, słynna książka Garey i Johnsona (i wiele innych) stanowi doskonałe odniesienie do techniki redukcji w scenerii klasycznej. Czy są jakieś ankiety lub książki na temat techniki redukcji w sparametryzowanym algorytmie, powiedzmy redukcja
Jakiś czas temu zadałem to pytanie na temat Przepełnienia stosu: Problem: sprzedaż Boba . Ktoś zasugerował także opublikowanie pytania tutaj. Ktoś już zadał tutaj pytanie związane z tym problemem - minimalna waga lasów danej liczności - ale o ile rozumiem, nie pomaga mi to z moim problemem. Warto...
Biorąc pod uwagę macierz m×nm×nm \times n (przy założeniu, że m≥nm≥nm \ge n ), jaki jest najszybszy algorytm obliczający swoją pozycję i podstawę kolumn? Wiem, że można to rozwiązać za pomocą liniowego przecięcia macierzy, co implikuje algorytm deterministyczny czasowy i algorytm randomizowany...
Szukam artykułów i artykułów na temat modalnej logiki podstrukturalnej - nie na semantykę modalności logicznej liniowej, ale na logikę podstrukturalną wzbogaconą standardowymi operatorami modalnymi, np. Podstrukturalną K (coś w rodzaju MALL z operatorem skrzynki, koniecznością i regułami...
Twierdzenie Banacha o punkcie stałym mówi, że jeśli mamy niepustą pełną przestrzeń metryczną AZAA , wówczas każda jednorodnie kurcząca się funkcja ma unikalny punkt stały . Jednak dowód tego twierdzenia wymaga aksjomatu wyboru - musimy wybrać dowolny element aby rozpocząć iterację , aby uzyskać...
Jakie są dobre artykuły / książki, aby lepiej zrozumieć moc rozkładu modułowego i jego właściwości? Szczególnie interesują mnie algorytmiczne aspekty dekompozycji modułowej. Słyszałem, że można znaleźć rozkład modułowy wykresu w czasie liniowym. Czy istnieje do tego stosunkowo prosty algorytm? Co...
Zestaw uderzenia z rodziny S.= { S1, … , Sn}S.={S.1,…,S.n}\mathcal{S} = \{S_1, \dots, S_n\} jest podzbiorem z taki sposób, do . Problem znalezienia minimalnego zestawu uderzeń z danej rodziny jest ogólnie trudny do przeprowadzenia, ponieważ uogólnia problem pokrycia wierzchołków. Teraz moje pytanie...
(Uogólniona) wysokość gwiazdy w języku jest minimalnym zagnieżdżeniem gwiazd Kleene wymaganym do przedstawienia języka za pomocą rozszerzonego wyrażenia regularnego. Przypomnijmy, że rozszerzonym wyrażeniem regularnym ponad skończonych alfabet spełnia następujące:ZAAA (1) i są rozszerzone...
Próbuję zrozumieć niektóre pojęcia dotyczące rozkładu modułowego i wykresów szerokości kliki . W tym artykule („Na wykresach uporządkowanych za pomocą P4”) znajduje się dowód na to, jak rozwiązać problemy z optymalizacją, takie jak liczba kliki lub liczba chromatyczna za pomocą rozkładu...
Defunkcjonalizacja to transformacja programu, która przekształca programy wyższego rzędu w programy pierwszego rzędu. Chodzi o to, że biorąc pod uwagę program, istnieje tylko skończona liczba abstrakcji lambda, więc można zastąpić każdą lambda identyfikatorem, a każdą aplikację funkcji wywołaniem...
tło Funkcje w to PAC poznawalny w quasipolomomialnym czasie z klasycznym algorytmem, który wymaga O ( 2 l o g ( n ) O ( d ) ) losowo wybranych zapytań do poznania obwodu o głębokości d [1]. Jeśli nie ma algorytmu faktoryzacji 2 n o ( 1 ), jest to optymalne [2]. Oczywiście na komputerze kwantowym...
Czy mógłbyś wskazać, jak zbudować funkcję Ackermana (tak naprawdę interesuje mnie wersja zaproponowana przez Rózsa Pétera i Raphaela Robinsona) za pomocą standardowych operatorów rekursywnych? Próbowałem oryginalnych prac Pétera i Robinsona, ale praca Pétera używa języka innego niż angielski, a...
Mam dwa pytania: Kto pierwszy użył relacji logicznych do powiązania semantyki? Prześledziłem je z powrotem do „Reynolds of the Relation Between Direct and Continuation Semantics ” Reynolda , ale nie mogę twierdzić, że przeprowadziłem wyczerpujące poszukiwania. Znalazłem odniesienia do relacji...
Używam tytułowego terminu w bardzo luźnym znaczeniu. Dużo pracy poświęcono ewolucyjnej teorii gier, w tym jej matematycznym fundamentom. Polecono mi „Gry ewolucyjne i dynamika populacji”, ale jeszcze się w to nie zagłębiłem. Istnieje również znaczna ilość pracy nad algorytmiczną teorią gier,...
Dzięki uniwersalnemu twierdzeniu o aproksymacji wiadomo, że sieć neuronowa z nawet jedną ukrytą warstwą i dowolną funkcją aktywacji może aproksymować dowolną funkcję ciągłą. Jakie są inne modele, które są również uniwersalnymi aproksymatorami
Kategoria ma dwuprodukty, gdy te same obiekty są zarówno produktami, jak i koproduktami. Czy ktoś badał teorię kategorii produktów dwubiegunowych? Być może najbardziej znanym przykładem jest kategoria przestrzeni wektorowych, w których bezpośrednia suma i bezpośrednie konstrukcje produktu dają tę...