Adventures in Monotone Complexity and TFNP
Adventures in Monotone Complexity and TFNP
复制标题
DOI：
10.4230/lipics.itcs.2019.38
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Mika Göös;Pritish Kamath;Robert Robere;Dmitry Sokolov
中科院分区：
文献类型：
--
作者：
Mika Göös;Pritish Kamath;Robert Robere;Dmitry Sokolov
分离：我们引入了XOR-SAT的单调变体，并表明其具有指数单调电路的复杂性。由于XOR-SAT在NC^2中，因此在Tardos（1988）的单调与非单调的分离上，这在质量上有所改善。我们还表明，r上的单调跨度程序比有限字段更强大。这些结果可以解释为在通信复杂性中分离TFNP的子类。表征：我们表明，PPA的通信（分别查询）类似物（TFNP的子类）捕获了跨越f_2的程序（f_2上的nullstellensatz学位）。以前，众所周知，沟通FP捕获了公式（Karchmer -Wigderson，1988），并且Communication pls Pls捕获了电路（Razborov，1995年）。
Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite fields. These results can be interpreted as separating subclasses of TFNP in communication complexity. Characterizations: We show that the communication (resp. query) analogue of PPA (subclass of TFNP) captures span programs over F_2 (resp. Nullstellensatz degree over F_2). Previously, it was known that communication FP captures formulas (Karchmer - Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).