Maybe an answer to this

Here input of length and position is binary rather than unary, so traditional "DLOGTIME-uniform" is now "O(n)-uniform". (If traditional "DLOGTIME-uniform" already take binary input then this question has false assumption)

Surely O(n) isn't that low, so will a lower model lead to weaker result? E.g. is uniformNC∩O(n)-uniform AC0 weaker than uniform AC0?

  • $\begingroup$ What exactly is your question? $\endgroup$ Dec 29, 2022 at 18:46
  • $\begingroup$ @EmilJeřábek will a lower model(e.g. uniformNC-uniform) lead to weaker result? $\endgroup$
    – l4m2
    Dec 30, 2022 at 1:58
  • $\begingroup$ What "result"?? $\endgroup$ Dec 30, 2022 at 8:28
  • $\begingroup$ Also, if you consider the input as indices written in binary, then DLOGTIME-uniformity becomes linear-time uniformity rather than polynomial-time uniformity. It is actually already defined that way; it is only called DLOGTIME-uniform in reference to the input size of the circuit being uniformized. $\endgroup$ Dec 30, 2022 at 8:33
  • $\begingroup$ @EmilJeřábek The ability it constructs circuit $\endgroup$
    – l4m2
    Dec 30, 2022 at 9:33


Your Answer

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

Browse other questions tagged or ask your own question.