<p>The usual circuit complexity concerns circuits where circuit $C_n$ computes function $f_n$. I am interested in circuits such that $C_n$ can compute $f_i$ for all $i \leq n$. I am assuming that the first $\log n$ inputs specify the $i$.</p>

<p>Is anything known about this?</p>

CC BY-SA 4.0
2018-06-11T15:56:04.480Z
I haven't heard of this, but I think it's a really neat concept.  I think that circuit complexity with your notion should be polynomially equivalent to the more standard notion of circuit complexity.  I'm guessing that the polynomial should be quadratic, but maybe it can be improved.  Please correct me if I'm wrong.  :)
Michael Wehar
CC BY-SA 4.0
2018-06-11T16:10:17.060Z
I believe so. At the same time, I do not think there is a general construction with better polynomial, since the functions may be completely different for different $n$'s. Not sure about uniform circuit classes, though. Perhaps there is better polynomial for them?
user2316602
CC BY-SA 4.0
2018-06-11T16:33:03.873Z
Very neat!!  Thanks for sharing and I look forward to seeing if anyone has ever studied this before.  :)
Michael Wehar
<cc.complexity-theory><circuit-complexity><circuits>
Circuits computing functions of inputs smaller than $n$
user2316602
# Circuits computing functions of inputs smaller than $n$

(Asked by: username_0 on 2018-06-11)

The usual circuit complexity concerns circuits where circuit $C\_n$ computes function $f\_n$. I am interested in circuits such that $C\_n$ can compute $f\_i$ for all $i \leq n$. I am assuming that the first $\log n$ inputs specify the $i$.

Is anything known about this?

**Tags:** cc.complexity-theory, circuit-complexity, circuits

> **Comments:**
> **username_1**: I haven't heard of this, but I think it's a really neat concept.  I think that circuit complexity with your notion should be polynomially equivalent to the more standard notion of circuit complexity.  I'm guessing that the polynomial should be quadratic, but maybe it can be improved.  Please correct me if I'm wrong.  :)  
> **username_0**: I believe so. At the same time, I do not think there is a general construction with better polynomial, since the functions may be completely different for different $n$'s. Not sure about uniform circuit classes, though. Perhaps there is better polynomial for them?  
> **username_1**: Very neat!!  Thanks for sharing and I look forward to seeing if anyone has ever studied this before.  :)  

---

## 0 answers

