P-complete - P-complete Problems

P-complete Problems

The most basic P-complete problem is this: given a Turing machine, an input for that machine, and a number T (written in unary), does that machine halt on that input within the first T steps? It is clear that this problem is P-complete: if we can parallelize a general simulation of a sequential computer, then we will be able to parallelize any program that runs on that computer. If this problem is in NC, then so is every other problem in P. If the number of steps is written in binary, the problem is EXPTIME-complete.

This problem illustrates a common trick in the theory of P-completeness. We aren't really interested in whether a problem can be solved quickly on a parallel machine. We're just interested in whether a parallel machine solves it much more quickly than a sequential machine. Therefore, we have to reword the problem so that the sequential version is in P. That is why this problem required T to be written in unary. If a number T is written as a binary number (a string of n ones and zeros, where n = log T), then the obvious sequential algorithm can take time 2n. On the other hand, if T is written as a unary number (a string of n ones, where n = T), then it only takes time n. By writing T in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time. That puts the sequential problem in P. Then, it will be in NC if and only if it is parallelizable.

Many other problems have been proved to be P-complete, and therefore are widely believed to be inherently sequential. These include the following problems, either as given, or in a decision-problem form:

• Circuit Value Problem (CVP) - Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate
• Restricted Case of CVP - Like CVP, except each gate has two inputs and two outputs (F and Not F), every other layer is just AND gates, the rest are OR gates (or, equivalently, all gates are NAND gates, or all gates are NOR gates), the inputs of a gate come from the immediately preceding layer
• Linear programming - Maximize a linear function subject to linear inequality constraints
• Lexicographically First Depth First Search Ordering - Given a graph with fixed ordered adjacency lists, and nodes u and v, is vertex u visited before vertex v in a depth-first search induced by the order of the adjacency lists?
• Context Free Grammar Membership - Given a context-free grammar and a string, can that string be generated by that grammar?
• Horn-satisfiability: given a set of Horn clauses, is there a variable assignment which satisfies them? This is P's version of the boolean satisfiability problem.
• Game of Life - Given an initial configuration of Conway's Game of Life, a particular cell, and a time T (in unary), is that cell alive after T steps?
• LZW (algorithm) (1978 paradigm) Data Compression - given strings s and t, will compressing s with an LZ78 method add t to the dictionary? (Note that for LZ77 compression such as gzip, this is much easier, as the problem reduces to "Is t in s?".)
• Type inference for partial types - Given an untyped term from the lambda calculus, determine whether this term has a partial type.

In order to prove that a given problem in P is P-complete, one typically tries to reduce a known P-complete problem to the given one.

In 1999, Jin-Yi Cai and D. Sivakumar, building on work by Ogihara, showed that if there exists a sparse language that is P-complete, then L = P.