Abstract(s)
Ce mémoire étudie le problème ancestral 1 de déterminer la puissance relative de l’intrication
préalable en complexité de la communication comparée à la communication quantique. L’idée
maîtresse du mémoire est d’opérer un rapprochement entre la complexité de la communication
et la théorie des jeux non-locaux. Spécifiquement, nous contemplons une variété de manières
de convertir des jeux non-locaux pour lesquels il est su que beaucoup d’intrication est requise
en problèmes de complexité de la communication. Ce faisant, nous obtenons les problèmes de
communications affichant les plus grands écarts connus à ce jour entre les deux modèles pour des
problèmes fonctionnels.
Ce mémoire étudie le problème ancestral 1 de déterminer la puissance relative de l’intrication
préalable en complexité de la communication comparée à la communication quantique. L’idée
maîtresse du mémoire est d’opérer un rapprochement entre la complexité de la communication
et la théorie des jeux non-locaux. Spécifiquement, nous contemplons une variété de manières
de convertir des jeux non-locaux pour lesquels il est su que beaucoup d’intrication est requise
en problèmes de complexité de la communication. Ce faisant, nous obtenons les problèmes de
communications affichant les plus grands écarts connus à ce jour entre les deux modèles pour des
problèmes fonctionnels.