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?

  • 3
    $\begingroup$ this is not well defined. how do you represent an infinite circuit? what is the question for arithmetic circuits? $\endgroup$ Mar 6 '13 at 15:37
  • $\begingroup$ eg P/poly problems can be regarded as finite circuit instances of infinitely increasing (unbounded) size.... $\endgroup$
    – vzn
    Mar 6 '13 at 17:07
  • 1
    $\begingroup$ 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)? $\endgroup$
    – Shaull
    Mar 6 '13 at 20:29
  • 2
    $\begingroup$ This isn't directly related to SAT for such circuits, but you might find it interesting. Furst, Saxe, and Sipser (the FOCS version: 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. $\endgroup$ Apr 15 '13 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.