Communication Complexity is NP-hard

Hirahara, Shuichi; Ilango, Rahul; Loff, Bruno

计算机科学 > 计算复杂性

arXiv:2507.10426 (cs)

[提交于 2025年7月14日 ]

标题：通信复杂性是NP难的

标题： Communication Complexity is NP-hard

Authors:Shuichi Hirahara, Rahul Ilango, Bruno Loff

摘要：在他首次定义通信复杂性的论文中，Yao 提出以下问题： \emph{计算$CC(f)$（给定函数$f$的两方通信复杂度）是否是NP完全的？} 当给定$f$的通信矩阵和一个数$k$时，判断$CC(f) \le k$的问题显然属于 NP。 Kushilevitz 和 Weinreb 已经证明该问题在密码学上是困难的。在这里我们证明它是 NP 难的。

摘要： In the paper where he first defined Communication Complexity, Yao asks: \emph{Is computing $CC(f)$ (the 2-way communication complexity of a given function $f$) NP-complete?} The problem of deciding whether $CC(f) \le k$, when given the communication matrix for $f$ and a number $k$, is easily seen to be in NP. Kushilevitz and Weinreb have shown that this problem is cryptographically hard. Here we show it is NP-hard.

主题：	计算复杂性 (cs.CC)
引用方式：	arXiv:2507.10426 [cs.CC]
	(或者 arXiv:2507.10426v1 [cs.CC] 对于此版本)
	https://doi.org/10.48550/arXiv.2507.10426

提交历史

来自： Bruno Loff [查看电子邮件]
[v1] 星期一， 2025 年 7 月 14 日 16:15:54 UTC (70 KB)

全文链接：

获取论文：

查看许可

当前浏览上下文:

cs.CC

新的 | 最近的 | 2025-07

切换浏览方式为:

参考文献与引用

导出 BibTeX 引用

计算机科学 > 计算复杂性

标题：通信复杂性是NP难的

标题： Communication Complexity is NP-hard

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

计算机科学 > 计算复杂性

标题： 通信复杂性是NP难的 显示英文标题

标题： Communication Complexity is NP-hard

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

与本文相关的代码，数据和媒体

演示

推荐器和搜索工具

arXivLabs：与社区合作伙伴的实验项目

标题：通信复杂性是NP难的