论文标题
NP的单独和线性整数约束的决策程序
NP Decision Procedure for Monomial and Linear Integer Constraints
论文作者
论文摘要
通过功能符号的约束的满意度，我们考虑了非阴性整数的数值不平等。我们认为的约束是线性系统AX = B的连接，以及形式X_I> = x_j^n（x_i <= x_j^n）的（非）凸约约束的连词。我们表明，即使对线性部分的解决方案明确给出了这些约束的满足性，即使对线性部分的解决方案也是NP库。结果，我们获得了NP完整性，以扩展具有功能图像S = F [p^n]的基集（QFBAPA）的某些无量词约束。
Motivated by satisfiability of constraints with function symbols, we consider numerical inequalities on non-negative integers. The constraints we consider are a conjunction of a linear system Ax = b and a conjunction of (non-)convex constraints of the form x_i >= x_j^n (x_i <= x_j^n). We show that the satisfiability of these constraints is NP-complete even if the solution to the linear part is given explicitly. As a consequence, we obtain NP completeness for an extension of certain quantifier-free constraints on sets with cardinalities (QFBAPA) with function images S = f[P^n].
