文章基本信息

标题：On the Complexity of Quantified Integer Programming
本地全文：下载
作者：Dmitry Chistikov ; Christoph Haase
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：94:1-94:13
DOI：10.4230/LIPIcs.ICALP.2017.94
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Quantified integer programming is the problem of deciding assertions of the form Q_k x_k ... forall x_2 exists x_1 : A * x >= c where vectors of variables x_k,..,x_1 form the vector x, all variables are interpreted over N (alternatively, over Z), and A and c are a matrix and vector over Z of appropriate sizes. We show in this paper that quantified integer programming with alternation depth k is complete for the kth level of the polynomial hierarchy.
关键词：integer programming; semi-linear sets; Presburger arithmetic; quantifier elimination