Нижние границы вычисления функции множества

Имея набор из элементов, скажем, я хочу вычислить функцию которая чувствительна ко всем частям входных данных, т.е. зависит от самого члена (то есть можно изменить любой член на что-то иначе для получения нового ввода значения на и различны). $A$ $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Например, может быть суммой или средним. $f$

Есть ли результат, который доказывает, что при некоторых условиях время, необходимое детерминированной машине Тьюринга для вычисления будет ? $f$ $\Omega(n)$

complexity-theory Виталий Олегович
источник

Обратите внимание, что если

является последовательностью с произвольным доступом и допущение чувствительности ослаблено, это не всегда выполняется. Например,

можно вычислить с помощью двух запросов, даже если это не хунта.

A

$A$

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

$(i,x_1,\dots,x_n) \to x_i$

sdcvvc

@sdcvvc твой пример напоминает мне инструкцию на языке Си V[i]. Какое определение для junta ?

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

-junta является булевой функцией , которая зависит только от

аргументов, т.е. существует множество

размера

таким , что для любого

, если

отличаются только на позициях вне

тогда

. Я использовал этот термин как функцию, которая не зависит от всех аргументов.

k

$k$

k

$k$

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

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

k

$k$

x

$x$

y

$y$

x

$x$

y

$y$

A

$A$

f (x) = f (y)

$f(x)=f(y)$

sdcvvc

Если вы пытаетесь найти поддержку своего ответа на проблему среднего расстояния на math.se, к сожалению, это не сработает.

Арьябхата

@Aryabhata первым намерением было найти поддержку для моего ответа на этот вопрос: math.stackexchange.com/questions/129969/… , но единственное, что этот результат скажет, - если в графе есть

вершин, алгоритм Расчет среднего расстояния им будет

, что вполне очевидно. Я удалил свой ответ там, потому что, как вы написали, я ничего не доказал.

n

$n$

Ω (n)

$\Omega(n)$

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

Ответы:

Необходимо указать модель вычисления и свойства . В следующем аргументе я изложу предположения, которые мне нужны. Это можно обобщить немного дальше, но я думаю, что этого должно быть достаточно, чтобы дать вам идею. $f$

Предположим, что машина никогда не считывает значение одного из членов (фиксированный набор, и задается в виде списка). Предположим далее, что является входом таким, что изменение значения его го члена не меняет ответа Предположим далее, что чувствительна ко всем частям ввода, то есть зависит от самого члена (то есть можно изменить любой член на что-то другое, чтобы получить новое входное значение -го значения на и разные). $M$ $A$ $A$ $A$ $i$ $M$ $f$ $A$ $A$ $A'$ $f$ $A$ $A'$

Мы можем использовать аргумент противника, чтобы показать, что машина не может вычислить правильный ответ, изменив значение этого члена чтобы получить иначе значение будет другим. Значение в этих двух наборах одинаково, поэтому один из них должен быть ложным, и, следовательно, не может правильно вычислить . $A$ $A'$ $f$ $M$ $M$ $f$

Следовательно, любая машина которая вычисляет , должна будет прочитать все входные данные, которые выполняют шагов. $M$ $f$ $\Omega(n)$

(С другой стороны, предположим, что у нас есть недетерминированная машина произвольного доступа, и мы хотим вычислить ИЛИ битов на входе. Мы можем недетерминированно угадать бит и проверить, равен ли он 1, если он равен 1, мы выводим 1 . Эта машина читает только один бит ввода в шагов и правильно решает проблему. Таким образом, без предположений относительно и результат не выполняется.) $O(\lg n)$ $M$ $f$

Кава
источник

Извините, я забыл написать, что моя модель вычислений была детерминированной машиной Тьюринга.

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

+1 для аргумента противника, который является отличным способом начать понимать нижние границы.

Джо