HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is the relation between NC and P/poly?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thewhatbetweenpolyandrelation

Problem

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?)

Solution

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.

Context

StackExchange Computer Science Q#41344, answer score: 8

Revisions (0)

No revisions yet.