ECCC-Report TR18-120https://eccc.weizmann.ac.il/report/2018/120Comments and Revisions published for TR18-120en-usSun, 24 Jun 2018 17:17:21 +0300
Paper TR18-120
| The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard |
Alexandros Hollender,
Paul Goldberg
https://eccc.weizmann.ac.il/report/2018/120The complexity class PPAD is usually defined in terms of the END-OF-LINE problem, in which we are given a concise representation of a large directed graph having indegree and outdegree at most 1, and a known source, and we seek some other degree-1 vertex. We show that variants where we are given multiple sources and seek one solution or multiple solutions are PPAD-complete. Our proof also shows that a multiple source SINK problem where we look for multiple sinks instead of one is equivalent to SINK (i.e. PPADS-complete). Using our result, we provide a full proof of PPAD-completeness of IMBALANCE. Finally, we use these results together with earlier work on the 2D-Brouwer problem to investigate the complexity of a new total search problem inspired by the mutilated chessboard tiling puzzle.Sun, 24 Jun 2018 17:17:21 +0300https://eccc.weizmann.ac.il/report/2018/120