<p>As we all know, satisfiability of Boolean circuits is NP-complete.</p>

<p>I am wondering if there are any studies of circuits with infinite inputs?
That is, suppose the input is from the set $\{0,1\}^\omega$ (countable sequences of $0,1$). </p>

<p>Another model I am interested in is arithmetic circuits, specifically with the gates $\min\{x,y\},1-x$, and $\frac12 x+\frac12 y$, with inputs in $[0,1]^\omega$.</p>

<p>The first observation is that if the circuits are finite with bounded fan-in, then this is equivalent to the model with finite inputs. So we must consider infinite circuits, or at least infinite fan-in.</p>

<p>Clearly, the satisfiability problem in general will be undecidable, since we can encode the behavior of a TM with an infinite circuit.</p>

<p>However, there are circuit classes for which the problem is interesting. For example, we can require our gates to represent the temporal operators of $LTL$ (where we have a finite depth circuit with infinite fan-in), which makes the satisfiability problem PSPACE complete </p>

<p>Are there other known models with interesting results?</p>

CC BY-SA 3.0
2013-03-06T15:37:06.847Z
this is not well defined. how do you represent an infinite circuit? what is the question for arithmetic circuits?
Sasho Nikolov
CC BY-SA 3.0
2013-03-06T17:07:27.013Z
eg P/poly problems can be regarded as finite circuit instances of infinitely increasing (unbounded) size....
vzn
CC BY-SA 3.0
2013-03-06T20:29:45.840Z
Indeed, this is not a well-defined question. I am interested in any model that takes as input infinitely many bits/numbers, for which the satisfiability problem is decidable. Clearly this requires some restrictions on the gates (e.g. only allow LTL operators). I am after references here. If there aren't any - why? are there results that suggest that any model over infinite inputs is "uninteresting" (according to some measure)?
Shaull
CC BY-SA 3.0
2013-04-15T01:13:16.070Z
This isn't directly related to SAT for such circuits, but you might find it interesting. Furst, Saxe, and Sipser (the FOCS version: http://dx.doi.org/10.1109/SFCS.1981.35) gave a measurability-based argument that infinite constant-depth circuits cannot compute any infinite parity function (the latter is any function of countably many boolean inputs such that changing any one input changes the output of the function). This argument is significantly simpler than the random restriction arguments for finite AC^0 circuits. They don't restrict how the circuits are described, though.
Joshua Grochow
<cc.complexity-theory><circuit-families><arithmetic-circuits><temporal-logic>
Satisfiability of circuits with infinite input
Shaull
# Satisfiability of circuits with infinite input

(Asked by: username_0 on 2013-03-06)

As we all know, satisfiability of Boolean circuits is NP-complete.

I am wondering if there are any studies of circuits with infinite inputs?
That is, suppose the input is from the set $\{0,1\}^\omega$ (countable sequences of $0,1$).

Another model I am interested in is arithmetic circuits, specifically with the gates $\min\{x,y\},1-x$, and $\frac12 x+\frac12 y$, with inputs in $[0,1]^\omega$.

The first observation is that if the circuits are finite with bounded fan-in, then this is equivalent to the model with finite inputs. So we must consider infinite circuits, or at least infinite fan-in.

Clearly, the satisfiability problem in general will be undecidable, since we can encode the behavior of a TM with an infinite circuit.

However, there are circuit classes for which the problem is interesting. For example, we can require our gates to represent the temporal operators of $LTL$ (where we have a finite depth circuit with infinite fan-in), which makes the satisfiability problem PSPACE complete

Are there other known models with interesting results?

**Tags:** cc.complexity-theory, circuit-families, arithmetic-circuits, temporal-logic

> **Comments:**
> **username_1**: this is not well defined. how do you represent an infinite circuit? what is the question for arithmetic circuits?  
> **username_2**: eg P/poly problems can be regarded as finite circuit instances of infinitely increasing (unbounded) size....  
> **username_0**: Indeed, this is not a well-defined question. I am interested in any model that takes as input infinitely many bits/numbers, for which the satisfiability problem is decidable. Clearly this requires some restrictions on the gates (e.g. only allow LTL operators). I am after references here. If there aren't any - why? are there results that suggest that any model over infinite inputs is "uninteresting" (according to some measure)?  
> **username_3**: This isn't directly related to SAT for such circuits, but you might find it interesting. Furst, Saxe, and Sipser (the FOCS version: http://dx.doi.org/10.1109/SFCS.1981.35) gave a measurability-based argument that infinite constant-depth circuits cannot compute any infinite parity function (the latter is any function of countably many boolean inputs such that changing any one input changes the output of the function). This argument is significantly simpler than the random restriction arguments for finite AC^0 circuits. They don't restrict how the circuits are described, though.  

---

## 0 answers

