I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.

For example, the word problem for regular languages is known to be $NC^1$-complete under $AC^0$-reductions and in ALogTime, which equals DLogTime-uniform $NC^1$. But the latter is not known to equal $NC^1$. Maybe I am misunderstanding something about the $AC^0$-reduction, but I would not think that it is powerful enough to "handle" the non-uniformity? This would be the only explanation I can come up with.

  • $\begingroup$ No need for equality, the fact that uniform NC1 is a subset of nonuniform NC1 suffices to show the problem is in nonuniform NC1. $\endgroup$
    – Kaveh
    Jan 27 '16 at 18:24
  • 2
    $\begingroup$ ps: please check our help center. This question seems more suitable for Computer Science. $\endgroup$
    – Kaveh
    Jan 27 '16 at 18:28
  • 3
    $\begingroup$ The reduction has basically the same uniformity as the class it shows completeness for. The regular languages are complete for nonuniform NC¹ under nonuniform AC⁰ reductions, and for DLOGTIME-u. NC¹ under DLOGTIME-u.AC⁰ reductions. $\endgroup$ Jan 27 '16 at 21:25
  • 1
    $\begingroup$ @Thomas, maybe I am missing or confusing something. For completeness one needs universality (aka hardness) not lower bounds. Lower bounds are not used to show completeness. It is a basic confusion arsing from using the word "hardness". We use uniform version to give an upper bound on a problem, and that implies the problem is also in the nonuniform version of the class because the nonuniform version contains the uniform version, we don't need an equality. So when I read the rest of the question in the view of the first sentence it seems like a basic confusion and more suitable for Computer Science. $\endgroup$
    – Kaveh
    Jan 27 '16 at 23:28
  • 1
    $\begingroup$ The sentence about the equality of nonuniform and uniform NC1 is really stupid. But the hint that the hardness w.r.t. a nonuniform or uniform class depends on the kind of reduction helped a lot! I never read about (non)uniform reductions before, but that makes sense. So I can choose one of the two, nonuniform or uniform NC1, with the corresponding reduction, which together with the ALogTime upper bound then gives me the corresponding completeness? $\endgroup$
    – Veto
    Jan 27 '16 at 23:52

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.