Teoretyczne informatyka lower-bounds

1

Optymalność algorytmu Grovera z dużym prawdopodobieństwem powodzenia

Dobrze wiadomo, że złożoność kwantowej kwerendy błędu ograniczonego funkcji to . Teraz pytanie brzmi: czy chcemy, aby nasz algorytm kwantowy odniósł sukces dla każdego wejścia z prawdopodobieństwem a nie ze zwykłą . Jeśli chodzi o jakie byłyby odpowiednie górne i dolne granice?O R (x1,x2), ... ,xn)OR(x1,x2,…,xn)OR(x_1,x_2,\ldots, x_n)Θ (n--√)Θ(n)\Theta(\sqrt{n})1 - ϵ1−ϵ1-\epsilon2 …

9 cc.complexity-theory ds.algorithms quantum-computing lower-bounds

2

Istnienie „matryc do barwienia”

Edycja: teraz jest pytanie uzupełniające związane z tym postem. Definicje Niech i będą liczbami całkowitymi. Używamy notacji .ccckkk[i]={1,2,...,i}[i]={1,2,...,i}[i] = \{1,2,...,i\} macierzy mówi się -to- barwiących matrycy , jeśli zachodzi:c×cc×cc \times cM=(mi,j)M=(mi,j)M = (m_{i,j})ccckkk mamy dla wszystkich ,mi,j∈[k]mi,j∈[k]m_{i,j} \in [k]i,j∈[c]i,j∈[c]i, j \in [c] dla wszystkich z i mamy .i,j,ℓ∈[c]i,j,ℓ∈[c]i,j,\ell \in [c]i≠ji≠ji …

9 co.combinatorics lower-bounds dc.distributed-comp

1

Dolne granice funkcji progowej

W złożoności drzewa decyzyjnego funkcji boolowskiej bardzo dobrze znaną metodą dolnej granicy jest znalezienie (przybliżonego) wielomianu reprezentującego funkcję. Paturi podał charakterystykę symetrycznych funkcji boolowskich (częściowych i całkowitych) pod względem oznaczonej ilościΓΓ\Gamma: Twierdzenie ( Paturi ): Niechfff być dowolną niestałą funkcją symetryczną i oznaczać fk=f(x)fk=f(x)f_k=f(x) kiedy |x|=k|x|=k|x|=k (tj. masa młota wynosząca …

9 cc.complexity-theory quantum-computing lower-bounds boolean-functions query-complexity

Pytania otagowane jako lower-bounds