Pytania otagowane jako reference-request

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

1
Czy bitcoin jest kryptograficznie bezpieczny
Próbuję zrozumieć protokół bitcoin w kontekście obliczeniowych zabezpieczeń kryptograficznych. Pytanie dotyczy prośby o odniesienie do podstaw artykułów z kryptografii na bitcoinach. Moje pierwsze pytanie brzmi: jaki bitcoin abstrakcyjnego protokołu kryptograficznego próbuje wdrożyć? Czy mamy definicję pieniądza elektronicznego / waluty cyfrowej w kryptografii, która przechwytuje bitcoiny? Jakie są wymagania bezpieczeństwa dotyczące …
1
Zwycięska strategia gry polegającej na usuwaniu „krawędzi lub izolowanego wierzchołka”
Czy ta doskonała gra informacyjna rozgrywana na wykresach jest znana / studiowana? Biorąc pod uwagę wykres G=(V,E)G=(V,E)G= (V,E) , dwóch graczy na przemian wybiera krawędź lub izolowany węzeł. Jeśli gracz wybierze krawędź e=(u,v)e=(u,v)e = (u,v) dwa węzły uuu i vvv zostaną usunięte wraz ze swoimi krawędziami padania. Jeśli gracz wybierze …
1
Górna granica stopnia funkcji boolowskiej pod względem jej czułości
Bardzo interesującym otwartym problemem w badaniu miar złożoności funkcji boolowskiej jest tak zwana hipoteza wrażliwości vs. blokowa. Informacje na temat wrażliwości kontra czułości bloków można znaleźć na następującym blogu S. Aaronsona na stronie http://www.scottaaronson.com/blog/?p=453 . Według mojej najlepszej wiedzy, najlepszą górną granicą znaną na w kategoriach s ( f ) …
1
Wyniki dla niższych granic / twardości w Noisy Parity (LWE)
Niektóre tło: Chciałbym znaleźć „mniej znane” dolne granice (lub wyniki twardości) dla problemu Uczenie się z błędami (LWE) i ich uogólnienia, takie jak Uczenie się z błędami przez pierścienie. W celu uzyskania szczegółowych definicji itp. Oto miła ankieta przeprowadzona przez Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Standardowym rodzajem założenia w stylu (R) LWE jest …
2
Na
EDYCJA (autor: Tara B): Nadal byłbym zainteresowany odniesieniem do dowodu na to, ponieważ musiałem to udowodnić na własne potrzeby. Szukam dowodu Twierdzenia 4, który pojawia się w tym artykule: Nieskończona hierarchia skrzyżowań języków bezkontekstowych autorstwa Liu i Weinera. Twierdzenie 4: wymiarową afinicznej kolektor jest do ekspresji w skończonej związek rozdzielaczy …
2
Warianty galerii sztuki z widocznością parą?
Problem z tradycyjną galerią sztuki tworzy region i strażników z pewnym pojęciem widoczności i prosi o minimalną liczbę strażników, którzy muszą być umieszczeni, aby zobaczyć cały region. Czy ktoś kiedykolwiek oglądał warianty galerii sztuki, w których obszar widoczności jest definiowany przez parę strażników. Na przykład, jedną z formuł może być …
2
Gry nielokalne i komunikacja kwantowa
Obecnie szukam dobrych materiałów referencyjnych dotyczących nielokalnych gier o korzystnych aspektach w komunikacji kwantowej. Na przykład jestem świadomy, że gry nielokalne są dobre w ograniczaniu złożoności komunikacji, a także w zapewnieniu bezpieczeństwa protokołów QKD. Chciałbym wiedzieć, jakie są niektóre z wielkich artykułów na temat nielokalnych gier w komunikacji kwantowej? Czy …
1
Złożoność unikalnej łączności st
Chciałbym wiedzieć, czy w (niedeterministyczny obszar logów) można rozstrzygnąć następujący problem :N L.NL\mathsf{NL} Biorąc pod uwagę ukierunkowany wykres z dwoma wyróżnionymi wierzchołkami s i t , czy istnieje unikalna ścieżka od s do t w G ?solGGssstttssstttsolGG Czuję, że to może być w ponieważ możemy zdecydować, zarówno jeśli istnieje s …
1
Biorąc pod uwagę PDA M taki, że L (M) jest w DCFL konstruuj DPDA N, tak że L (N) = L (M)
Czy można zbudować algorytm, który przyjmuje jako dane wejściowe automat do przesuwania wraz z obietnicą, że język zaakceptowany przez ten automat L ( M ) jest deterministycznym językiem bezkontekstowym i wysyła deterministyczny automat do przesuwania N, który akceptuje dokładnie zaakceptowany język przez M ?MMML(M)L(M)L(M)N.NNM.MM Równoważne problemu byłoby skonstruować algorytm, który …
2
Odniesienia do języków programowania opartych na logice warunkowej
Logiki warunkowe to logiki, które rozszerzają tradycyjną implikację logiczną za pomocą operatorów modalnych odpowiadających innym pojęciom warunku (na przykład przyczynowy warunkowy brzmi „ powoduje„ B ”lub warunkowanie probabilistyczne „ ”, które brzmi „ dany B ”).A A | B AA□→BA◻→BA\; \square\!\!\!\!\to BAAAA|BA|BA|BAAABBB Zazwyczaj logiki te są badane teoretycznie modelowo, ale …
4
Znalezienie skończonego modelu
Wiem, że pytanie „czy formuła pierwszego rzędu ma model” jest ogólnie nierozstrzygalne.ϕϕ\phi Czy ktoś mógłby mi dać link lub książkę, która da odpowiedź na skończone modele. Jeśli mam wzór pierwszego rzędu , czy można rozstrzygnąć, czy ϕ ma model skończony? Jestem pewien, że pytanie jest dobrze znane, ale nawet nie …
1
Złożoność przestrzeni dla średnich przypadków
Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić …
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.