|
|
On the Complexity of Search Problems with a Unique Solution
Králová, Veronika ; Hubáček, Pavel (vedoucí práce) ; Brzuska, Christopher (oponent) ; Bitansky, Nir (oponent)
Meggido a Papadimitriou [Theor. Comput. Sci., 1991] definovali třídu TFNP, která je tvořena vyhledávacími problémy, pro které řešení vždy existuje a lze je testovat v polynomiálním čase. V této práci studujeme, zdali lze různé problémy redukovat na problémy z TFNP. Problémy, jejichž redukovatelnost do TFNP studujeme, mají společnou vlastnost, že všechny jejich instance mají jednoznačné řešení (pokud nějaké řešení vůbec existuje). V první části této práce studujeme problém zvaný ARRIVAL, který se poprvé ob- jevil v článku Dohrau, Gärtner, Kohler, Matoušek a Welzl [A Journey Through Discrete Mathemathics: A tribute to Jiří Matoušek, 2017]. ARRIVAL je následující rozhodovací problém: Máme dán orientovaný graf, po kterém se pohybuje vláček podle předepsaných pravidel, a ptáme se, jestli vláček někdy dojede do předem určeného vrcholu. Prvně vylepšíme výsledek Dohrau a kol., kteří ukázali, že tento problém je v NP ∩ coNP. Ukážeme, že existuje jednoznačný certifikát pro náležení do jazyka a tedy dokážeme, že ARRIVAL je v UP ∩ coUP. Dále budeme studovat vyhledávací variantu problému ARRIVAL, při které máme určit kolikrát vláček projel po každé hraně grafu. Jak ukázal Karthik C. S. [Inf. Process. Lett., 2017], vyhledávací varianta ARRIVAL je ve třídě PLS. My tento výsledek vylepšíme a ukážeme redukci z problému...
|
host ::
RSS.