论文标题
关于平价问题的细粒度复杂性
On the Fine-Grained Complexity of Parity Problems
论文作者
论文摘要
我们考虑在细粒度复杂性中研究的基本问题的奇偶校验变体。我们表明，对于许多经典问题，包括全对路径（APSP），直径，半径，中位数，第二最短路径，最大连续的子集团，最大连续卷，最小卷积，最小卷积和$ 0/1 $ -KKNAPACK。 通常很难设计出从问题到平等版本的直接减少。取而代之的是，我们重新审视现有的硬度降低，并以特定于问题的方式对其进行量身定制。文献中几乎所有来自APSP的降低都通过（亚地铁等效但更简单的）负重三角（NWT）问题进行。我们的新修改后的减少也从NWT或IT的非标准奇偶校验变体开始。我们无法建立NWT的更自然的奇偶校验计数变体的亚地铁等效性，在那里我们询问负三角形的数量是否甚至是奇数。也许令人惊讶的是，我们通过设计看似柔和的零重量三角问题的减少来证明这一点是合理的，这表明（有条件地）比NWT的决定要严格难得（有条件地）。
We consider the parity variants of basic problems studied in fine-grained complexity. We show that finding the exact solution is just as hard as finding its parity (i.e. if the solution is even or odd) for a large number of classical problems, including All-Pairs Shortest Paths (APSP), Diameter, Radius, Median, Second Shortest Path, Maximum Consecutive Subsums, Min-Plus Convolution, and $0/1$-Knapsack. A direct reduction from a problem to its parity version is often difficult to design. Instead, we revisit the existing hardness reductions and tailor them in a problem-specific way to the parity version. Nearly all reductions from APSP in the literature proceed via the (subcubic-equivalent but simpler) Negative Weight Triangle (NWT) problem. Our new modified reductions also start from NWT or a non-standard parity variant of it. We are not able to establish a subcubic-equivalence with the more natural parity counting variant of NWT, where we ask if the number of negative triangles is even or odd. Perhaps surprisingly, we justify this by designing a reduction from the seemingly-harder Zero Weight Triangle problem, showing that parity is (conditionally) strictly harder than decision for NWT.
