Pytania otagowane jako reference-request

Prośba o referencję jest wykorzystywana, gdy autor musi wiedzieć o pracy związanej z pytaniem.

2
Zastosowania XORification
XORification to technika utrudniania funkcji lub formuły boolowskiej poprzez zastąpienie każdej zmiennej XOR k ≥ 2 odrębnych zmiennych x 1 ⊕ … ⊕ x k . xxxk≥2k≥2k\geq 2x1⊕…⊕xkx1⊕…⊕xkx_1 \oplus \ldots \oplus x_k Zdaję sobie sprawę z zastosowania tej techniki w złożoności dowodu, głównie w celu uzyskania niższych granic przestrzeni dla …
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
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 …
2
Czy istnieje twierdzenie Hierarchia czasu dla PH?
Czy to prawda, że ​​w hierarchii wielomianowej występują problemy, które można rozwiązać w czasie O(nk)O(nk)O(n^k) (przez naprzemienną maszynę Turinga na pewnym poziomie hierarchii wielomianowej), których nie można rozwiązać w O(nk−1)O(nk−1)O(n^{k-1}) na żadnym poziomie hierarchia wielomianowa? Innymi słowy - czy istnieje twierdzenie o hierarchii czasu dla hierarchii wielomianowej, tak jak ma …
1
Poczwórna struktura danych (Delaunay / Voronoi)
2 pytania do geometrii obliczeniowej lub algebraistów: Właśnie zaczynam nurkować w geometrii obliczeniowej i uwielbiam ją =) Próbuję przeczytać słynny artykuł Guibasa i Stolfiego zatytułowany „Prymitywy do manipulowania ogólnymi poddziałami i obliczaniem diagramów Voronoi” w celu zaimplementowania algorytmu triangulacji Delaunaya. Kusi mnie, aby pominąć wszystkie teoretyczne rzeczy i po prostu …
3
Uogólnienia metody Brzozowskiego pochodnych wyrażeń regularnych do gramatyki?
Metoda pochodnych Brzozowskiego jest bardzo ładną techniką do budowania deterministycznych automatów z wyrażeń regularnych w ładnie algebraiczny sposób. Opracowałem kilka uroczych uogólnień tej techniki do obsługi niektórych większych klas gramatycznych, ale algorytmy są na tyle proste, że wydaje się całkiem możliwe, że zostały wcześniej odkryte. Ale wydaje się, że odniesienia …
1
Układanka do cięcia pałeczek
Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2. Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1 , 2 , … , n1,2),…,n{1,2,\ldots,n} Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja: http://www.iwriteiam.nl/cutsticks.html Co jeszcze wiadomo na …
1
Przestrzeń topologiczna związana z SAT: czy jest zwarta?
Spełnialności problemem jest to, oczywiście, podstawowym problemem teoretycznym CS. Bawiłem się jedną wersją problemu z nieskończenie wieloma zmiennymi. \newcommand{\sat}{\mathrm{sat}} \newcommand{\unsat}{\mathrm{unsat}} Podstawowe ustawienia. Niech będzie niepustym i prawdopodobnie nieskończonym zestawem zmiennych . Dosłowność to albo zmienna albo jej negacja . Klauzula jest rozróżnieniem skończonej liczby literałów . Na koniec definiujemy formułę …
2
Odniesienie do „bardziej algebraicznego” podejścia do automatów wypychających i świetlówek kompaktowych?
W książce Sakarovitcha na temat teorii automatów jest napisane we wstępie do części dotyczącej racjonalności w wolnej grupie, że przedstawiony w niej materiał stanowi „fundament prawdziwie matematycznej teorii języków bezkontekstowych”. Nie jest to jednak jednoznaczne, ponieważ języki bezkontekstowe i automaty wypychające są poza zakresem książki. Zdaję sobie sprawę z niektórych …
5
Dlaczego ekonomiści powinni dbać o złożoność obliczeniową
Czy próbując przekonać ekonomistów o znaczeniu teorii złożoności w druku, istnieje standardowe odniesienie do cytowania? Znam post na blogu Noama Nisana , ankietę Tima Roughgarden i rozdział 11 eseju Scotta Aaronsona . Te posty są dostępne dla informatyków, ale nie używają języka ekonomistów i nie są publikowane w miejscach zwykle …
3
Konstruktywnie wydajne algorytmy bez sprawdzania poprawności i wydajności
Szukam naturalnych przykładów wydajnych algorytmów (tj. W czasie wielomianowym) ul ich poprawność i skuteczność można konstruktywnie udowodnić (np. w lub ), alePRAPRAPRAHAHAHA nie jest znany żaden dowód wykorzystujący tylko wydajne koncepcje (tzn. nie wiemy, jak udowodnić ich poprawność i wydajność w lub ).TV0TV0TV^0S12S21S^1_2 Mogę samodzielnie tworzyć sztuczne przykłady. Chcę jednak …
1
Czy PRIMEGAME Conwaya generuje wszystkie podstawowe moce 2?
Większość stron, które odwiedziłem czytając ten interesujący temat, podaje coś podobnego „jedynymi potęgami dwóch (innych niż 2), które występują w tej sekwencji, są te z głównym wykładnikiem potęgi” (MathWorld) lub „Po 2 sekwencja ta zawiera następujące potęgi 2: [...], które są podstawowymi potęgami 2”. (Wikipedia) Te staranne sformułowania sugerowałyby, że …
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.