文章基本信息

标题：The Complexity of Knapsack in Graph Groups
本地全文：下载
作者：Markus Lohrey ; Georg Zetzsche
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：66
页码：52:1-52:14
DOI：10.4230/LIPIcs.STACS.2017.52
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Myasnikov et al. have introduced the knapsack problem for arbitrary finitely generated groups. In LohreyZ16 the authors proved that for each graph group, the knapsack problem can be solved in NP. Here, we determine the exact complexity of the problem for every graph group. While the problem is TC^0-complete for complete graphs, it is LogCFL-complete for each (non-complete) transitive forest. For every remaining graph, the problem is NP-complete.
关键词：knapsack; subset sum; graph groups; decision problems in group theory