Teoretyczne informatyka

2

Rozstrzygalność wnioskowania o typie i sprawdzania typu w MLTT

W Intuitionistycznej teorii typów: część predykcyjna Martina-Löfa udowodniono, że sprawdzanie typówa : Aa:Aa \colon Apodlega rozstrzygnięciu z zastrzeżeniemzaaaprzede wszystkim do pisania , poprzez udowodnienie twierdzenia o normalizacji dla zamkniętych terminów do pisania. Z drugiej strony widziałem, jak napisano w wielu miejscach (Wikipedia, Nördstrom itp.), Że sprawdzanie typu (intensywne) MLTT jest …

9 reference-request type-theory type-inference

1

Zrozumienie dowodu silnej normalizacji rachunku konstrukcji

Mam trudności ze zrozumieniem dowodu silnej normalizacji dla rachunku konstrukcji. Staram się podążać za dowodem zawartym w pracy Hermana Geuversa „Krótki i elastyczny dowód silnej normalizacji dla rachunku konstrukcji”. Potrafię dobrze podążać za główną linią rozumowania. Konstrukcje Geuvers dla każdego typuTTT interpretacja [[T]]ξ[[T]]ξ[\![T]\!]_\xi na podstawie pewnej oceny zmiennych typu ξ(α)ξ(α)\xi(\alpha). …

9 lo.logic type-theory lambda-calculus typed-lambda-calculus

1

Najbardziej znane asymptotyczne rozmiary PCP / 3-SAT

Jakie są najbardziej znane asymptotyczne górne granice wielkości dowodów probabilistycznie sprawdzalnych? Idealnie szukam współczesnej ankiety dotyczącej tego szerokiego pytania, ale jeśli jej nie ma, szczególnie interesuje mnie niedopuszczalność 3-SAT. Niech 7/8 + ε-3-SAT będzie 3-SAT z obietnicą, że jeśli 7/8 + ε część klauzul jest zadowalająca, to instancja jest zadowalająca. …

9 cc.complexity-theory reference-request np-hardness pcp

1

Czy nastąpił jakiś postęp w zaostrzaniu wykładnika, w wyniku którego niezależność ?

Braverman wykazały, że rozkład które -wise niezależnie -fool głębokość obwody wielkości o "sklejanie" The Smolensky aproksymacja i aproksymacja Fouriera funkcji logicznych . Autor i ci, którzy przypuszczali, że to pierwotnie przypuszczają, że wykładnik tam można zredukować do( l o gmϵ)O (re2))(losolmϵ)O(re2))(log \frac{m}{\epsilon})^{O(d^2)}ϵϵ\epsilonrered ZAdo0ZAdo0AC^0mmmZAdo0ZAdo0AC^0O ( d)O(re)O(d)i jestem ciekawy, czy poczyniono postępy …

9 boolean-functions fourier-analysis

1

Uogólnienie stwierdzenia, że monoid rozpoznaje język iff monoid syntaktyczny dzieli monoid

Pozwolić AAAbyć skończonym alfabetem. Dla danego języka składniowym monoid jest dobrze znanym pojęciem w teorii język form. Co więcej, monoid rozpoznaje język jeśli istnieje morfizm taki, że .L⊆A∗L⊆A∗L \subseteq A^{\ast} M(L)M(L)M(L)MMMLLLφ:A∗→Mφ:A∗→M\varphi : A^{\ast} \to ML=φ−1(φ(L)))L=φ−1(φ(L)))L = \varphi^{-1}(\varphi(L))) Mamy więc ładny wynik: Monoid rozpoznaje jeśli jest homomorficznym obrazem submonoidu (napisanego jako …

9 fl.formal-languages automata-theory regular-language algebra monoid

2

Kontrprzykład do algorytmów maksymalnego przepływu z irracjonalnymi wagami?

Wiadomo, że Ford-Fulkerson lub Edmonds-Karp z heurystyczną grubą rurą (dwa algorytmy dla maksymalnego przepływu) nie muszą się zatrzymywać, jeśli niektóre ciężary są nieracjonalne. W rzeczywistości mogą nawet zbierać się na niewłaściwej wartości! Jednak wszystkie przykłady, które mogłem znaleźć w literaturze [odnośniki poniżej oraz odnośniki w nich] wykorzystują tylko jedną wartość …

9 ds.algorithms graph-algorithms max-flow

1

Nazwy systemu F i systemu T.

Czy ktoś wie, skąd pochodzą nazwy System „F” i System „T”? Nie pytam, kto wprowadził te nazwy (Girard System F i Gödel System T), ale co oznaczają „F” i „T”.

9 ho.history-overview type-systems formal-systems

3

Jakie są przykłady tego, jak niejednolita może być przydatna?

Ciekawi mnie, w jaki sposób niejednorodność okazała się przydatna w obliczeniach. Jednym ze sposobów jest losowość, jak wBPP⊆P/polyBPP⊆P/polyBPP \subseteq P/poly, a kolejnym są tabele przeglądowe, które służą do pokazania, że wszystkie języki mają niejednolite obwody. W szczególności interesują mnie sposoby, w jakie obiekty, o których wiadomo, że istnieją za pomocą …

9 circuit-complexity advice-and-nonuniformity

1

Czy sparametryzowana złożoność będzie przyszłością teorii złożoności?

Jestem naukowcem, który pracuje w teorii algorytmów i złożoności, do pewnego stopnia używam sparametryzowanej złożoności. Wydaje mi się, że badacze o sparametryzowanej złożoności są bardzo aktywni (nie mam na myśli, że inni nie) pod względem liczby prac badawczych. Widziałem, że badacze ze złożoności komunikacyjnej, złożoności arytmetycznej itp. Również w większym …

9 soft-question parameterized-complexity

1

Twierdzenie Cantora w teorii typów

Twierdzenie Cantora stwierdza, że Dla każdego zestawu A zbiór wszystkich podzbiorów A ma znacznie większą liczebność niż sam A. Czy można zakodować coś takiego za pomocą typów / propozycji bez odwoływania się do zestawów ZFC? Doceniony zostanie kod lub pseudokod do kodowania tej propozycji w języku zależnym od typu.

9 type-theory set-theory

1

Algorytm do obliczania odległości między mocami

Biorąc pod uwagę coprime a , ba,ba, b, czy możesz szybko obliczyć minx , y> 0|zax-by|minx,y>0|ax−by| \min_{x, y > 0} |a^x - b^y| Tutaj są liczbami całkowitymi. Oczywiście przyjęcie daje nieciekawą odpowiedź; ogólnie, jak blisko te moce mogą się zbliżyć? Jak szybko obliczyć minimalizujące ?x, yx,yx, yx = y= 0x=y=0x …

9 ds.algorithms randomized-algorithms nt.number-theory comp-number-theory

1

Jakie jest prawdopodobieństwo, że losowa funkcja boolowska ma trywialną grupę automorfizmów?

Biorąc pod uwagę funkcję boolowską , mamy grupę automorfizmów .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Czy są jakieś znane granice dla ? Czy jest coś znanego dla ilości postaci dla jakiejś grupy ?Prf(Aut(f)≠1)Prf(Aut(f)≠1)Pr_f(Aut(f) \neq 1)Prf(G≤Aut(f))Prf(G≤Aut(f))Pr_f(G \leq Aut(f))GGG

9 boolean-functions randomness gr.group-theory symmetry

1

Zrozumienie wydajności solverów QFBV SMT

Solwery SMT, takie jak Z3 lub Boolector, wykorzystują złożony zestaw heurystyk do rozwiązywania problemów. Jednak bardzo utrudnia to przewidywanie wydajności takiego rozwiązania. Moje pytanie brzmi zatem: Pytanie Czy istnieje sposób na zrozumienie lub uzyskanie wglądu w wydajność solvera SMT dla konkretnego w teorii bitwektorów bez kwantyfikatora (QFBV)? Obejmuje to także …

9 ds.algorithms sat heuristics

5

Czy sieci neuronowe można wykorzystać do opracowania algorytmów?

Po coraz większych sukcesach sieci neuronowych w grach planszowych wydaje się, że następnym celem, który wyznaczyliśmy, może być coś bardziej przydatnego niż pokonanie ludzi w Starcraft. Dokładniej, zastanawiałem się, czy Czy sieci neuronowe można przeszkolić do rozwiązywania klasycznych problemów algorytmicznych? Mam na myśli, że na przykład sieć otrzyma wykres wejściowy …

9 cc.complexity-theory ds.algorithms machine-learning ne.neural-evol

1

Znajdowanie podgrafów o wysokiej szerokości i stałym stopniu

Dano mi wykres z szerokością i dowolnym stopniem, i chciałbym znaleźć podrozdział z (niekoniecznie indukowany podsgraf) taki, że ma stały stopień, a jego szerokość jest tak wysoka, jak to możliwe. Formalnie mój problem jest następujący: po wybraniu stopnia związanego , jaka jest najlepsza funkcja tak że na dowolnym wykresieGGG kkkHHHGGGHHHd∈Nd∈Nd …

9 co.combinatorics treewidth graph-minor bounded-degree