2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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... $\endgroup$
    – Thomas Klimpel
    Jun 11, 2018 at 6:17
  • $\begingroup$ @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? $\endgroup$
    – Vincent J. Ruan
    Jun 11, 2018 at 7:38
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Emil Jeřábek
    Jun 11, 2018 at 8:18
  • 1
    $\begingroup$ @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. $\endgroup$
    – Thomas Klimpel
    Jun 11, 2018 at 10:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Jun 11, 2018 at 12:20

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy