1
$\begingroup$

Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no complete problems.

What are some of the known techniques to show a problem is in $NC$?

For example reducing to determinants is one way since there is an $NC$ algorithm for determinants. Every attempt to show perfect matching is in $NC$ is through a reduction to determinant by derandomizing isolation lemma.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ I don't understand the comment about the lack of complete problems. To show containment in $NC$ isn't it sufficient to reduce to a problem in $NC$ using a suitable reduction? Isn't this what the example for determinants does? It seems the only difference is that without a complete problem, it may be that the problem at hand may not be reducible to any known $NC$-problems? $\endgroup$
    – Christian Komusiewicz
    Commented Nov 13, 2020 at 9:35
  • $\begingroup$ What problems take the place of determinants? It looks the techniques utilized are without systematic structure. $\endgroup$
    – Turbo
    Commented Nov 13, 2020 at 9:46
  • 1
    $\begingroup$ To add to what Christian Komusiewicz wrote, if you for some weird reason insist on reducing to a complete problem rather than just showing directly that the problem is in NC (which is the most common way for all kinds of classes like P, NP, PSPACE, EXP, ..., not just for NC), you can reduce it to an $\mathrm{NC}_k$-complete problem for some $k$. In any case, this question is too broad. $\endgroup$
    – Emil Jeřábek
    Commented Nov 13, 2020 at 10:13
  • 1
    $\begingroup$ Yes, of course, there are $\mathrm{NC}^k$-complete problems for every $k\ge1$. For $k\ge2$, you can take for example evaluation of (constant) Boolean circuits of depth $\le(\log n)^k$. For $n=1$, you can take evaluation of Boolean formulas. $\endgroup$
    – Emil Jeřábek
    Commented Nov 13, 2020 at 12:19
  • 1
    $\begingroup$ In the last sentence, I meant $k=1$, not $n=1$. $\endgroup$
    – Emil Jeřábek
    Commented Nov 13, 2020 at 16:48

0

Reset to default