Complexité de la communication: jeu de tromperie à destination de la fonction du produit intérieur
-
05-11-2019 - |
Question
J'essaie de prouver que la méthode de l'ensemble de tromperie ne donne pas une bonne limite inférieure pour la complexité de communication de la fonction du produit interne. Plus précisément, j'essaie de montrer que le meilleur lien que nous obtenons en utilisant la méthode de l'ensemble de tromperie est $$ d (ip) geq omega ( log n) $$
$ D (ip) $ est la complexité de communication déterministe de la fonction du produit interne. Cela implique que tout ensemble de tromperie pour le produit intérieur ne peut pas avoir plus que $ n ^ 2 $ éléments. Comment montrer ceci? Je peux vérifier l'instruction pour des instances spécifiques, mais je n'ai aucune intuition pour la preuve.
Pas de solution correcte
Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange