Limites inferiores do cálculo de uma função de um conjunto

Tendo um conjunto de elementos, digamos que eu quero calcular uma função que é sensível a todas as partes da entrada, ou seja, depende de muito membro de (ou seja, é possível alterar qualquer membro de para algo mais para obter uma nova entrada st valor de em e são diferentes). $A$ $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Por exemplo, pode ser a soma ou a média. $f$

Existe um resultado que prove que, sob algumas condições, o tempo necessário para uma máquina de Turing determinística para calcular será ? $f$ $\Omega(n)$

complexity-theory Виталий Олегович
fonte

Observe que se é uma sequência com acesso aleatório e a suposição de sensibilidade é enfraquecida, isso nem sempre é válido. Por exemplo, podem ser computados com duas consultas, mesmo que não seja uma junta.

A

$A$

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

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

Sdcvvc 10/04/12

@sdcvvc seu exemplo me lembra o ensino da língua C V[i]. Qual é a definição de junta ?

214128 #

Um -junta é uma função booleana que depende apenas de argumentos, isto é, existe um conjunto de tamanho tal que para qualquer , , se e diferem apenas nas posições fora de , então . Eu abusei desse termo para significar uma função que não depende de todos os argumentos.

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

Se você está tentando encontrar suporte para sua resposta ao problema da distância média no math.se, infelizmente isso não serve.

Aryabhata

@Aryabhata, a primeira intenção foi encontrar suporte para minha resposta a esta pergunta: math.stackexchange.com/questions/129969/… , mas a única coisa que esse resultado dirá é que, se houver

vértices no gráfico, o algoritmo calcular a distância média entre eles será

, o que é bastante óbvio. Eu apaguei minha resposta lá, porque, como você escreveu, não provei nada.

n

$n$

Ω (n)

$\Omega(n)$

214126 #

Respostas:

Você deve especificar o modelo de computação e as propriedades de . No argumento a seguir, declararei as suposições necessárias. Pode ser generalizado um pouco mais, mas acho que deve ser suficiente para lhe dar a ideia. $f$

Suponha que a máquina nunca leia o valor de um dos membros de (um conjunto fixo e é fornecido como uma lista). Suponha ainda que é uma entrada tal que alterar o valor de seu membro não altera a resposta de Suponha ainda que é sensível a todas as partes da entrada, ou seja, depende de muito membro de (ou seja, é possível alterar qualquer membro de para outra coisa para obter uma nova entrada st valor de em e são diferentes). $M$ $A$ $A$ $A$ $i$ $M$ $f$ $A$ $A$ $A'$ $f$ $A$ $A'$

Podemos usar um argumento adversário para mostrar que a máquina não pode calcular a resposta correta alterando o valor desse membro de para obter contrário o valor de é diferente. O valor de nesses dois conjuntos é o mesmo; portanto, um deles deve ser falso e, portanto, não pode calcular corretamente. $A$ $A'$ $f$ $M$ $M$ $f$

Portanto, qualquer máquina que calcule precisará ler todas as entradas que executam etapas. $M$ $f$ $\Omega(n)$

(Por outro lado, suponha que tenhamos uma máquina de acesso aleatório não determinístico e que queremos calcular OU dos bits na entrada. Podemos adivinhar um pouco não-deterministicamente e verificar se esse é 1, se é 1, produzimos 1 Esta máquina lê apenas um único bit da entrada nas etapas e responde corretamente ao problema. Portanto, sem suposições sobre e o resultado não é válido.) $O(\lg n)$ $M$ $f$

Kaveh
fonte

Desculpe, esqueci de escrever que meu modelo de computação era a máquina determinística de Turing.

214126 #

+1 no argumento do adversário, que é uma ótima maneira de começar a entender os limites inferiores.

31412 Joe