Teoretyczne informatyka

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

3
Wymień czas i złożoność zapytań
Praca bezpośrednio ze złożonością czasu lub dolnymi granicami obwodu jest przerażająca. Dlatego opracowujemy narzędzia takie jak złożoność zapytań (lub złożoność drzewa decyzyjnego), aby uzyskać kontrolę nad dolnymi granicami. Ponieważ każde zapytanie zajmuje co najmniej jeden krok jednostkowy, a obliczenia między zapytaniami są liczone jako wolne, złożoność czasu jest co najmniej …
1
Najbardziej wydajny sposób na konwersję obwodu na obwód (dowolnej głębokości) za pomocą fanout 1 bramki
EDYCJA (22 sierpnia 2011 r.): Jeszcze bardziej upraszczam pytanie i wyróżniam je. Być może to prostsze pytanie będzie miało łatwą odpowiedź. Przekreślę także wszystkie części pierwotnego pytania, które nie są już istotne. (Podziękowania dla Stasysa Jukny i Ryana O'Donnella za częściową odpowiedź na oryginalne pytanie!) Tło: Biorąc pod uwagę obwód …
4
Czy testy mogą wykazać brak błędów?
(n+1)(n+1)(n + 1) punkty są wymagane do jednoznacznego określenia wielomianu stopnia ; na przykład dwa punkty na płaszczyźnie określają dokładnie jedną linię.nnn Ile punktów jest wymaganych do jednoznacznego określenia funkcji obliczeniowej , biorąc pod uwagę długość programu, który oblicza w ustalonym języku? (tj. związany ze złożonością Kołmogorowa ).f:N→Nf:N→Nf : N …
4
Jaki jest sens konwersji
Myślę, że tego nie rozumiem, ale konwersja wygląda na mnie jako konwersja β , która nic nie robi, szczególny przypadek konwersji β, w której wynikiem jest tylko termin z abstrakcji lambda, ponieważ nie ma nic do zrobienia, rodzaj bezcelowej konwersji β .ηη\etaββ\betaββ\betaββ\beta Może więc konwersja jest czymś naprawdę głębokim i …
1
Bitcoin i zapobieganie podwójnym wydatkom w zdecentralizowanych walutach cyfrowych
Ostatnie podejście do tworzenia zdecentralizowanej waluty internetowej, zwanej Bitcoin , wzbudza pewne zainteresowanie. Celem jest posiadanie sposobu na przelewanie waluty bez centralnego organu i bez podwójnych wydatków lub fałszowania. Ich podejście polega na tym, że wszystkie węzły w sieci próbują zweryfikować transakcję, wykonując obliczenia typu proof-of-work, a następnie transakcje o …
4
Bezpośrednia redukcja SAT do 3-SAT
Tutaj celem jest zredukowanie arbitralnego problemu SAT do 3-SAT w czasie wielomianowym przy użyciu jak najmniejszej liczby klauzul i zmiennych. Moje pytanie jest motywowane ciekawością. Mniej formalnie chciałbym wiedzieć: „Jaka jest„ najbardziej naturalna ”redukcja z SAT na 3-SAT?” Teraz zmniejszenie, które zawsze widziałem w podręcznikach, wygląda mniej więcej tak: Najpierw …
2
Dlaczego komputerowi tak trudno jest coś udowodnić?
To może być uznane za głupie pytanie. Nie jestem informatyką (i jeszcze nie jestem matematyką), więc przepraszam, jeśli uważasz, że poniższe pytania zawierają pewne błędne założenia. Chociaż istnieją plany sformalizowania ostatniego twierdzenia Fermata (patrz ta prezentacja ), nigdy nie czytałem ani nie słyszałem, że komputer może udowodnić nawet „proste” twierdzenie …
2
Rozwiązywanie labiryntu z numerami
Mój 8-latek znudził się tworzeniem konwencjonalnych labiryntów i zaczął tworzyć warianty, które wyglądają tak: Chodzi o to, aby zacząć od x i osiągnąć normalne zasady. Dodatkowo możesz „przeskoczyć” z dowolnej liczby całkowitej aaa na inną liczbę całkowitą bbb , ale musisz zapłacić |a−b||a−b||a-b|dolarów za przywilej. Celem jest rozwiązanie labiryntu przy …
1
Jaki jest status logiki rozmytej dla TCS w 2011 roku?
Przeglądam Podręcznik informatyki inspirowanej naturą i innowacji dla SIGACT News. To bardzo interesująca lektura. Każdy rozdział ma jednak smak: „To moja dziedzina badań i do cholery, to niesamowite!” Więc część tego, co próbuję zrobić, to oddzielić szum i dokonać trzeźwej oceny zawartości książki. Jeden rozdział poświęcony jest logice rozmytej i …
3
Klasyfikacja typowych / nietypowych rodzajów Lambda Calculi
Czy ktoś może krótko wyjaśnić (jeśli to możliwe!) Lub odesłać mnie do referencji, podsumowującej różnice między niepisanym rachunkiem lambda i bardziej popularnym typem rachunku lambda? Szczególnie szukam stwierdzeń o ich mocy ekspresyjnej, równoważności z systemami logicznymi / arytmetycznymi lub metodami obliczeniowymi oraz, w stosownych przypadkach, analogii do języków programowania. Chociaż …
2
Znajdź największą kostkę zawartą w unii prostopadłościanów
Mam dużo prostopadłościanów w przestrzeni 3D, każda ma punkt początkowy na (x, y, z) i ma rozmiar (Lx, Ly, Lz). Zastanawiam się, jak znaleźć największą kostkę w tej przestrzeni 3D, która jest zawarta w unii prostopadłościanów. Czy istnieje na to wydajny algorytm? Na przykład, jeśli mam następujące prostopadłościany: prostopadłościan zaczynający …
1
Udowodnić nieistotność dowodu w Coq?
Czy istnieje sposób na udowodnienie następującego twierdzenia w Coq? Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2. EDYCJA : Próba krótkiego wyjaśnienia „czym jest nieistotność dowodu” (popraw mnie, jeśli się mylę lub nieścisłość) Podstawowym założeniem jest to, że w świecie propozycja (lub …
5
Dlaczego P = NP nie oznacza P = AP (tj. P = PSPACE)?
Powszechnie wiadomo, że jeśli wówczas hierarchia wielomianowa upadnie, a .P=NPP=NP\mathbf{P}=\mathbf{NP}P=PHP=PH\mathbf{P}=\mathbf{PH} Można to łatwo zrozumieć indukcyjnie za pomocą maszyn Oracle. Pytanie brzmi - dlaczego nie możemy kontynuować procesu indukcyjnego poza stałym poziomem naprzemienności i udowodnić (aka )?P=AltTime(nO(1))P=AltTime(nO(1))\mathbf{P}=\mathbf{AltTime}(n^{O(1)})AP=PSPACEAP=PSPACE\mathbf{AP}=\mathbf{PSPACE} Szukam intuicyjnej odpowiedzi.
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.