Springe direkt zu Inhalt

Michaela Borzechowski:

The Complexity Class Unique End of Potential Line


The complexity class Unique End of Potential Line (UniqueEOPL) was introduced in 2018 by Fearnley et al. and captures total search problems that are promised to have a unique solution. Therefore, the original promise version of each problem is transformed to a total search version. UniqueEOPL contains some interesting problems like P-LCP, Cube-USO and Arrival. It is an especially interesting class because it has a  ”natural” complete problem: One Permutation Discrete Contraction (OPDC).

The goal of this work is to give a comprehensive introduction to the complexity theory of search problems with a focus on the class UniqueEOPL. A list of all currently known problems in UniqueEOPL is presented and for each problem, a definition and examples are given. Some selected reductions are shown in full detail and with corrections.

The main contribution is the new containment result of Grid-USO in UniqueEOPL, which is proven via a reduction from Grid-USO to Unique Forward EOPL. From that result it also follows that P-GLCP is contained in UniqueEOPL too.

Master of Science (M.Sc.)
Homepage des Autors