Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

1
Złożoność wersji wyszukiwania 2-SAT przy założeniu
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 = NL} Jeśli nie, to co z algorytmami wykorzystującymi przestrzeń sublinearną (w liczbie klauzul)?
3
Zastosowania teorii mnogości, teorii porządkowej, nieskończonej kombinatoryki i ogólnej topologii w informatyce?
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, topologii niskowymiarowej, topologii geometrycznej itp. Szukam jednak zastosowań nieskończonych obiektów tych podmiotów, tj. Drzew nieskończonych ( …
2
Które algorytmy randomizowane mają wykładniczo małe prawdopodobieństwo błędu?
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 kilka przykładów, które przychodzą na myśl: Algorytmy próbkowania, np. Gdzie chcemy oszacować …
4
Programowanie wnioskowania o własnym kodzie źródłowym
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 pytania. Interesują mnie dwie rzeczy: (A) Język programowania P, który …
1
Złożoność informacji algorytmów zapytań?
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 złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w …
1
Czy ta gęsta wersja algorytmu Kruskala jest dobrze znana?
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(mlog⁡m)O(m \log m) (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy Θ ( n2))Θ(n2))\Theta(n^2) we wszystkich przypadkach, podobnie jak Prim, gdy implementujemy je za pomocą macierzy …
1
pełny problem z quasi-wielomianem związanym z liczbą rozwiązań
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ą górną granicą liczby rozwiązań (świadków)? Czy istnieje powszechnie przyjęte przypuszczenie, …
1
Dlaczego praca Schönfinkela nad wyeliminowaniem „zmiennych powiązanych” w logice była tak istotna?
AFAIK, Pierwsze dowody używania funkcji wyższego rzędu sięgają artykułu Schönfinkela z 1924 r .: „O elementach logiki matematycznej” - gdzie pozwalał przekazywać funkcje jako argumenty innym funkcjom. To wydaje się interesujące. Jednak wszystko, co czytałem o jego pracy (i Curry'ego z rozszerzenia) zdaje się nawiązywać do jednej rzeczy w takiej …
1
Jakiś wielomian, który trudno policzyć, ale łatwo go wybrać?
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 ){+,×}{+,×}\{+,\times\}F(x1,…,xn)F(x1,…,xn)F(x_1,\ldots,x_n)f(x1,…,xn)f(x1,…,xn)f(x_1,\ldots,x_n) oblicza fff jeśli F(a)=f(a)F(a)=f(a)F(a)=f(a) dla wszystkich a∈Nna∈Nna\in \mathbb{N}^n ; …
1
Czy
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ć ważne, więc zastanawiam się, co się dzieje …
1
Rozdzielanie słów losowymi DFA
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 (nielosowych) ciągów. Wyraźnie losowy DFA o wystarczająco wielu stanach …
2
Naprawiono punkty w obliczalności i logice
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 twierdzeniami o stałym punkcie w logice a -calculus.λλ\lambda tło 1) Rola …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.