Index: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Home > P-complete
In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. A decision problem is in P-complete if it is in P, and every problem in P can be reduced to it in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem A is in P-complete if, for each problem B in P, there are constants c and k such that B can be reduced to A in time O((log n)c) using O(nk) parallel processors. See NC for the definition of parallel processors.1 Motivation
The class P, typically taken to consist of all the "tractable" problems for a sequential computer, contains the class NC, which consists of those problems which can be efficiently solved on a parallel computer. This is because parallel computers can be simulated on a sequential machine.
It is not known whether NC=P. In other words, it is not known whether there are any tractable problems that are inherently sequential. Just as it is widely suspected that P does not equal NP, so it is widely suspected that NC does not equal P.
The class NP-complete, which can be thought of as containing the "probably intractable" problems, is introduced to analyze the P=NP question, and the class P-complete, which can be thought of as containing the "probably not parallelizable" or "probably inherently sequential" problems, serves in a similar manner to study the NC=P question.
Finding an efficient way to parallelize the solution to some P-complete problem would disprove the suspicion that NC ≠ P.
2 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.
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 or NOR gates), the inputs of a gate come from the immediately-preceding layer
- Linear programming - Maximize a linear function subject to linear inequality constraints
- 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?
- 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 problemMathematical logic Computational complexity theory The Boolean satisfiability problem (SAT is a decision problem considered in complexity theory. An instance of the problem is defined by a Boolean expression written using only AND, OR, NOT, variables, and.
- Game of Life - Given an initial configuration of Conway's Game of LifeThis page is about Conway's Game of Life, the cellular automaton. For Hasbro's board game, see Hasbro's Game of Life. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is the best-known example of, 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 (such as Unisys's LZWLZW Lempel-Ziv-Welch is a lossless data compression algorithm. The algorithm is derived from the LZ77 algorithm presented by Abraham Lempel and Jacob Ziv in a paper entitled "A Universal Algorithm for Sequential Data Compression" in the IEEE Transactions technology) add t to the dictionary? (Note that for LZ77 compression such as gzipgzip is short for GNU Zip, a GNU open-source replacement for the Unix compress program. Gzip is based on the deflate algorithm, which is a combination of LZ77 and Huffman coding. Deflate' was developed in response to patents that covered LZW and other com, this is much easier, as the problem reduces to "Is s in t?".)
In order to prove that a given problem is P-complete, one typically tries to reduce a known P-complete problem to the given one, using an efficient parallel algorithm.
Read more »