首页    期刊浏览 2024年11月07日 星期四
登录注册

文章基本信息

  • 标题:The Complexity of Multi-source Variants of the End-of-Line Problem, and the Concise Mutilated Chessboard
  • 本地全文:下载
  • 作者:Alexandros Hollender ; Paul Goldberg
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2018
  • 卷号:2018
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    The 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.

  • 关键词:End of Line ; Mutilated Chessboard ; PPAD ; TFNP
国家哲学社会科学文献中心版权所有