Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Integer Circuit:
TR00-012 | 14th February 2000
Ke Yang

Integer Circuit Evaluation is PSPACE-complete

In this paper, we address the problem of evaluating the
Integer Circuit (IC), or the $\{\cup, \times, +\}$-circuit over
the set of natural numbers. The problem is a natural extension
to the integer expression by Stockmeyer and Mayer, and is also studied
by Mckenzie, Vollmer and Wagner in ... more >>>

TR18-055 | 26th March 2018
Titus Dose

Balance Problems for Integer Circuits

Revisions: 5

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 ... more >>>

ISSN 1433-8092 | Imprint