We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the balance problem for $\{-,\cdot\}$-circuits is undecidable which

is the first natural problem for integer circuits or related constraint satisfaction problems

that admits only one arithmetic operation and is proven to be undeciable.

Starting from this result we precisely characterize the complexity of balance problems

for proper subsets of $\{-,\cdot\}$. These problems turn out to be complete for one of the classes

L, NL, and NP. The case where only the multiplication is allowed turns out to be particular

interesting as it leads us to the general non-trivial observation that the product $S$ of two sets with sufficiently large maxima

is subbalanced (i.e., $|S| \le \max(S)/2$), which might be interesting on its own.

The proof of Theorem 18 was rewritten.

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the balance problem for $\{-,\cdot\}$-circuits is undecidable which

is the first natural problem for integer circuits or related constraint satisfaction problems

that admits only one arithmetic operation and is proven to be undeciable.

Starting from this result we precisely characterize the complexity of balance problems

for proper subsets of $\{-,\cdot\}$. These problems turn out to be complete for one of the classes

L, NL, and NP. The case where only the multiplication is allowed turns out to be particular

interesting as it leads us to the general non-trivial observation that the product $S$ of two sets with sufficiently large maxima

is subbalanced (i.e., $|S| \le \max(S)/2$), which might be interesting on its own.

Minor improvements have been made.

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits computing finite sets of natural numbers. These problems naturally build on problems for integer expressions and integer circuits studied by Stockmeyer and Meyer (1973), McKenzie and Wagner (2007), and Glaßer et al (2010).

Our work shows that the balance problem for $\{-,\cdot\}$-circuits is undecidable which is the first natural problem for integer circuits or related constraint satisfaction problems that admits only one arithmetic operation and is proven to be undeciable.

Starting from this result we precisely characterize the complexity of balance problems for proper subsets of $\{-,\cdot\}$. These problems turn out to be complete for one of the classes L, NL, and NP. The case where only the multiplication is allowed turns out to be particular interesting as it leads us to the general non-trivial observation that the product $S$ of two sets with sufficiently large maxima is subbalanced (i.e., $|S| \le \max(S)/2$), which might be interesting on its own.

formatting of the abstract has been improved

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

is the first natural problem for integer circuits or related constraint satisfaction problems

that admits only one arithmetic operation and is proven to be undeciable.

for proper subsets of $\{-,\cdot\}$. These problems turn out to be complete for one of the classes

L, NL, and NP. The case where only the multiplication is allowed turns out to be particular

interesting as it leads us to the general non-trivial observation that the product $S$ of two sets with sufficiently large maxima

is subbalanced (i.e., $|S| \le \max(S)/2$), which might be interesting on its own.