Teoretyczne informatyka

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

1
Naturalne twierdzenia udowodnione tylko „z dużym prawdopodobieństwem”?
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 deterministyczny nie? Przez „losowy dowód” stwierdzenia rozumiem toPPP Istnieje algorytm randomizowany, który przyjmuje dane …
2
Czy każdy język rekurencyjny jest rozpoznawany przez śmiertelną maszynę Turinga?
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 akceptuje L , istnieje również śmiertelna baza TM, która akceptuje …
1
Wyrażenia o szerokości kliki z głębokością logarytmiczną
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 rozkładu co najwyżej . (Patrz np. „Algorytmy …
1
Równoważność kontroli wykonalności i optymalizacji dla systemów liniowych
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 wyszukiwanie binarne. Obie te redukcje są wielomianowe, ale nie silnie wielomianowe (tzn. Zależą od liczby …
2
Przybliżenie w czasie podwykonawczym
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 ) ?2nδ22nδ22^{n^{\delta_2}}δ2∈(0,1)δ2∈(0,1)\delta_2\in(0,1) Szczególnie interesuje mnie to, co wiadomo o …
1
Gładka złożoność nieujemnego stałego
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, silną wskazówką bycia w wygładzonym P było istnienie algorytmu …
2
Pełna kompletność a pełna abstrakcja tłumaczenia programu
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 kompilatora Hasegawy [ 1 , 2 ] i Egger i in. glin. [ 3 ] udowodnić pełną …
2
minimalizowanie wielkości wyrażeń regularnych dla zbiorów skończonych
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 sumą długości wszystkich ciągów. Dane wejściowe to …
1
Czy MALL + nieograniczone typy rekurencyjne Turing jest kompletne?
Jeśli spojrzysz na rekurencyjne kombinatory w nierozpisanym rachunku lambda, takie jak kombinator Y lub kombinator omega: ωY==(λx.xx)(λx.xx)λf.(λx.f(xx))(λx.f(xx))ω=(λx.xx)(λx.xx)Y=λf.(λx.f(xx))(λx.f(xx)) \begin{array}{lcl} \omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\ Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\; (\lambda x.\,f\;(x\;x)) \\ \end{array} Oczywiste jest, że wszystkie te kombinatory kończą kopiowanie gdzieś w swojej definicji. Co więcej, …
2
Czy rozstrzyganie propozycji jest kompletnym systemem dowodowym?
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 rozwiązanie jest niepełne. Rozumiem sens niepełnej rozdzielczości. Rozumiem również, …
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.