I am unable to see a clear explanation of how the classes NC and P/poly intersect or not. (and if they do intersect then how and where? and if not then what is the proof?)
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ I think the questions above and below the line are rather independent and should be asked as separate questions. I expect that there are people who have a good answer to one but no answer to the other. $\endgroup$– David RicherbyCommented Apr 13, 2015 at 19:25
-
$\begingroup$ The breadth objected to in the close vote seems to be as a result of the second, largely independent question. Since the second question is not addressed by the answer, I've deleted it. I think that deals with the breadth issue. $\endgroup$– David RicherbyCommented Jun 22, 2015 at 23:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
10
If you define NC as the class of problems computable using polynomial size, polylogarithmic depth circuits, then NC$\subseteq$P/poly, since P/poly is the class of problems computable using polynomial size circuits (without restrictions on the depth). Sometimes we also require the circuits to be uniform, and then we get the stronger conclusion uniform-NC$\subseteq$P. In both cases it is conjectured that the containments are strict.
In fact, since P-complete problems are complete with respect to very weak reductions, uniform-NC$\subsetneq$P if and only if a P-complete problem is not in NC. Wikipedia has a list of many P-complete problems.
answered Apr 13, 2015 at 19:33
-
$\begingroup$ Damn! I should have seen this! I was getting confused as to how to set the "advice" string while converting a NC circuit into P/poly. I guess you mean that one can set the advice string to anything arbitrary and it still works? And any thoughts about the second question? $\endgroup$– user6818Commented Apr 13, 2015 at 20:01
-
$\begingroup$ P/poly is the class of problems computable using polynomial size circuits. This is equivalent to the definition using polynomial advice. $\endgroup$ Commented Apr 13, 2015 at 20:14
-
$\begingroup$ Unfortunately I'm not an expert in cryptography, so it's probably best to follow David's advice and split your question in two. $\endgroup$ Commented Apr 13, 2015 at 20:15
-
$\begingroup$ You are effectively saying that the only difference between $NC$ and P/poly is that the later has the additional condition of having polylogarithmic depth circuits. Is it? $\endgroup$– user6818Commented Apr 15, 2015 at 20:31
-
$\begingroup$ Yes, this is exactly correct. $\endgroup$ Commented Apr 15, 2015 at 20:33