标题： NP难性与基于ETH的通信复杂性近似无解性通过松弛交错性 显示英文标题

标题： NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing

摘要： 我们证明了在标准协议树模型中，计算布尔函数的确定性通信复杂度 D(f) 是 NP 难的，独立且同时回答了 Hirahara-Llango-Loff（arXiv:2507.10426）提出的问题，该问题最初由 Yao（1979）提出。 我们的归约建立并扩展了 Mackenzie 和 Saffidine（arXiv:2411.19003）引入的一套结构化的“交错”引理；这些引理可以作为黑箱在未来的下界构造中重复使用。 我们的归约产生的实例对于具有强结构特性的自相似构造具有最优协议，为设计展示布尔矩阵通信复杂度的 NP 难性的归约提供了一个灵活的框架。 这补充了 Hirahara、Ilango 和 Loff 的工作，他们通过不同的途径在相同模型中建立了 NP 难性；我们的分析还提供了可重复使用的结构保证，并支持关于不可近似性的进一步结果。 由于我们构造中的组件是自相似的，它们可以递归嵌入。 我们简要说明了这在指数时间假设下会产生一个无限制增长的加法不可近似差距。 此外，我们概述了一条在固定常数加法误差范围内近似 D(f) 的 NP 难性的路径。 基于 ETH 的不可近似性结果的详细内容将在未来版本中出现。 除了确定确定性通信复杂度本身的复杂度外，我们开发的模块化框架为更广泛的归约打开了大门，我们认为这将有助于解决通信复杂性中的其他长期悬而未决的问题。 显示英文摘要

摘要： We prove that computing the deterministic communication complexity D(f) of a Boolean function is NP-hard in the standard protocol-tree model, answering, independently and concurrently with Hirahara-Llango-Loff (arXiv:2507.10426), a question first posed by Yao (1979). Our reduction builds and expands on a suite of structural "interlacing" lemmas introduced by Mackenzie and Saffidine (arXiv:2411.19003); these lemmas can be reused as black boxes in future lower-bound constructions. The instances produced by our reduction admit optimal protocols for self-similar constructions with strong structural properties, giving a flexible framework for the design of reductions showing NP-hardness of deciding the communication complexity of a Boolean matrix. This complements the work by Hirahara, Ilango, and Loff, which establishes NP-hardness in the same model via a different route; our analysis additionally yields reusable structural guarantees and underpins further consequences concerning inapproximability. Because the gadgets in our construction are self-similar, they can be recursively embedded. We sketch how this yields, under the Exponential-Time Hypothesis, an additive inapproximability gap that grows without bound. Furthermore we outline a route toward NP-hardness of approximating D(f) within a fixed constant additive error. Full details of the ETH-based inapproximability results will appear in a future version. Beyond settling the complexity of deterministic communication complexity itself, the modular framework we develop opens the door to a wider class of reductions and, we believe, will prove useful in tackling other long-standing questions in communication complexity.