(Przepraszam, jeśli jest to dobrze znane.) Chciałbym podać jakiś przedmiot jednemu z agentów, aby agent j otrzymał element z prawdopodobieństwem p i . Czy istnieje narzędzie kryptograficzne (lub inne), aby każdy agent (a nawet każdy obserwator) był w stanie przekonać się, że losowe losowanie...
Załóżmy, że jest wykresem z liczbą barwiącą d = χ ( G ) . Rozważ następującą grę między Alicją i Bobem. W każdej rundzie Alicja wybiera wierzchołek, a Bob odpowiada kolorem { 1 , … , d - 1 } dla tego wierzchołka. Gra kończy się, gdy zostanie odkryta monochromatyczna krawędź. Niech X ( G ) będzie...
Chciałbym zapytać o szczególny przypadek pytania „ Decyzja, czy dany obwód NC 0 oblicza permutację ” QiCheng, na który nie udzielono odpowiedzi. Obwód boolowski nazywa się obwodem NC 0 k , jeżeli każda bramka wyjściowa syntaktycznie zależy od co najwyżej k bramek wejściowych. (Mówimy, że bramka...
W złożoności obliczeniowej istnieje istotne rozróżnienie między obliczeniami monotonicznymi i ogólnymi, a słynne twierdzenie Razborova stwierdza, że 3-SAT, a nawet DOPASOWANIE nie są wielomianowe w monotonicznym modelu obwodów boolowskich. Moje pytanie jest proste: czy istnieje analog kwantowy...
Edycja: wybieram odpowiedź z najwyższym wynikiem do 6 grudnia 2012 r. To delikatne pytanie. Pojęcie (deterministycznych) algorytmów sięga BC. Co z algorytmami probabilistycznymi? W tym wpisie wiki algorytm Rabina dla problemu najbliższej pary w geometrii obliczeniowej podano jako pierwszy...
Badanie ekologii i ewolucji staje się coraz bardziej matematyczne, ale wydaje się, że większość narzędzi teoretycznych pochodzi z fizyki. Jednak w wielu przypadkach problemy mają bardzo dyskretny charakter (patrz na przykład SLBS00 ) i mogą skorzystać z perspektywy informatyki . Jednak wiem tylko o...
Niedawno czytałem Dwie dualności obliczeń: typy ujemne i ułamkowe . Artykuł rozwija typy sum i typy produktów, nadając semantykę typom a - bi a/b. W przeciwieństwie do dodawania i mnożenia, nie ma jednego, lecz dwa odwrotności potęgowania, logarytmów i rootowania. Jeśli typy funkcji (a → b) są...
To pytanie zostało przeniesione z Computer Science Stack Exchange, ponieważ można na nie odpowiedzieć na Theoretical Computer Science Stack Exchange. Migrował 6 lat temu . Wydaje się, że wiele osób uważa, że , po części dlatego, że wierzą, że faktoring nie jest możliwy do...
Biorąc pod uwagę mmm o nnn binarnego macierzy MMM (wartość wynosi 000 lub 111 ), problemem jest ustalenie, czy istnieje dwoma wektorami binarnymi v1≠v2v1≠v2v_1 \ne v_2 w taki sposób, Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (wszystkie operacje wykonywane przez ZZ\mathbb{Z} ). Czy ten problem jest trudny...
Czy jest przykładem języka, który jest w NPNPNP , ale gdzie nie możemy udowodnić ten fakt bezpośrednio poprzez pokazanie, że istnieje wielomian świadka do członkostwa w tym języku? Zamiast tego fakt, że język znajduje się w NPNPNP , można udowodnić, redukując go do innego języka w NPNPNP , gdzie...
Grothendieck zmarł . Miał ogromny wpływ na matematykę XX wieku trwającą aż do XXI wieku. To pytanie jest zadawane nieco w stylu / duchu, na przykład w sprawie wkładu Alana Turinga w informatykę . Jakie główne wpływy Grothendiecka na informatykę
Jakie problemy należą do ale nie są znane z ?BPPBPP\mathsf{BPP}PP\mathsf P Mówiąc dokładniej, interesują mnie niezależne problemy, czyli takie, których derandomizacje nie są znane jako równoważne. Na przykład wiadomo, że derandomizacja PIT i wieloczynnikowe wielomianowe rozkładanie na czynniki są...
Klasyczne problemy z kolejką pytają, biorąc pod uwagę dodatnią liczbę całkowitą n , czy istnieje tablica Q [ 1 .. n ] liczb całkowitych spełniająca następujące warunki:nnnnnnQ [ 1 .. n ]Q[1..n]Q[1..n] dla wszystkich i1 ≤ Q [ i ] ≤ n1≤Q[i]≤n1\le Q[i] \le njaii dla wszystkich i ≠ jQ [ i ] ≠ Q [ j...
W mojej edukacji informatycznej coraz częściej zauważam, że większość dyskretnych problemów jest NP-kompletna (przynajmniej), podczas gdy optymalizacja ciągłych problemów jest prawie zawsze łatwo osiągalna, zwykle za pomocą technik gradientowych. Czy są od tego
Uważam ten artykuł za bardzo interesujący. Podsumowując: omawia, dlaczego w praktyce rzadko znajduje się najgorszy przypadek problemu NP-zupełnego. Idea tego artykułu polega na tym, że przypadki są zwykle bardzo niedostatecznie lub bardzo przeciążone, a oba są stosunkowo łatwe do rozwiązania....
Usiłuję objąć głowę prawdziwymi różnicami między modelem współbieżności aktora a modelem współbieżności procesów komunikacji sekwencyjnej (CSP). Do tej pory najlepsze, co udało mi się wymyślić, to to, że Model aktora pozwala na zmianę liczby i układu węzłów, podczas gdy CSP ma stałą strukturę...
Rozważ problem minimalnego pokrycia zestawu z następującymi ograniczeniami: każdy zestaw zawiera co najwyżej kkk elementów, a każdy element wszechświata występuje w co najwyżej zestawach fff Na przykład: w przypadku k=4k=4k = 4 i f=2f=2f = 2 odpowiada minimalnej wierzchołek problemu pokrywy na...
Czy można przetłumaczyć wzór B logiczny na równoważną kombinację klauzul Horna? Artykuł w Wikipedii na temat HornSAT wydaje się sugerować, że tak, ale nie byłem w stanie ścigać żadnego odniesienia. Zauważ, że nie mam na myśli „w czasie wielomianowym”, ale raczej „w...
Obecnie czytam „ Lambda-Calculus and Combinators ” Hindleya i Seldina. Nie jestem ekspertem, ale zawsze interesowałem się rachunkiem lambda ze względu na zaangażowanie w programowanie funkcjonalne (zaczynając od Lisp i SICP, a teraz od R i Haskell). W „ Binary rachunek lambda i rachunek...
Czy występują jakieś naturalne problemy w , które nie są (wiadomo, że są / sądzi się, że są) w U P ∩ c o U P ?N.P.∩ c o NP.NP∩coNPNP \cap coNPUP.∩ c o UP.UP∩coUPUP \cap coUP Oczywiście wielki każdy wie o w jest wersja decyzja faktoringu (czy n mają współczynnik wielkości co najwyżej k), ale to...