|
|
On the Complexity of Search Problems with a Unique Solution
Králová, Veronika ; Hubáček, Pavel (advisor) ; Brzuska, Christopher (referee) ; Bitansky, Nir (referee)
Meggido and Papadimitriou [Theor. Comput. Sci., 1991] introduced the class TFNP of search problems for which a solution always exists and is polynomially verifiable. In this thesis, we study the possibility of reducing different problems into problems in TFNP. The property which is in common for problems, for which we study the reducibility to TFNP, is that all instances of these problems have a unique solution (if there is any solution present). In the first part of this thesis, we study a problem called ARRIVAL, which was intro- duced by Dohrau, Gärtner, Kohler, Matoušek and Welzl [A Journey Through Discrete Mathemathics: A Tribute to Jiří Matoušek, 2017]. ARRIVAL is the following decisional problem: Given a graph in which a train is moving according to prescribed rules does the train arrive to a given vertex? We first improve the result of Dohrau et al. who showed that the problem is in NP ∩ coNP. We show that there exists a unique certificate for being in the language and, thus, prove that it lies in UP ∩ coUP. We also study the search version of the ARRIVAL problem, which asks for the tran- script of number of traversals for each edge. It was known that the search version lies in PLS, which was proven by Karthik C. S. [Inf. Process. Lett., 2017]. We improve this result by showing a reduction from...
|
guest ::
