Dolne granice obliczania funkcji zbioru

Posiadanie zestawu $A$ z elementów, powiedzmy, że chcę obliczyć funkcję która jest wrażliwa na wszystkie części danych wejściowych, tj. zależy od samego elementu (tzn. można zmienić dowolny element na coś innego, aby uzyskać nowe wejście pierwsza wartość na i są różne). $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Na przykład może być sumą lub średnią. $f$

Czy istnieje wynik, który dowodzi, że w pewnych warunkach czas potrzebny deterministycznej maszynie Turinga do obliczenia będzie ? $f$ $\Omega(n)$

complexity-theory

— Виталий Олегович
źródło

Zauważ, że jeśli

A

$A$ jest sekwencją z losowym dostępem, a założenie czułości jest osłabione, nie zawsze tak jest. Na przykład,

(i, x_{1}, \dots, x_{n}) \to x_{i}

$(i,x_1,\dots,x_n) \to x_i$ można obliczyć za pomocą dwóch zapytań, nawet jeśli nie jest to junta.

— sdcvvc,

@sdcvvc Twój przykład przypomina mi instrukcji języka C V[i]. Jaka jest definicja junta ?

— Виталий Олегович

k

$k$ -junta to funkcja boolowska, która zależy tylko od

k

$k$ argumenty, tzn. istnieje zestaw

A \subset {1, 2, \dots, n}

$A\subset\{1,2,\dots,n\}$ wielkościowy

k

$k$ tak, że dla każdego

x

$x$ ,

y

$y$ , gdyby

x

$x$ i

y

$y$ różnią się tylko pozycjami na zewnątrz

A

$A$ , następnie

f (x) = f (y)

$f(x)=f(y)$ . Nadużyłem tego terminu, aby oznaczać funkcję, która nie zależy od wszystkich argumentów.

— sdcvvc

Jeśli próbujesz znaleźć wsparcie dla swojej odpowiedzi na problem średniej odległości na stronie math.se, niestety to nie zadziała.

— Aryabhata

@Aryabhata pierwszą intencją było znalezienie wsparcia dla mojej odpowiedzi na to pytanie: math.stackexchange.com/questions/129969/… , ale jedyne, co ten wynik powie, to że jeśli są

n

$n$ wierzchołki na wykresie, algorytm obliczający ich średnią odległość

Ω (n)

$\Omega(n)$ , co jest dość oczywiste. Usunąłem tam swoją odpowiedź, ponieważ jak napisałeś, niczego nie udowodniłem.

— Виталий Олегович

Musisz określić model obliczeń i właściwości $f$ . W poniższym argumencie przedstawię założenia, których potrzebuję. Można go nieco bardziej uogólnić, ale myślę, że powinien wystarczyć, aby dać ci pomysł.

Załóż, że maszyna $M$ nigdy nie odczytuje wartości jednego z członków $A$ (ustalony zestaw oraz $A$ podano jako listę). Załóżmy ponadto, że $A$ jest takim wejściem, że zmiana jego wartości $i$ członek się nie zmienia $M$ odpowiedź. Załóżmy ponadto, że $f$ jest wrażliwy na wszystkie części danych wejściowych, tzn. zależy od samego członka $A$ (tzn. można zmienić dowolnego członka $A$ na coś innego, aby uzyskać nowy wkład $A'$ wartość st $f$ na $A$ i $A'$ są różne).

Możemy użyć argumentu przeciwnika, aby pokazać, że maszyna nie może obliczyć poprawnej odpowiedzi, zmieniając wartość tego elementu $A$ pozyskać $A'$ w innym przypadku wartość $f$ jest inny. Wartość $M$ na tych dwóch zestawach jest taki sam, więc jeden z nich musi być fałszywy i dlatego $M$ nie można obliczyć $f$ poprawnie.

Dlatego każda maszyna $M$ to oblicza $f$ będzie musiał przeczytać wszystkie potrzebne dane wejściowe $\Omega(n)$ kroki.

(Z drugiej strony, załóżmy, że mamy niedeterministyczną maszynę o swobodnym dostępie i chcemy obliczyć OR bitów na wejściu. Możemy niedeterministycznie zgadnąć trochę i sprawdzić, czy to jest 1, jeśli jest to 1, wyprowadzamy 1 To urządzenie odczytuje tylko jeden bit wejścia $O(\lg n)$ kroki i poprawnie rozwiązuje problem. Więc bez założeń $M$ i $f$ wynik nie ma zastosowania).

— Kaveh
źródło

Przepraszam, zapomniałem napisać, że moim modelem obliczeniowym była deterministyczna maszyna Turinga.

— Виталий Олегович

+1 za argument przeciwnika, który jest świetnym sposobem na rozpoczęcie zrozumienia dolnych granic.

— Joe