<p>Unlike the class <span class="math-container">$P$</span> or <span class="math-container">$NP$</span> the class <span class="math-container">$NC$</span> does not have any complete problems. To show a problem is in <span class="math-container">$NC$</span> one needs to marshal efforts to directly show the problem is in <span class="math-container">$NC$</span> since there are no complete problems.</p>
<p>What are some of the known techniques to show a problem is in <span class="math-container">$NC$</span>?</p>
<p>For example reducing to determinants is one way since there is an <span class="math-container">$NC$</span> algorithm for determinants. Every attempt to show perfect matching is in <span class="math-container">$NC$</span> is through a reduction to determinant by derandomizing isolation lemma.</p>

CC BY-SA 4.0
2020-11-13T09:35:36.450Z
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?
Christian Komusiewicz
CC BY-SA 4.0
2020-11-13T09:46:40.993Z
What problems take the place of determinants? It looks the techniques utilized are without systematic structure.
Turbo
CC BY-SA 4.0
2020-11-13T10:13:37.333Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-11-13T11:39:10.870Z
@EmilJeřábek I think you mean $NC^k$ right? Would a complete problem at every $k$ answer this https://cstheory.stackexchange.com/questions/36231/problems-in-nc-not-known-to-lie-in-nc2? I do not know of $NC^k$ complete problems at every $k$ and I checked the zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc (if there is a complete problem definition at every $k$ it answers my posting).
Turbo
CC BY-SA 4.0
2020-11-13T12:19:26.907Z
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.
Emil Jeřábek
CC BY-SA 4.0
2020-11-13T16:48:11.950Z
In the last sentence, I meant $k=1$, not $n=1$.
Emil Jeřábek
<cc.complexity-theory><reductions><big-list><dc.parallel-comp><proof-techniques>
Some examples of tools to demonstrate problem is in $NC$
Turbo
# Some examples of tools to demonstrate problem is in $NC$

(Asked by: username_0 on 2020-11-13)

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.

**Tags:** cc.complexity-theory, reductions, big-list, dc.parallel-comp, proof-techniques
> **Comments:**
> **username_1**: 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?  
> **username_0**: What problems take the place of determinants? It looks the techniques utilized are without systematic structure.  
> **username_2**: 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.  
> **username_0**: @EmilJeřábek I think you mean $NC^k$ right? Would a complete problem at every $k$ answer this https://cstheory.stackexchange.com/questions/36231/problems-in-nc-not-known-to-lie-in-nc2? I do not know of $NC^k$ complete problems at every $k$ and I checked the zoo https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#nc (if there is a complete problem definition at every $k$ it answers my posting).  
> **username_2**: 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.  
> **username_2**: In the last sentence, I meant $k=1$, not $n=1$.  

---

## 0 answers

