11
$\begingroup$

While an EE undergrad I attended some lectures that presented a nice characterization of boolean circuits in terms of how many nested loops they have. In complexity, boolean circuits are often thought of as dags, but in real hardware cycles are common. Now, modulo some technicalities regarding what a loop is and what constitutes a nested loop, the claim was basically that in order to implement in hardware an automaton one needs two nested loops, and in order to implement a processor one needs three nested loops. (I might be off-by-one with these counts.)

Two things bother me:

  1. There was nothing like a formal proof.
  2. I didn't see this anywhere else.

Did anyone investigate precise statements of this kind?

Searching for the name of the professor I found a small webpage and book (Chapter 4) that discuss this taxonomy.

Sort of background: In case you wonder why are cycles useful at all in real hardware, here is a simple example. Connect two inverters in a cycle. (An inverter is a gate that computes the boolean function NOT.) This circuit has two stable equilibriums (and an unstable one). Absent any outside intervention, the circuit will simply stay in one of the two states. However, it is possible to force the circuit into one particular state by applying an external signal. The situation can be seen like this: While the cycle is connected to the outside signal "we read the input," and otherwise we simply "remember the last value we saw." So one loop helps us remember stuff.

Improve this question
$\endgroup$
2
  • $\begingroup$ Perhaps this is best seen as a way to structure the design of a large-scale digital circuit (just like it might be a good idea to use subroutines in a large-scale computer program), and not really as a formal lower bound? (Chapter 14 of the book that you linked has plenty of Theorems with Proofs, but they seem to assume that you follow certain principles in the design of the circuit?) $\endgroup$
    – Jukka Suomela
    Commented Sep 13, 2010 at 18:27
  • 1
    $\begingroup$ Jukka may be right. Take the example of a flip-flop (a one-loop system) versus a finite state machine (a two-loop system as usually implemented). Can't you inline the FSM's combinational transition logic (which has no loops) directly into the flip-flop's loop? Of course, a one-bit FSM isn't very interesting. It can only be constant or alternate every cycle. The latter is of course a T-flip-flop with the T terminal connected to a 1 wire. But the same idea works for a bank of flip-flops. $\endgroup$
    – Per Vognsen
    Commented Oct 12, 2010 at 5:25

1 Answer 1

Reset to default
5
$\begingroup$

You should have a look at PhD thesis (later published as a monograph) of Tomás Feder: Stable Networks and Product Graphs, where he studied the complexity of finding stable configurations of networks, which are exactly circuits with "loops" like you mentioned.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.