论文标题
网格的独特下沉方向是潜在线的独特末端
Unique Sink Orientations of Grids is in Unique End of Potential Line
论文作者
论文摘要
Fearnly等人在2018年引入了潜在线（UEOPL）及其承诺版本的独特末端（UEOPL）。 UEOPL捕获了搜索问题，其中有望具有独特的解决方案。 UEOPL捕获了这些承诺问题的总搜索版本。可以通过定义作为未实现承诺的简短证书返回的违规行为来总共解决的承诺问题。 Griduso是在带有独特的水槽方向的网格中找到水槽的问题。它是由Gärtner等人引入的。我们描述了从Griduso到Uniqueforwardeopl的承诺减少的承诺，这是一个UEOPL-完整问题。因此，我们表明Griduso在UEOPL中，其承诺版本在Pueopl中。
The complexity classes Unique End of Potential Line (UEOPL) and its promise version PUEOPL were introduced in 2018 by Fearnly et al. UEOPL captures search problems where the instances are promised to have a unique solution. UEOPL captures total search versions of these promise problems. The promise problems can be made total by defining violations that are returned as a short certificate of an unfulfilled promise. GridUSO is the problem of finding the sink in a grid with a unique sink orientation. It was introduced by Gärtner et al. We describe a promise preserving reduction from GridUSO to UniqueForwardEOPL, a UEOPL-complete problem. Thus, we show that GridUSO is in UEOPL and its promise version is in PUEOPL.
