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.

Can every problem in the class P be worked in polylogarithmic time with
polynomially many processors?  This question is open.

The Circuit Value Problem.

A Boolean circuit is defined to be a directed acyclic graph with seven kinds
of nodes:

1.,2.  Sources.  Each source is either a 0-source or a 1-source, and has
    in-degree 0 and out-degree 1.
3.  Branches.  Each branch has in-degree 1 and out-degree 2.
4.  Not-gates.  Each not-gate has in-degree 1 and out-degree 1.
5.  And-gates.  Each and-gate has in-degree 2 and out-degree 1.
6.  Or-gates.  Each or-gate has in-degree 2 and out-degree 1.
7.  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 nodes is as follows:

1. The value of a 0-source node is consistent if and only if it's "false."
2. The value of a 1-source node is consistent if and only if it's "true."
3. The value of a branch node is consistent if and only if it's the same as
   the value of its predecessor node.
4. The value of an not-gate is consistent if and only if it's the opposite
   of the value of its predecessor node.
5. The value of an and-gate is consistent if and only if it's the same as the
   conjunction ("and") of its two predecessor nodes.
6. The value of an or-gate is consistent if and only if it's the same as the
   disjunction ("or") of its two predecessor nodes.
7. The value of the sink node is consistent if and only if it's the same as
   the value of its predecessor node.

A Boolean circuit can be encoded as a string.  Fix an encoding scheme.
We then define Bool-Circuit-Sat to be the language of encodings of
satisfiable Boolean circuits.  It is easy to see that Bool-Circuit-Sat
is in the class P, i.e., polynomial time.