Rozważmy wykres (problem ma sens zarówno dla wykresów skierowanych, jak i niekierowanych). Nazwij macierzą odległości : to najkrótsza odległość ścieżki od wierzchołka do wierzchołka w dla pewnej stałej funkcji agregacji (na przykład lub ).M G G M G [ i , j ] i j G + maxsolGGM.solMGM_GsolGGM.sol[ i...
To mnie dezorientuje. Jednym z łatwych przypadków liczenia jest sytuacja, gdy problem decyzyjny występuje w i nie ma rozwiązań.PPP Wykład pokazuje, że problem zliczania liczby idealnych dopasowań na grafie dwustronnym (równoważnie, zliczanie liczby okładek cykli na ukierunkowanym wykresie) jest...
Posiadam książkę, która zainspirowana Principia Mathematica (PM) Russella i logicznym pozytywizmem próbuje sformalizować konkretną dziedzinę, określając aksjomaty i wydając z nich twierdzenia. Krótko mówiąc, próbuje zrobić dla swojej dziedziny to, co PM próbował zrobić dla matematyki. Podobnie jak...
Conway ma bardzo ładną konstrukcję o surrealistycznych liczbach. Są to „liczby”, które zawierają zarówno liczby rzeczywiste, jak i liczby porządkowe, są całkowicie uporządkowane i mają wszystkie właściwości pola (z wyjątkiem, że nie tworzą zbioru, ale klasę). Zobacz na przykład ten plik pdf lub...
Czy kiedykolwiek zaimplementowano drzewa partycji? Mówię tutaj o drzewach partycji z geometrii obliczeniowej. Najwcześniejsze (prawie) optymalne wersje były spowodowane przez Matouseka i innych, a ostatnio Timothy Chan: https://cs.uwaterloo.ca/~tmchan/optpt_2_10.pdf To dla mnie szaleństwo, że...
Czy są jakieś konkretne (lub bogate źródło) przykłady zastosowania liczb adycznych w
Jaki jest związek między prostym typem rachunku lambda a logiką wyższego rzędu? Pod Curry-Howardem wydaje się, że prosty typ rachunku lambda odpowiada logice zdań. Jak to się ma do logiki wyższego rzędu? Według tego poradnika Geuversa: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf...
Rozważ następujący problem: Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y. Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P...
Jak wiemy, definicja złożoności obliczeniowej algorytmu prawie nie budzi kontrowersji, ale definicja złożoności obliczeniowej rzeczywistych lub modeli obliczeniowych rzeczywistych nie jest w takim przypadku. Model i model Bluma i Smalesa znamy w książce Computable Analysis. I pozornie model w...
Niech będzie polem. Jak zwykle dla f ∈ k [ x 1 , x 2 , … , x n ] definiujemy L ( f ) jako złożoność linii f względem k w linii prostej . Niech K będzie zbiorem jednomianów f , a mianowicie jednomianów, które występują w f z niezerowym współczynniku.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in...
Załóżmy, że nasze dane wejściowe są binarne i musimy wyprowadzić ⌊ x / c ⌋ , gdzie c jest jakąś stałą liczbą całkowitą. To tylko zmiana, jeśli c jest potęgą dwóch, ale co z innymi liczbami? Czy możemy to zrobić z obwodem o stałej głębokości dla każdego c ? Co z c = 3 ?xxx⌊x/c⌋⌊x/c⌋\lfloor x/c...
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno...
Rozważam pomysły dotyczące dokładnych algorytmów kwantowych. W szczególności rozważam prawdopodobne ograniczenia , które składa się z języków dokładnie określonych przez rodziny jednorodnych obwodów kwantowych o jednolitym czasie działania w dowolnym zestawie skończonych...
Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .an≥⋯≥a1an≥⋯≥a1a_n \geq \dots\geq a_1ε∈(0,1)ε∈(0,1)\varepsilon \in...
Czy skończony odwrotny problem izomorfizmu półgrupy GI jest kompletny ? Tutaj zakłada się, że skończone odwrotne półgrupy są podane przez ich tabliczki
Dowód Goldreicha i in., Że trzy kolory mogą mieć zerowe dowody wiedzy, wykorzystuje bitowe zaangażowanie w całe zabarwienie wykresu w każdej rundzie [1]. Jeśli wykres ma wierzchołków i krawędzie, bezpieczne hash ma bitów i szukamy błędów prawdopodobieństwo , całkowity koszt komunikacjie b...
Obecnie słucham przemówienia Alana Kaysa „Czy to naprawdę skomplikowane, czy tylko skomplikowaliśmy?” ( Https://www.youtube.com/watch?v=ubaX1Smg6pY&= ), w którym mówi, że „semafory były złym pomysłem i nie było coś, co nazywa czas pseudo że była lepsza” (at 51:40 na połączonego materiału...
Drzewo decyzyjne do odczytu definiuje się następująco: and F danej ł s e się do odczytu po drzew decyzyjnych.T.R u eTrueTruefaa l s eFalseFalse Jeśli i B są drzewami decyzyjnymi do odczytu, a x jest zmienną nie występującą w A i B , to ( x ∧ A ) ∨ ( ˉ x ∧ B ) jest również drzewem decyzyjnym do...
System dodawania wektorów (VAS) to skończony zestaw działań . jest zbiorem oznaczeń . Trasa jest niepusty słowo oznaczenia st . Jeśli takie słowo istnieje, mówimy, że jest osiągalne z .A⊂ZdA⊂ZdA \subset \mathbb{Z}^dm 0 m 1 … m n ∀ i ∈ { 0 , … , n - 1 } , m i + 1 - m i ∈ A m n m...
W moim starym czeskim podręczniku algorytmów natknąłem się na następujący problem, niestety przyszedł bez wskazówek i rozwiązania. „Określamy Fibonacciego słów , , , gdzie i są ogólnie literami. Jak w danej ciąg (ponad potencjalnie dużym alfabetem) czy możesz znaleźć najdłuższe pod-słowo...