4
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ 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. :) $\endgroup$
    – Michael Wehar
    Jun 11, 2018 at 15:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – user2316602
    Jun 11, 2018 at 16:10
  • $\begingroup$ Very neat!! Thanks for sharing and I look forward to seeing if anyone has ever studied this before. :) $\endgroup$
    – Michael Wehar
    Jun 11, 2018 at 16:33

0

Reset to default

Your Answer

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