Teoretyczne informatyka

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

2
Maszyny Turinga, których zakończenie jest niemożliwe do udowodnienia?
Mam naiwne pytanie: czy istnieje maszyna Turinga, której zakończenie jest prawdziwe, ale której nie da się udowodnić żadną naturalną, spójną i skończoną aksjomatyczną teorią? Proszę o zwykły dowód istnienia, a nie o konkretny przykład. Może to mieć związek z analizą porządkową . Rzeczywiście, dla maszyny Turinga możemy zdefiniować jako najmniejszy …
3
Czy klasa prymitywnych funkcjonałów rekurencyjnych jest równoważna z klasą funkcji, które płód kończy?
Płód, jeśli o nim nie słyszałeś, możesz przeczytać tutaj . Wykorzystuje system „macierzy wywołań” i „grafów wywołań”, aby znaleźć wszystkie „zachowania rekurencyjne” wywołań rekurencyjnych w funkcji. Pokazanie, że funkcja się kończy, pokazuje, że wszystkie zachowania rekurencyjne wywołań rekurencyjnych wykonanych do funkcji są zgodne z pewnym „porządkiem leksykograficznym”. Jego sprawdzanie zakończenia …
2
Co można rozwiązać za pomocą programowania półfinałowego, czego nie można rozwiązać za pomocą programowania liniowego?
Znam programy liniowe, ponieważ mogą one rozwiązywać problemy z liniowymi funkcjami celu i ograniczeniami liniowymi. Ale co programowanie półfinalne może rozwiązać, czego programowanie liniowe nie jest w stanie? Wiem już, że programy półfinałowe są uogólnieniem programów liniowych. Jak rozpoznać problem, który można rozwiązać za pomocą programowania półfinałowego? Jakiego typowego problemu …
2
Dokładna złożoność problemu w
Pozwolić xi∈{−1,0,+1}xi∈{−1,0,+1}x_i \in \{-1,0,+1\} dla i∈{1,…,n}i∈{1,…,n}i \in \{1,\ldots,n\}, z obietnicą, że x=∑ni=1xi∈{0,1}x=∑i=1nxi∈{0,1}x = \sum_{i=1}^n{x_i} \in \{0,1\} (gdzie suma się skończyła ZZ\mathbb{Z}). Jaka jest złożoność ustalenia, czyx=1x=1x = 1? Zauważ, że w trywialny sposób leży problem ∩m≥2AC0[m]∩m≥2AC0[m]\cap_{m \geq 2}{\mathsf{AC}^0[m]} ponieważ x≡1modmx≡1modmx \equiv 1\bmod{m}iff . Pytanie brzmi: czy problem leży w ? …
1
Hyperdoktryny i monadyczna logika drugiego rzędu
To pytanie jest zasadniczo pytaniem, które zadałem na Mathoverflow. Monadyczna logika drugiego rzędu (MSO) to logika drugiego rzędu z kwantyfikacją w stosunku do pojedynczych predykatów. Oznacza to kwantyfikację zbiorów. Istnieje kilka logiki MSO, które są fundamentalne dla struktur badanych w informatyce. Pytanie 1. Czy istnieje kategoryczna semantyka dla logiki Monadic …
1
Złożoność rodzaju ślepego?
Wszyscy wiemy, że minimalną złożonością algorytmu sortowania opartego na porównaniu są porównania . Próbuję wykonać sortowanie w ciemno , tzn. Biorąc pod uwagę liczbę wyjdź z obwodu (z bramkami logicznymi, arytmetycznymi i „porównawczymi”), który sortuje listę elementów.Ω ( n logn )Ω(nlog⁡n)\Omega(n \log n)nnnnnn Wstępne obliczanie wszystkich porównań select 2},(n2))(n2)){n \choose …
2
Dokładne algorytmy czasu wykładniczego dla programów 0-1 z danymi nieujemnymi
Czy są znane algorytmy dla następującego problemu, które pokonały naiwny algorytm? Dane wejściowe: matryca AAA i wektory b,cb,cb,c, gdzie wszystkie wpisy z pozycji A,b,cA,b,cA,b,c są liczbami całkowitymi nieujemnymi. Wyjście: optymalne rozwiązanie x∗x∗x^* do max{cTx:Ax≤b,x∈{0,1}n}max{cTx:Ax≤b,x∈{0,1}n}\max \{ c^T x : Ax \le b, x \in \{ 0,1\}^n \}. To pytanie jest udoskonaloną …
2
Liczba cykli na wykresie
Ile cykli CkCkC_k (k≥3)(k≥3)(k \geq 3) znajdują się na wykresie wierzchołków, tak że wykres nie ma żadnego cyklu .nnn CmCmC_m (m>k)(m>k)(m>k) Na przykład , , wówczas wykres będzie miał najwyżej dwa , tak że nie będzie miał żadnegon=5n=5n=5k=3k=3k=3C3C3C_3GGGCk(k>3).Ck(k>3).C_k (k > 3). Myślę, że są O(n)O(n)O(n) cykle będą tam spełniające powyższe …
2
Bariery w oddzielaniu innych klas złożoności
Czy naturalne dowody , relatywizacja i algebriacja wpływają również na separację innych klas złożoności, takich jakL≠NL≠NP≠coNP≠PH≠PSPACEL≠NL≠NP≠coNP≠PH≠PSPACEL\neq NL\neq NP\neq coNP \neq PH\neq PSPACE itp? Na przykład bariera naturalnego dowodu powinna wpływać na każdy dowód NP≠CoNPNP≠CoNPNP\neq CoNP ponieważ się rozdzieli P≠NPP≠NPP\neq NP. Jednak związek międzyNPNPNP i CoNPCoNPCoNP wydaje się nie mieć wiele …
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.