Teoretyczne informatyka

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

2
Minimalna szerokość drzewa obwodu dla WIĘKSZOŚCI
Jaka jest minimalna szerokość drzewa obwodu powyżej {∧,∨,¬}{∧,∨,¬}\{\wedge,\vee,\neg\} do obliczenia MAJ? Tutaj MAJ :{0,1}n→{0,1}:{0,1}n→{0,1}:\{0,1\}^n \rightarrow \{0,1\} wyprowadza 1, jeśli co najmniej połowa jego danych wejściowych to 111 . Dbam tylko o rozmiar obwodu (powinien być wielomianowy) i że dane wejściowe powinny być odczytywane tylko raz, chociaż rozwarcie bramki wejściowej może …
2
Czy kompilator dla typu zależnego jest znacznie trudniejszy niż interpreter?
Nauczyłem się czegoś o implementowaniu typów zależnych, takich jak ten samouczek , ale większość z nich to implementacja tłumaczy. Moje pytanie brzmi: wydaje się, że implementacja kompilatora dla typu zależnego jest znacznie trudniejsza niż kompilator, ponieważ naprawdę można ocenić argumenty typu zależnego dla sprawdzania typu. Więc Czy moje naiwne wrażenie …
2
Suma niezależnych wykładniczych zmiennych losowych
Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam, że jest to prawda, ale granice, które czytam, wymagają …
1
Czy
Zdefiniuj jako klasę języków, które mogą być akceptowane przez (wielopasmową) maszynę Turinga w czasie f ( n ) + 1 . („ + 1 ” ma jedynie na celu uproszczenie notacji i uniknięcie pomyłek.) Zauważ, że nie ma O ( ⋅ ) wokół f ( n ) + 1 .D …
3
Obwody arytmetyczne o
Rozważ obwód, który przyjmuje jako liczby wejściowe w [ 0 , 1 ][0,1][0,1] i ma bramki, które składają się z funkcji max ( x , y)max(x,y)\max(x, y) , min ( x , y)min(x,y)\min(x, y) , 1 - x1−x1 - x i x + y2)x+y2\frac{x+y}{2} . Wyjście obwodu jest wówczas również …
1
Próbkowanie z wielowymiarowego Gaussa z grafem kowariancji Laplaciana (odwrotna)
Wiemy np. Z Koutis-Miller-Peng (na podstawie pracy Spielmana i Tenga), że możemy bardzo szybko rozwiązać układy liniowe dla macierzy które są wykresem macierzy Laplaciana dla niektórych rzadkich wykresów z nieujemnymi wagami krawędzi .Ax=bAx=bA x = bAAA Teraz (pierwsze pytanie) rozważ użycie jednej z tych grafów macierzy Laplaciana jako kowariancji lub …
1
Jakie formalne klasy językowe to XML i JSON z unikalnymi kluczami?
Przeniosłem to pytanie z stackoverflow, gdzie id nie otrzymał odpowiedzi. Mieliśmy podobne pytanie, czy JSON jest regularny : JSON i XML są często nazywane językami bezkontekstowymi - oba są określone głównie przez gramatykę formalną w EBNF. Jednak dotyczy to tylko JSON zdefiniowanego w RFC 4329, sekcja 2.2, który nie wymaga …
1
Kiedy przestrzenie spójności mają wycofania i wypychania?
\newcommand{\symp}{\Bumpeq} Relacja koherencji ≎X≎X\symp_X na zbiorze XXX jest relacją zwrotną i symetryczną. Przestrzeń koherencji to para (X,≎X)(X,≎X)(X, \symp_X) , a morfizm f:X→Yf:X→Yf : X \to Y między przestrzeniami koherencji jest relacją f⊆X×Yf⊆X×Yf \subseteq X \times Y taką, że dla wszystkich (x,y)∈f(x,y)∈f(x,y) \in f i (x′,y′)∈f(x′,y′)∈f(x',y') \in f , jeśli x≎Xx′x≎Xx′x …
2
Interaktywny dowód liczby Boga?
Ostatnio uczyłem się o interaktywnych dowodach i zastanawiałem się, czy cała ta sprawa była jedynie ciekawostką teoretyczną, czy też miała jakieś praktyczne zastosowania. Myślałem, że zacznę od przykładu, który przyszedł mi do głowy pod prysznicem: Ostatnio ogłaszano, że „liczba Boga” = 20. (Liczba Boga to minimalna liczba kroków potrzebnych do …
2
Zmniejszenie P vs. NP do SAT
W poniższym pytaniu wykorzystano pomysły z kryptografii zastosowane w teorii złożoności. To powiedziawszy, jest to pytanie teoretycznie złożone, i aby odpowiedzieć na to pytanie, nie jest wymagana żadna wiedza kryptograficzna. Celowo piszę to pytanie bardzo nieformalnie. Brakuje szczegółów, prawdopodobnie jest to nieco niepoprawnie podane. Prosimy o wskazanie poprawek w swoich …
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.