Computer Science 456/656
Automata and Formal Languages
One important question that arises in connection with parallel or distributed
computing is, given a certain problem that takes a certain amount of time,
can the work be partitioned amoung many processors (which are allowed to
communicate with each other) in such a way as to speed up the computation?
The real question is, which problems can be worked in O(log^k(n)) time
using polynomially many processors? For example, the minimum element in
an array of size n can be found in O(log n) time using n processors.
The class of all such problems is called
NC,
or
"Nick's Class",
named after
Nicholas Pippenger.
Can every problem in the class P be worked in polylogarithmic time with
polynomially many processors? This question is open.
It is trivial that NC is a subclass of P.
The Circuit Value Problem.
A Boolean circuit is defined to be a directed acyclic graph with seven kinds
of nodes:
-
Sources. Each source is either a 0-source or a 1-source, and has
in-degree 0 and out-degree 1.
-
Branches. Each branch has in-degree 1 and out-degree 2.
-
Not-gates. Each not-gate has in-degree 1 and out-degree 1.
-
And-gates. Each and-gate has in-degree 2 and out-degree 1.
-
Or-gates. Each or-gate has in-degree 2 and out-degree 1.
-
Sink. There is only one sink, which has in-degree 1 and out-degree 0.
We define a satisfying assignment of a Boolean circuit to be the assignment
of a truth value to each node, which is "consistent" at each node. The
definition of consistency at a node is as follows:
-
The value of a 0-source node is consistent if and only if it's "false."
-
The value of a 1-source node is consistent if and only if it's "true."
-
The value of a branch node is consistent if and only if it's the same as
the value of the predecessor node.
-
The value of a not-gate is consistent if and only if it's the opposite
of the value of the predecessor node.
-
The value of an and-gate is consistent if and only if it's the same as the
conjunction ("and") of the two predecessor nodes.
-
The value of an or-gate is consistent if and only if it's the same as the
disjunction ("or") of the two predecessor nodes.
-
The value of the sink node is consistent if and only if it's the same as
the value of the predecessor node.
A Boolean circuit can be encoded as a string. Fix an encoding scheme.
We then define CVP to be the language of encodings of
satisfiable Boolean circuits. It is easy to see that CVP
is in the class P, i.e., polynomial time.
But it is also an example of a
P-complete
problem, that is, if the circuit value problem in the class NC,
then P = NC. The importance question is of the same order of magnitude
as the importance of the better known question of whether P = NP.
Exercises:
-
Prove that every regular language is in NC.
Hint.
-
Write a parallel algorithm that uses n/log(n) processors to find the
maximum of n items in an array in O(log n) time.
-
Can you prove that every context-free language is in NC? Try to parallelize
the CYK algorithm.
-
Prove that the special version of CVP where not-gates are not allowed is NC.
-
Find a good definition of NC in terms of machines, in the same spirit as
the usual definition of NP in terms of NTMs. (Try the world-wide-web.)