FewP to klasa z wielomianem ograniczonym liczbą rozwiązań (w wielkości wejściowej). Tam nie jest znana -Complete problem . Interesuje mnie, jak daleko możemy rozciągnąć tę obserwację.N P f e w PNPNPNPNPNPNPfewPfewPfewP Czy istnieje jakiś naturalny problem z uzupełnieniem z quasi-wielomianową...
To pytanie zostało również opublikowane na Math.SE, /math/1002540/fixed-points-in-computability-nd-logic Mam nadzieję, że opublikowanie go tutaj jest również w porządku. Jeśli nie, lub jeśli jest to zbyt podstawowe dla CS.SE, powiedz mi, a ja go usunę. Chciałbym lepiej zrozumieć związek między...
Mniej więcej rok temu razem z przyjacielem zastanawialiśmy się, jak zaimplementować algorytm Kruskala dla gęstych wykresów w lepszej niż zwykle granicy O ( m logm )O(mlogm)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich...
Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów. Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a...
Jeśli , a następnie jest algorytm logspace który rozwiązuje wersja decyzja 2-SAT.L=NLL=NL\mathsf{L = NL} Czy wiadomo, że sugeruje, że istnieje algorytm przestrzeni logicznej, który pozwala uzyskać zadowalające przypisanie , jeśli dane wejściowe są zadowalające dla 2-SAT?L=NLL=NL\mathsf{L =...
Jakiś czas temu po raz pierwszy ktoś mi powiedział, że call / cc może zezwalać na obiekty proof dla klasycznych proofów poprzez wdrożenie prawa Peirce'a. Ostatnio zastanawiałem się nad tym tematem i wydaje mi się, że nie mogę go znaleźć. Jednak naprawdę nie widzę, żeby ktokolwiek mówił o tym....
Jestem matematykiem zainteresowanym teorią zbiorów, teorią porządkową, nieskończoną kombinatoryką i topologią ogólną. Czy są jakieś zastosowania dla tych przedmiotów w informatyce? Szukałem trochę i znalazłem wiele zastosowań (oczywiście) do teorii grafów skończonych, topologii skończonej,...
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje...
To pytanie zostało wcześniej opublikowane w Computer Science Stack Exchange tutaj . Wyobraź sobie, że jesteś odnoszącym sukcesy podróżnym sprzedawcą z klientami w całym kraju. Aby przyspieszyć wysyłkę, opracowałeś flotę dronów jednorazowego użytku o efektywnym zasięgu 50 kilometrów. Dzięki tej...
Załóżmy, że algorytm losowy używa rrr losowych bitów. Najniższe prawdopodobieństwo błędu, jakiego można się spodziewać (nie spełniając deterministycznego algorytmu z błędem 0), wynosi 2)- Ω ( r )2)-Ω(r)2^{-\Omega(r)} . Które algorytmy losowe osiągają tak minimalne prawdopodobieństwo błędu? Oto...
Załóżmy, że otrzymujemy zestaw n zmiennych logicznych x_1, ..., x_n oraz zestaw funkcji m y_1 ... y_m, gdzie każdy y_i jest XOR (danego) podzbioru tych zmiennych. Celem jest obliczenie minimalnej liczby operacji XOR, które należy wykonać, aby obliczyć wszystkie te funkcje y_1 ... y_m. Zauważ, że...
Niech oznacza zbiór a C (n, k) oznacza zbiór wszystkich kombinacji elementów z bez powtórzeń. Niech będzie liczbą w . Mówimy, że permutacja zestawu pozwala uniknąć jeśli nie ma k-krotki liczb całkowitych taki, że { 1 , . . . , n } k [ n ] p = p 1 p 2 . . . p k k C ( n , k ) π : [ n ] → [ n ] [ n...
Inspiracją dla tego pytania jest następujące (niejasne) pytanie: Jakie są podstawy programowania / logiczne podstawy posiadania sztucznej inteligencji, która mogłaby rozumować własny kod źródłowy i go modyfikować? To wcale nie jest rygorystyczne, więc oto moja próba wyciągnięcia z tego konkretnego...
Problem z rowem jest następujący:kkk Instancja: Niekierowany wykres z wierzchołkami i do n \ wybierz 2 krawędzie.nsolsolGnnn( n2))(n2))n \choose 2 Pytanie: Czy w G istnieje (właściwy) cykl K ?kkksolsolG Tło: Dla każdego ustalonego kkk możemy rozwiązać cykl 2 tys2)k2k w czasie O (...
W prostej formie: Można dwukierunkowa skończony automat rozpoznaje vvv wykresy -Vertex które zawierają trójkąt z o(v3)o(v3)o(v^3) stany? Detale Zainteresowania są tu vvv wykresy -Vertex kodowane przy użyciu sekwencji krawędzi, każda krawędź jest para różnych wierzchołki...
W złożoności obwodu mamy rozdzielenia mocy różnych modeli obwodów. W złożoności dowodu mamy rozróżnienia między mocami różnych systemów dowodu. Ale w algorytmie wciąż mamy tylko kilka różnic między potęgami paradygmatów algorytmicznych . Moje pytania poniżej mają na celu dotknięcie tego...
Jakie są główne przykłady udanej derandomizacji lub przynajmniej postępów w wykazywaniu konkretnych dowodów w kierunku celu (a nie związku losowości z twardością)?P=BPPP=BPPP=BPP Jedyny przykład, jaki przychodzi mi na myśl, to deterministyczne badanie pierwotności wielomianów czasowych AKS (nawet...
Pytanie: Załóżmy, że mam specyfikację problemu składającego się z aksjomatów i celu (tj. Powiązanym problemem dowodowym jest to, czy cel jest zadowalający, biorąc pod uwagę wszystkie aksjomaty). Załóżmy również, że problem nie zawiera żadnych niespójności / sprzeczności między aksjomatami. Czy...
Tło: Biorąc pod uwagę dwa deterministyczne automaty skończone A i B, tworzymy iloczyn C, pozwalając, by stany w C były iloczynem kartezjańskim stanów w A i stanów w B. Następnie wybieramy stany przejściowe, początkowe i końcowe, aby język został zaakceptowany przez C to przecięcie języków dla A i...
To niekoniecznie jest pytanie badawcze. Tylko pytanie z ciekawości: Próbuję zrozumieć, czy można zdefiniować języki „nieredukowalne”. Na pierwszy rzut oka nazywam język L „redukowalny”, jeśli można go zapisać jako z i , w przeciwnym razie nazywam język „nieredukowalny” . Czy to prawda:L=A⋅BL=A⋅BL...