2026-07-19T18:20:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20175 2024-07-02T08:09:56Z ddc:004 open_access

Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents Borzechowski, Michaela Fearnley, John Gordon, Spencer Savani, Rahul Schnider, Patrick Weber, Simon P-LCP Unique Sink Orientation α-Ham Sandwich search complexity TFNP UEOPL 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michaela Borzechowski and John Fearnley and Spencer Gordon and Rahul Savani and Patrick Schnider and Simon Weber 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.32 urn:nbn:de:0030-drops-201751 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.32 eng https://creativecommons.org/licenses/by/4.0/legalcode