Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
We show that for a randomly sampled unsatisfiable $O(\log n)$-CNF over $n$ variables the randomized two-party communication cost of finding a clause falsified by the given variable assignment is linear in $n$.
Artur Riazanov、Anastasia Sofronova、Dmitry Sokolov、Weiqiang Yuan
计算技术、计算机技术
Artur Riazanov,Anastasia Sofronova,Dmitry Sokolov,Weiqiang Yuan.Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication[EB/OL].(2025-07-16)[2025-08-16].https://arxiv.org/abs/2507.12124.点此复制
评论