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?

$\endgroup$
  • 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 '18 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 '18 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 '18 at 16:33

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.