To pytanie dotyczy logiki zdań i wszystkie wystąpienia „rozstrzygania” należy interpretować jako „rozstrzyganie zdań”. To pytanie jest bardzo proste, ale od dłuższego czasu mnie niepokoi. Widzę, że ludzie twierdzą, że rozwiązanie zdań jest kompletne, ale widzę też, że ludzie twierdzą, że...
Wiadomo, że minimalizowanie rozmiaru wyrażenia regularnego jest pełne dla PSPACE, nawet jeśli mamy specyfikację języka jako DFA . Jakie są wyniki, jeśli język jest skończony? Problem ten można rozważyć w dwóch modelach: Dane wejściowe to wszystkie ciągi w języku, a rozmiar wejściowy mierzymy...
Miałem nadzieję, że ktoś może mi wyjaśnić, dlaczego dokładnie problem produktu z podzbiorem jest silnie trudny do NP, podczas gdy problem sumy z podzbiorem jest trudny do NP. Podzbiór Suma: Biorąc pod uwagę, i T , czy istnieje podzbiór X ' , tak że Σ i ∈ X ' x I = T .X={x1,...,xn}X={x1,...,xn}X =...
Od dwóch dekad trwają fantastyczne prace nad Permanentnym. Przez pewien czas zastanawiałem się nad możliwością zastosowania algorytmu Smooth P dla Permanent of Nonnegative Matrices. Istnieje oczywiście słynny algorytm JSV, ale jest to fpras. Myśląc o innych pracach w ramach wygładzonej złożoności,...
Ja jako dane wyjściowe DAG z n wierzchołków gdzie każdy wierzchołek x dodatkowo znakowane pewnym S ( x ) ⊆ { 1 , ... , N } .GGGnnnxxxS(x)⊆{1,…,n}S(x)⊆{1,…,n}S(x) \subseteq \{1, \ldots, n\} Topologicznym rodzajem jest bijection f z wierzchołków G do { 1 , … , n } taki, że dla wszystkich x , y ,...
Czy istnieje jakiś naturalny sposób na zrozumienie istoty semantyki relacyjnej polimorfizmu parametrycznego? Właśnie zacząłem czytać o pojęciu parametryczności relacyjnej, a la John Reynolds „Typy, abstrakcja i polimorfizm parametryczny” i mam problem ze zrozumieniem, w jaki sposób motywowana...
Istnieją badania dotyczące algorytmów aproksymacyjnych dla całkowitych problemów NP w czasie wielomianowym i dokładnych algorytmów w czasie wykładniczym. Czy istnieją badania na temat algorytmów aproksymacyjnych dla kompletnych problemów NP w podwykładniczym czasie formy gdzie δ 2 ∈ ( 0 , 1 )...
Jest to zapisane we wpisie wiki dotyczącym Symbolic Execution , ale nie mogę znaleźć żadnego odniesienia do niego. Czy ktoś może mi pokazać wskaźnik? Dziękuję
Wysiłki związane z weryfikacją kompilatora często sprowadzają się do udowodnienia, że kompilator jest w pełni abstrakcyjny: zachowuje i odzwierciedla (kontekstowe) równoważności. Zamiast dostarczania pełnych dowodów abstrakcji, niektóre ostatnie (oparte na kategoriach) prace weryfikacyjne...
Wykres Izomorfizm ( ) jest dobrym kandydatem dla N P problemu -intermediate. N P istnieje -intermediate problemy chyba P = N P . Szukam naturalnego problemu, który jest trudny dla G I przy redukcji Karp (Problem graficzny X taki, że G I < m p X
Jednym ze sposobów wykazania, że sprawdzenie wykonalności liniowego układu nierówności jest tak trudne, jak programowanie liniowe, jest zmniejszenie za pomocą metody elipsoidalnej. Jeszcze łatwiejszym sposobem jest odgadnięcie optymalnego rozwiązania i wprowadzenie go jako ograniczenia poprzez...
Kiedy otrzymujemy rozkład drzewa wykresu o szerokości , istnieje kilka sposobów, dzięki którym możemy go uczynić „ładnym”. W szczególności wiadomo, że można go przekształcić w rozkład drzewa, w którym drzewo jest binarne, a jego wysokość wynosi . Można to osiągnąć przy zachowaniu szerokości...
Mówimy, że maszyna Turinga jest śmiertelna, jeśli M zatrzymuje się przy każdej początkowej konfiguracji (w szczególności zawartość taśmy i stan początkowy mogą być dowolne). Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną Maszynę Turinga? (tzn. jeśli istnieje baza TM, która...
Istnieje wiele sytuacji, w których zrandomizowany „dowód” jest znacznie łatwiejszy niż dowód deterministyczny, którego kanonicznym przykładem jest testowanie tożsamości wielomianowej. Pytanie : Czy istnieją jakieś naturalne „twierdzenia” matematyczne, w których znany jest dowód losowy, ale dowód...
Krótkie pytanie Jaka jest moc obliczeniowa obwodów „kwantowych”, jeśli pozwolimy na niejednorodne (ale wciąż odwracalne) bramki i wymagamy, aby dane wyjściowe dawały prawidłową odpowiedź z pewnością? To pytanie w pewnym sensie dotyczy tego, co dzieje się z klasą kiedy pozwalasz obwodom na...
Chciałbym zapytać o dobre teksty wprowadzające złożoność obwodu. Pomocne będą również wszelkie wskazówki dotyczące ostatnich postępów i otwartych problemów w tej
Jeden z interesujących otwartych problemów dotyczących DFA wymienionych w Czy są jakieś otwarte problemy dotyczące DFA? jest wielkością DFA wymaganą do oddzielenia dwóch łańcuchów długości nnn . Jestem ciekawy, czy są jakieś wyniki dotyczące zdolności losowego DFA do oddzielania dwóch podanych...
Zamiast dowodów empirycznych, jakie formalne zasady udowodniliśmy, że obliczenia kwantowe będą szybsze niż obliczenia tradycyjne /
Co się stanie, jeśli zdefiniujemy P P A D wPPAD{\bf PPAD} taki sposób, że zamiast polytime-maszyny Turinga / obwodu polisize, maszyny logistycznej Turinga lub obwodu A C 0AC0{\bf AC^0} koduje problem? Ostatnio dając szybsze algorytmy Okręgowego spełnialności dla małych obwodów okazało się być...
Każdy monotoniczny obwód arytmetyczny , tj. Obwód , oblicza pewną wielomianową wielomian z nieujemnymi współczynnikami całkowitymi. Biorąc pod uwagę wielomian , obwódF ( x 1 , … , x n ) f ( x 1 , … , x n