确定性通信复杂度的NP困难性与加性不可近似性
NP-Hardness and Additive Inapproximability of Deterministic Communication Complexity
Serge Gaspers, Tao Zixu He, Simon Mackenzie
AI 速览：作者报告：给定布尔函数完整真值表，确定两方计算该函数所需最小最坏情况通信比特数是NP困难的，且在任何固定加性误差下不可近似。
Given the full truth table of a Boolean function whose input is split between two players, we study the complexity of determining the minimum worst-case number of bits they must communicate to compute it. This is a basic meta-complexity question, posed by Yao in 1979. We prove NP-hardness of approximation within every fixed additive error for deterministic communication complexity, under deterministic polynomial-time reductions. The result holds both in the standard model and in Yao's original model, where the players alternate after every bit and only the receiver of the last bit must determine the answer. In particular, it resolves the exact computation question under Yao's original conventions. Earlier versions of this same paper established exact NP-hardness for the standard model, independently and concurrently with Hirahara, Ilango, and Loff. In both models, a polynomial-time estimator with any fixed additive error would yield a polynomial-time $3$-SAT algorithm, deterministic or bounded-error randomized according to the estimator. For the standard model, we also give quantitative implications for errors that grow with the number $T$ of table entries. A bounded-error randomized polynomial-time estimator with additive error $c\log T/\log\log T$, for any fixed $0\le c<1/8$, yields a bounded-error randomized $3$-SAT algorithm on $N$ variables and $O(N)$ clauses running in time $2^{O(N^α)}$ for every fixed $8c<α<1$. A deterministic polynomial-time estimator with additive error $c_*\log\log T$, for an effective absolute constant $c_*>0$, yields a deterministic algorithm running in time $2^{O((\log N)^2)}$ on such formulas.