论文标题
可实现的能力有所不同：在USOS中进行汇总的复杂性差距
Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
论文作者
论文摘要
在HyperCube的唯一水槽方向（USO）中查找水槽的算法可用于解决许多代数和几何问题，最重要的是包括P-Matrix线性互补性问题和线性编程。可实现的USO是源于将这些问题减少到USO接收器问题的原因。因此，找到可实现的USOS的水槽在实际上是相关的，但是尚不清楚是否可以利用算法来更快地找到算法。但是，所有（非平凡的）已知无条件的下限用于接收器找到的界限都可以利用可见的USO，而USO是不可实现的。这表明在可实现的USOS上，陷入困境的问题确实更容易。 在本文中，我们表明，对于所有USOS的子类都是正确的。我们考虑Matoušek-type USOS的类，这是Matoušek的LP型问题转化为USOS语言。我们在所有人之间显示了汇合之间的查询复杂性差距，而仅在可实现的$ n $二维matoušek-type USOS中进行汇总。我们为两种情况提供具体的确定性算法和下限，并表明在可实现的情况下，$ O（log^2 n）$顶点评估查询就足够了，而通常需要$ n $ Queries。 Matoušek型USOS是第一个被发现承认这种差距的USO课程。
Algorithms for finding the sink in Unique Sink Orientations (USOs) of the hypercube can be used to solve many algebraic and geometric problems, most importantly including the P-Matrix Linear Complementarity Problem and Linear Programming. The realizable USOs are those that arise from the reductions of these problems to the USO sink-finding problem. Finding the sink of realizable USOs is thus highly practically relevant, yet it is unknown whether realizability can be exploited algorithmically to find the sink more quickly. However, all (non-trivial) known unconditional lower bounds for sink-finding make use of USOs that are provably not realizable. This indicates that the sink-finding problem might indeed be strictly easier on realizable USOs. In this paper we show that this is true for a subclass of all USOs. We consider the class of Matoušek-type USOs, which are a translation of Matoušek's LP-type problems into the language of USOs. We show a query complexity gap between sink-finding in all, and sink-finding in only the realizable $n$-dimensional Matoušek-type USOs. We provide concrete deterministic algorithms and lower bounds for both cases, and show that in the realizable case $O(log^2 n)$ vertex evaluation queries suffice, while in general exactly $n$ queries are needed. The Matoušek-type USOs are the first USO class found to admit such a gap.
