3

Does the unbounded fan-in circuit model apply in "practical" settings? In other words, are there real-world realisable computers with unbounded fan-in gates?

As I understand, standard silicon ASICs are made of so-called cells where the number of input signals in the largest cells is small (e.g. never exceeds a fan-in of 100).

Randomblue
  • 319
  • 1
  • 5
  • 1
    If you are talking about things like the circuit class $\mathsf{AC}^0$, then I don't think the point of this class is to capture something about the real world. You can see it as a toy model in which to develop lower bound techniques. Also, $\mathsf{AC}^0$ lower bounds were originally motivated by oracle separation results in complexity theory. – Sasho Nikolov May 29 '19 at 23:29
  • 1
    AC0 can be seen also as boolean circuits of arbitrary depth but such as alternation between OR and AND is bounded on every input-to-output path.

    Alternation between gate is related somehow (but I don't know more actually) to powerconsumption and speed of stabilisation of circuits. So I would say that actually it could be intersting. In practice, I doubt any circuits designer use results from circuits complexity.

     – C.P. Jun 04 '19 at 17:50
  • Related question: https://cstheory.stackexchange.com/questions/3624/practical-consequences-of-parity-notin-ac0 – Hermann Gruber Oct 28 '19 at 19:21
  • @Sasho: consider turning your comment into an answer. – Hermann Gruber Oct 28 '19 at 19:22

2 Answers2

1

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .

Bjørn Kjos-Hanssen
  • 4,485
  • 2
  • 25
  • 40
0

The fan-in of any real-world classical gate is bounded by $B := 2^{2^{1000000}}$ because if you tried to store $B$-many distinct bits of information in the observable universe you would run out of space before you ran out of bits.

This does not mean that there cannot be practical uses for it, as there are plausibly real-world circuits that are well approximated by the unbounded model. This is not dissimilar to the fact that we talk about space as if it was structured like $\mathbb{R}$ in physics.

There are other ways that this model can be useful in applications as well. This answer raises the question

Is there a realistic quantum architecture which is effectively equivalent to the quantum circuit with unbounded fan-out?

and claims that the answer is yes. Here, even though the actual circuit cannot be built, something else that is computably equivalent can be. I'm not knowledgeable of quantum algorithms, but it seems obvious to me that there are plausible scenarios where you'd rather work with the circuit model than whatever the real-world model is.

Stella Biderman
  • 1,046
  • 6
  • 19