Limites inférieures du calcul d'une fonction d'un ensemble

Ayant un ensemble de éléments, disons que je veux calculer une fonction qui est sensible à toutes les parties de l'entrée, c'est-à-dire qui dépend de chaque membre de (c'est-à-dire qu'il est possible de changer n'importe quel membre de en quelque chose sinon pour obtenir une nouvelle entrée st les valeurs de sur et sont différentes). $A$ $n$ $f(A)$ $A$ $A$ $A'$ $f$ $A$ $A'$

Par exemple, pourrait être la somme ou la moyenne. $f$

Y a-t-il un résultat qui prouve que, dans certaines conditions, le temps nécessaire à une machine de Turing déterministe pour calculer sera ? $f$ $\Omega(n)$

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

Notez que si

est une séquence à accès aléatoire et que l'hypothèse de sensibilité est affaiblie, cela ne se vérifie pas toujours. Par exemple,

peut être calculé avec deux requêtes, même s'il ne s'agit pas d'une junte.

A

$A$

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

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

sdcvvc

@sdcvvc votre exemple me rappelle l'instruction en langage C V[i]. Quelle est la définition de la junte ?

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

Une

junta est une fonction booléenne qui ne dépend que de

arguments, c'est-à-dire qu'il existe un ensemble

de taille

tel que pour tout

, si

ne diffèrent que sur les positions en dehors de

, alors

. J'ai abusé de ce terme pour désigner une fonction qui ne dépend pas de tous les arguments.

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

Si vous essayez de trouver un support pour votre réponse au problème de distance moyenne sur math.se, malheureusement, cela ne fonctionnera pas.

Aryabhata

@Aryabhata la première intention était de trouver un support pour ma réponse à cette question: math.stackexchange.com/questions/129969/… , mais la seule chose que ce résultat dira est que s'il y a

sommets dans le graphique, l'algorithme calculer la distance moyenne entre eux sera

, ce qui est assez évident. J'ai supprimé ma réponse parce que, comme vous l'avez écrit, je n'ai rien prouvé.

n

$n$

Ω (n)

$\Omega(n)$

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

Réponses:

Vous devez être spécifier le modèle de calcul et les propriétés de . Dans l'argument suivant, j'énoncerai les hypothèses dont j'ai besoin. Elle peut être généralisée un peu plus loin mais je pense qu'elle devrait suffire à vous donner l'idée. $f$

Supposons que la machine ne lit jamais la valeur de l'un des membres de (un ensemble fixe, et est donné sous forme de liste). On suppose en outre que est une entrée de telle sorte que la modification de la valeur de sa ième élément ne change pas réponse de. Supposons en outre que soit sensible à toutes les parties de l'entrée, c'est-à-dire qu'il dépend de chaque membre de (c'est-à-dire qu'il est possible de changer n'importe quel membre de en quelque chose d'autre pour obtenir une nouvelle entrée st valeur de sur et sont différents). $M$ $A$ $A$ $A$ $i$ $M$ $f$ $A$ $A$ $A'$ $f$ $A$ $A'$

On peut utiliser un argument adversaire pour montrer que la machine ne peut pas calculer la bonne réponse en changeant la valeur de ce membre de pour obtenir sinon st la valeur de est différente. La valeur de sur ces deux ensembles est la même, donc l'un d'eux doit être faux et donc ne peut pas calculer correctement. $A$ $A'$ $f$ $M$ $M$ $f$

Par conséquent, toute machine qui calcule devra lire l'intégralité de l'entrée qui prend des pas . $M$ $f$ $\Omega(n)$

(D'un autre côté, supposons que nous avons une machine à accès aléatoire non déterministe, et que nous voulons calculer OU des bits dans l'entrée. Nous pouvons deviner de manière non déterministe un bit et vérifier si c'est 1, s'il est 1, nous émettons 1 . Cette machine ne lit qu'un seul bit de l'entrée en étapes et répond correctement au problème. Donc, sans hypothèses sur et le résultat ne tient pas.) $O(\lg n)$ $M$ $f$

Kaveh
la source

Désolé d'avoir oublié d'écrire que mon modèle de calcul était la machine déterministe de Turing.

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

+1 pour l'argument de l'adversaire, ce qui est un excellent moyen de commencer à comprendre les limites inférieures.

Joe