Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #5 to TR18-055 | 21st June 2018 17:58

Balance Problems for Integer Circuits

RSS-Feed




Revision #5
Authors: Titus Dose
Accepted on: 21st June 2018 17:58
Downloads: 34
Keywords: 


Abstract:

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.



Changes to previous version:

The former Theorem 12 whose proof contained ca 8 pages can also be obtained quite directly from the literature. Therefore, the former proof was replaced with a much shorter one.


Revision #4 to TR18-055 | 4th May 2018 12:02

Balance Problems for Integer Circuits





Revision #4
Authors: Titus Dose
Accepted on: 4th May 2018 12:02
Downloads: 70
Keywords: 


Abstract:

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.


Revision #3 to TR18-055 | 18th April 2018 16:54

Balance Problems for Integer Circuits





Revision #3
Authors: Titus Dose
Accepted on: 18th April 2018 16:54
Downloads: 53
Keywords: 


Abstract:

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.



Changes to previous version:

The proof of Theorem 18 was rewritten.


Revision #2 to TR18-055 | 12th April 2018 17:28

Balance Problems for Integer Circuits





Revision #2
Authors: Titus Dose
Accepted on: 12th April 2018 17:28
Downloads: 52
Keywords: 


Abstract:

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.



Changes to previous version:

Minor improvements have been made.


Revision #1 to TR18-055 | 26th March 2018 23:14

Balance Problems for Integer Circuits





Revision #1
Authors: Titus Dose
Accepted on: 26th March 2018 23:14
Downloads: 68
Keywords: 


Abstract:

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.



Changes to previous version:

formatting of the abstract has been improved


Paper:

TR18-055 | 26th March 2018 13:58

Balance Problems for Integer Circuits





TR18-055
Authors: Titus Dose
Publication: 26th March 2018 14:08
Downloads: 104
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint