Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities.
Linear integer programming is $\mathsf{NP}$ complete since $\mathsf{SAT}$ reduces to it.
Would there be programming constructs that with 'decidable portions of Skolem' leads to $\mathsf{NP}$ completeness?
My background is not logic and not sure if I make sense however if there is reasonable way to salvage the post it will be nice.
I am trying to see if linear integer programming that is $\mathsf{NP}$ complete has an analogy in Skolem arithmetic where variable addition is disallowed?
$\exists z_1,\dots,z_n\in\mathbb Z: Ax\leq b$ where $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ should be translatable to
$$\Big(\prod_{i=1}^nz_i^{a_{i1}}|p_1^b\Big)\wedge\dots\wedge\Big(\prod_{i=1}^nz_i^{a_{im}}|p_m^b\Big)$$
where $p_j$ are primes according to What are the definable sets in Skolem arithmetic? but $p_j$ are primes and so I am making a mistake.
