Abstract
We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sink orientation (USO), and a variant of the α-Ham Sandwich problem. For all three settings, we show that “two choices are enough”, meaning that the general non-binary version of the problem can be reduced in polynomial time to the binary version. This specifically means that generalized P-LCPs are equivalent to P-LCPs, and grid USOs are equivalent to cube USOs. These results are obtained by showing that both the P-LCP and our α-Ham Sandwich variant are equivalent to a new problem we introduce, P-Lin-Bellman. This problem can be seen as a new tool for formulating problems as P-LCPs. Show more
Permanent link
https://doi.org/10.3929/ethz-b-000683853Publication status
publishedBook title
51st International Colloquium on Automata, Languages, and ProgrammingJournal / series
Leibniz International Proceedings in Informatics (LIPIcs)Volume
Pages / Article No.
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für InformatikEvent
Subject
P-LCP; Unique Sink Orientation; α-Ham Sandwich; search complexity; TFNP; UEOPLFunding
204320 - Unique Sink Orientations (SNF)
More
Show all metadata
ETH Bibliography
yes
Altmetrics