N C and P-Completeness

Many of the problems that you are familiar with are in the class N C. For example, the 0/1 version of the shortest path problem is in N C, and every context-free language is in the class N C.

Whether N C = P is an open question of enormous importance.

The Circuit Value Problem, or the Boolean Circuit Problem

We now give a P-complete problem, namely the circuit value problem.

An instance of the Circuit Value Problem is a sequence of n Boolean assignments.

1. The left side of the i^{th} assignment is the Boolean variable x_{i}.

2. The right side of the i^{th} assignment is one of the following.

(a) 0 (false)

(b) 1 (true)

(c) x_{j} for j < i

(d) ! x_{j} for j < i (! means ‘not’)

(e) x_{j} + x_{k} for j < i and k < i (+ means ‘or’)

(f) x_{j} ∗ x_{k} for j < i and k < i (∗ means ‘and’)

3. The answer to an instance of the CVP is the value of x_{n}.

Trivially, CVP is in P. Simply execute the n statements in order. It is known that CVP is P-complete, which implies that if it is in Nick’s Class, then

N C = P.

Problems

1. Given an alphabet Σ, an instance of the symbol find problem over Σ consists of a string w over Σ together with a single symbol x ∈ Σ. The instance is true if and only if some symbol of the string w is equal to x. Prove that the symbol find problem over Σ is in Nick’s Class.

2. Prove that every regular language is in Nick’s Class.

3. Using the fact that CVP is P-complete, prove that the programming language C++ is P-complete.