<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2016-01-27T18:24:10.653Z
No need for equality, the fact that uniform NC1 is a subset of nonuniform NC1 suffices to show the problem is in nonuniform NC1.
Kaveh
CC BY-SA 3.0
2016-01-27T18:28:13.940Z
ps: please check our [help/on-topic]. This question seems more suitable for [cs.se].
Kaveh
CC BY-SA 3.0
2016-01-27T21:25:52.910Z
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.
Michaël Cadilhac
CC BY-SA 3.0
2016-01-27T22:29:06.853Z
@Kaveh Is stuff like ALogTime and DLogTime-uniform really suitable for beginners? I have to admit that after reading that question and thinking about it, I now fully share the confusion: "the word problem for regular languages" seems to be easy to separate from NP, but I have no idea how to separate ALogTime from NP (I don't even see how to separate it from PH). I understand that I have to specify a reduction before I can even talk about a complexity class associated with "the word problem for regular languages", but nonuniform AC⁰ reductions doesn't sound impressive, yet...
Thomas Klimpel
CC BY-SA 3.0
2016-01-27T23:28:52.327Z
@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 [cs.se].
Kaveh
CC BY-SA 3.0
2016-01-27T23:34:34.417Z
@Thomas, Or the sentence "But the latter is not known to equal NC1". It is pretty obvious that the uniform class is properly contained in the nonuniform class, so it is known that they are not. I am not sure what you mean by separating the word problem from NP, the problem is in NC1 which is inside NP. And obviously no one knows how to separate the class of problems reducible to the word problem under AC0 reductions from NP, which is equivalent to separating NC1 from NP.
Kaveh
CC BY-SA 3.0
2016-01-27T23:41:10.327Z
Sorry, it is obviously no research question. I did not know about this separation...
Veto
CC BY-SA 3.0
2016-01-27T23:52:24.830Z
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?
Veto
CC BY-SA 3.0
2016-01-28T03:00:03.590Z
It is not uncommon that people ask question on [cstheory.se] in place of [cs.se]. :) If you would like the question to be migrated to [cs.se] you can flag the question for moderator attention and they can migrate it for you.
Kaveh
<circuit-complexity><upper-bounds><complexity><uniformity>
Circuit complexity lower bounds and uniformity
Veto
# Circuit complexity lower bounds and uniformity

(Asked by: username_0 on 2016-01-27)

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.

**Tags:** circuit-complexity, upper-bounds, complexity, uniformity
> **Comments:**
> **username_1**: No need for equality, the fact that uniform NC1 is a subset of nonuniform NC1 suffices to show the problem is in nonuniform NC1.  
> **username_1**: ps: please check our [help/on-topic]. This question seems more suitable for [cs.se].  
> **username_2**: 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.  
> **username_3**: @Kaveh Is stuff like ALogTime and DLogTime-uniform really suitable for beginners? I have to admit that after reading that question and thinking about it, I now fully share the confusion: "the word problem for regular languages" seems to be easy to separate from NP, but I have no idea how to separate ALogTime from NP (I don't even see how to separate it from PH). I understand that I have to specify a reduction before I can even talk about a complexity class associated with "the word problem for regular languages", but nonuniform AC⁰ reductions doesn't sound impressive, yet...  
> **username_1**: @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 [cs.se].  
> **username_1**: @Thomas, Or the sentence "But the latter is not known to equal NC1". It is pretty obvious that the uniform class is properly contained in the nonuniform class, so it is known that they are not. I am not sure what you mean by separating the word problem from NP, the problem is in NC1 which is inside NP. And obviously no one knows how to separate the class of problems reducible to the word problem under AC0 reductions from NP, which is equivalent to separating NC1 from NP.  
> **username_0**: Sorry, it is obviously no research question. I did not know about this separation...  
> **username_0**: 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?  
> **username_1**: It is not uncommon that people ask question on [cstheory.se] in place of [cs.se]. :) If you would like the question to be migrated to [cs.se] you can flag the question for moderator attention and they can migrate it for you.  

---

## 0 answers

