<p>The question is on the title.</p>

<p>We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, <strong>is there any $k \ge 2$ and any $\text{NC}^k$-complete problem with respect to logspace reduction?</strong> For $k = 1$, Barrington's theorem already gives a logspace complete problem.</p>

<p>It seems that if $\text{NC}$ has a logspace complete problem, the $\text{NC}$ hierarchy collapses. So, the title question is open, but the other question still stands.</p>

<p>Edit: Fixed so that the original (title) question is OPEN, and there is one question left so far.</p>

CC BY-SA 4.0
2018-06-11T06:17:17.303Z
Do you mean uniform NC? Or more precise dlogtime- or logspace-uniform NC? In that case, you have that NC1 is included in logspace, so most NC1 problems will be trivially complete for logspace reductions. (Even for AC0 or dlogtime redurctions, uniform NC1 has complete problems, like the regular language $\bar{A_5}$ from Barrington's theorem, or the Boolean formula evaluation problem from Buss's breakthrough. SAC1 (=LogCFG) has complete problems too.) But for k >= 2, this might indeed be an interesting question, even if the answer should turn out to be trivial...
Thomas Klimpel
CC BY-SA 4.0
2018-06-11T07:38:18.473Z
@ThomasKlimpel Yeah I mean the normal definitions of NC classes: logspace-uniform. I get what you say, but how about the whole class NC? Does it collapse if it has a logspace-reduction complete problem?
Vincent J. Ruan
CC BY-SA 4.0
2018-06-11T07:57:41.457Z
Of course NC would collapse, if there is a NC complete problem, since that problem would belong to NC^k for some specific k. The interesting part of your question for me is about NC^k complete problem(s) for k >= 2. (Both since the answer for k=1 is well known, and because your notions would have to be modified for k=1 anyway.) I suggest that you edit your question to focus on the non-obvious parts. The obvious parts would be better addressed at cs.stackexchange.com in my opinion...
Thomas Klimpel
CC BY-SA 4.0
2018-06-11T08:18:57.557Z
*All* of the question would be better addressed at cs.stackexchange.com. Of course there are NC^k-complete problems for each $k\ge2$, and they are constructed in the most routine way imaginable: by taking a universal evaluator for machines defining the class. In this particular case, one can simply take an evaluator for $(\log n)^k$-depth constant Boolean circuits. (Make them monotone if you wish.)
Emil Jeřábek
CC BY-SA 4.0
2018-06-11T10:36:32.720Z
@ThomasKlimpel I will fix the question soon. But I think NC1-completeness is not trivial. It's because a logspace reduction in general can only be transformed into a $\log^2$-depth logspace-uniform circuit. Anyway, Barrington's theorem does give a NC1-complete problem.
Vincent J. Ruan
CC BY-SA 4.0
2018-06-11T10:37:55.590Z
@EmilJeřábek Can you elaborate more on that typical NCk-complete problem? I don't get it.
Vincent J. Ruan
CC BY-SA 4.0
2018-06-11T10:46:16.933Z
@EmilJeřábek You are probably right. The non-trivial part for me would be to show that the universal evaluator itself is inside the given class, i.e. that an evaluator for $(\log n)^k$-depth Boolean circuits is in NC^k.
Thomas Klimpel
CC BY-SA 4.0
2018-06-11T12:20:44.213Z
@ThomasKlimpel Hint: it’s easier to first construct an evaluator for circuits represented by their ecl (extended connection language). The modification to use a more conventional representation (dcl) is then straightforward (but fails for $\mathrm{NC}^1$). Also, this may be a matter of taste, but I find it easier to think about the evaluator as an alternating Turing machine working in $O(\log n)$ space and $O((\log n)^k)$ time (which is an equivalent definition of uniform $\mathrm{NC}^k$), rather than in terms of uniform sequences of circuits.
Emil Jeřábek
<cc.complexity-theory><complexity-classes><circuit-complexity><logspace>
Is there any NC-complete problem with respect to logspace reduction?
Vincent J. Ruan
# Is there any NC-complete problem with respect to logspace reduction?

(Asked by: username_0 on 2018-06-11)

The question is on the title.

We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, **is there any $k \ge 2$ and any $\text{NC}^k$-complete problem with respect to logspace reduction?** For $k = 1$, Barrington's theorem already gives a logspace complete problem.

It seems that if $\text{NC}$ has a logspace complete problem, the $\text{NC}$ hierarchy collapses. So, the title question is open, but the other question still stands.

Edit: Fixed so that the original (title) question is OPEN, and there is one question left so far.

**Tags:** cc.complexity-theory, complexity-classes, circuit-complexity, logspace

> **Comments:**
> **username_1**: Do you mean uniform NC? Or more precise dlogtime- or logspace-uniform NC? In that case, you have that NC1 is included in logspace, so most NC1 problems will be trivially complete for logspace reductions. (Even for AC0 or dlogtime redurctions, uniform NC1 has complete problems, like the regular language $\bar{A_5}$ from Barrington's theorem, or the Boolean formula evaluation problem from Buss's breakthrough. SAC1 (=LogCFG) has complete problems too.) But for k >= 2, this might indeed be an interesting question, even if the answer should turn out to be trivial...  
> **username_0**: @ThomasKlimpel Yeah I mean the normal definitions of NC classes: logspace-uniform. I get what you say, but how about the whole class NC? Does it collapse if it has a logspace-reduction complete problem?  
> **username_1**: Of course NC would collapse, if there is a NC complete problem, since that problem would belong to NC^k for some specific k. The interesting part of your question for me is about NC^k complete problem(s) for k >= 2. (Both since the answer for k=1 is well known, and because your notions would have to be modified for k=1 anyway.) I suggest that you edit your question to focus on the non-obvious parts. The obvious parts would be better addressed at cs.stackexchange.com in my opinion...  
> **username_2**: *All* of the question would be better addressed at cs.stackexchange.com. Of course there are NC^k-complete problems for each $k\ge2$, and they are constructed in the most routine way imaginable: by taking a universal evaluator for machines defining the class. In this particular case, one can simply take an evaluator for $(\log n)^k$-depth constant Boolean circuits. (Make them monotone if you wish.)  
> **username_0**: @ThomasKlimpel I will fix the question soon. But I think NC1-completeness is not trivial. It's because a logspace reduction in general can only be transformed into a $\log^2$-depth logspace-uniform circuit. Anyway, Barrington's theorem does give a NC1-complete problem.  
> **username_0**: @EmilJeřábek Can you elaborate more on that typical NCk-complete problem? I don't get it.  
> **username_1**: @EmilJeřábek You are probably right. The non-trivial part for me would be to show that the universal evaluator itself is inside the given class, i.e. that an evaluator for $(\log n)^k$-depth Boolean circuits is in NC^k.  
> **username_2**: @ThomasKlimpel Hint: it’s easier to first construct an evaluator for circuits represented by their ecl (extended connection language). The modification to use a more conventional representation (dcl) is then straightforward (but fails for $\mathrm{NC}^1$). Also, this may be a matter of taste, but I find it easier to think about the evaluator as an alternating Turing machine working in $O(\log n)$ space and $O((\log n)^k)$ time (which is an equivalent definition of uniform $\mathrm{NC}^k$), rather than in terms of uniform sequences of circuits.  

---

## 0 answers

