ECCC-Report TR18-055https://eccc.weizmann.ac.il/report/2018/055Comments and Revisions published for TR18-055en-usThu, 21 Jun 2018 17:58:26 +0300
Revision 5
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055#revision5We 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.Thu, 21 Jun 2018 17:58:26 +0300https://eccc.weizmann.ac.il/report/2018/055#revision5
Revision 4
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055#revision4We 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.Fri, 04 May 2018 12:02:19 +0300https://eccc.weizmann.ac.il/report/2018/055#revision4
Revision 3
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055#revision3We 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.Wed, 18 Apr 2018 16:54:28 +0300https://eccc.weizmann.ac.il/report/2018/055#revision3
Revision 2
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055#revision2We 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.Thu, 12 Apr 2018 17:28:41 +0300https://eccc.weizmann.ac.il/report/2018/055#revision2
Revision 1
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055#revision1We 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.Mon, 26 Mar 2018 23:14:27 +0300https://eccc.weizmann.ac.il/report/2018/055#revision1
Paper TR18-055
| Balance Problems for Integer Circuits |
Titus Dose
https://eccc.weizmann.ac.il/report/2018/055We 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.Mon, 26 Mar 2018 14:08:50 +0300https://eccc.weizmann.ac.il/report/2018/055