Teoretyczne informatyka

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

1
Czy możemy uzyskać posortowaną listę z posortowanej macierzy w
Jestem zmieszany. Chcę udowodnić, że problem sortowania macierzy przez , tj. Wiersze i kolumny są w porządku rosnącym, to . Kontynuuję, zakładając, że można to zrobić szybciej niż i próbuję złamać dolną granicę Dla porównań potrzebnych do posortowania m elementów. Mam dwie sprzeczne odpowiedzi:nnnnnnΩ (n2)logn )Ω(n2)log⁡n)\Omega(n^2\log n)n2)lognn2)log⁡nn^2\log nlog( m ! …
1
(Kryptograficzne) problemy do rozwiązania w wielomianowej liczbie kroków arytmetycznych
W artykule Adi Shamira [1] z 1979 r. Pokazuje, że faktoring można wykonać w wielomianowej liczbie kroków arytmetycznych . Fakt ten został powtórzony i dlatego zwrócił moją uwagę w niedawnej pracy Borweina i Hobarta [2] w kontekście programów liniowych (SLP). Ponieważ byłem raczej zaskoczony, gdy to przeczytałem, mam następujące pytanie: …
2
Certyfikowany kompilator i optymalizacje w Coq / Agda
Interesują mnie sprawdzone kompilatory sformalizowane w teorii typów Martina-Löfa, tj. Coq / Agda. W tej chwili napisałem przykład małej zabawki. Dzięki temu mogę udowodnić, że moje optymalizacje są prawidłowe. Na przykład można wyeliminować dodawanie zerowe, tzn. Wyrażenia takie jak „x + 0”. Czy istnieją optymalizacje, które są trudne do przeprowadzenia …
1
CTL * i rachunek różniczkowy
dobrze wiadomo, że modal -calculusμμ\mu jest jedną z najbardziej ekspresyjnych logik czasowych do wyrażania właściwości drzew / grafów, i że CTL * jest ściśle mniej ekspresyjny niż -calculus.μμ\mu W tym miejscu chciałbym poprosić o przykład formuły calculus, tak prostej, jak to możliwe, która nie jest wyrażalna w CTL *, i …
1
„Informacje możliwe do zweryfikowania”: czy jest to znana koncepcja?
Poniższe wydaje mi się naturalną definicją i zastanawiam się, czy gdzieś to zbadano Rozważać X⊂2{0,1}∗X⊂2{0,1}∗\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}zestaw języków. NastępnieK⊂{0,1}ωK⊂{0,1}ωK \subset \lbrace 0, 1 \rbrace^\omega nazywa się "XX\mathsf{X}-weryfikowalne informacje ”, gdy są L∈XL∈XL \in \mathsf{X} św (i) Biorąc pod uwagę x∈Lx∈Lx \in L, każdy prefiks xxx jest w …
2
Czy istnieje skuteczny algorytm do znalezienia i-tej drogi?
Oto tło tego pytania. Graliśmy z przyjaciółmi w grę, w której każdy musi dać innym ludziom prezent. Aby ustalić, kto powinien komuś dać prezent, decydujemy się na losowanie. Problem w tym, że ktoś może dać sobie prezenty, co nie jest śmieszne. Widać, że oczekiwana liczba takich nieszczęśliwych osób wynosi 1, …
1
Minimalne drzewo opinające dla wszystkich dopasowań wierzchołków
Natknąłem się na ten problem z dopasowaniem, dla którego nie jestem w stanie zapisać algorytmu czasu wielomianowego. Pozwolić P,QP,QP, Qbyć kompletnymi wykresami ważonymi z zestawami wierzchołków odpowiednio i , gdzie . Ponadto pozwalają i być funkcje ciężar na krawędziach i , odpowiednio.PVPVP_VQVQVQ_V|PV|=|QV|=n|PV|=|QV|=n|P_V| = |Q_V|=nwPwPw_PwQwQw_QPPPQQQ W przypadku modyfikujemy w następujący sposób: …
2
Wyniki dotyczące złożoności funkcji rekurencyjnych o niższych elementach?
Zaintrygowany ciekawym pytaniem Chrisa Presseya na temat funkcji elementarno-rekurencyjnych badałem więcej i nie mogłem znaleźć odpowiedzi na to pytanie w Internecie. Te podstawowe funkcje rekurencyjne odpowiadają dobrze wykładniczemu hierarchii .DTIME (2)n) ∪ DTIME (2)2)n) ∪ ⋯DTIME(2n)∪DTIME(22n)∪⋯\text{DTIME}(2^n) \cup \text{DTIME}(2^{2^n}) \cup \cdots Z definicji wydaje się proste, że problemy decyzyjne rozstrzygalne (termin?) …
1
Czy teoria typów Martina-Löfa przyczyni się do większej zdolności do pisania poprawnego kodu, który da się udowodnić
Ten post odnosi się do izomorfizmu Curry'ego-Howarda i teorii typów Martina-Löfa . W postie stwierdza się o przyszłym „zjednoczeniu” języka opisu matematyki z językiem programowania komputerowego opartym na operacjach. Moje pytania to: Czy te pomysły doprowadzą do lepszej zdolności (poprzez języki) do pisania możliwego do udowodnienia poprawnego kodu? Czy pełne …
1
Prosty dowód, że rozstrzygalność typowalności w systemie F ( ) implikuje rozstrzygalność sprawdzania typu?
Załóżmy, że nie znamy wyniku Joe B. Wellsa z 1994 roku, że zarówno typowość, jak i sprawdzanie typów są nierozstrzygalne w Systemie F (AKA ). W rachunku Lambda z typami Barendregta (1992) znalazłem dowód z powodu Maleckiego 1989, że sprawdzanie typów implikuje typowość. To dlatego, żeλ 2λ2)\lambda 2 istnieje taki, …
1
Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia
Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice?O R (x1,x2), ... ,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n)Θ (n--√)Θ(n)\Theta(\sqrt{n})1 - ϵ1−ϵ1-\epsilon2 …
3
Czy można obliczyć, czy dwie funkcje są równe ekstensywne?
Jeśli masz dwie funkcje implementujące inny algorytm sortowania, to czy można na podstawie kodu źródłowego wnioskować, że obie mają takie same właściwości zewnętrzne? Czy to znaczy, że oboje będą mieć możliwą nieposortowaną sekwencję jako dane wejściowe i posortowaną sekwencję jako dane wyjściowe? W jaki sposób te właściwości zewnętrzne mogą być …
2
Intuicja za systemami dowodowymi
Próbuję zrozumieć artykuł na temat p-Optimal Proof Systems and Logic for PTIME . W artykule jest pojęcie nazywane systemami dowodowymi i nie rozumiem intencji: Σ = { 0 , 1 }Σ={0,1}\Sigma = \{0,1\} ... Identyfikujemy problemy z podzbiorami w .QQQΣ∗Σ∗\Sigma^* Myślę, że intencją jest to, że kodujemy pewną strukturę w …
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.