Sharp-P-complete

Sharp-P-complete

#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory. A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it by a polynomial-time counting reduction, i.e. a polynomial-time Turing reduction relating the cardinalities of solution sets.[citation needed] Equivalently, a problem is #P-complete if and only if it is in #P, and for any non-deterministic Turing machine ("NP machine"), the problem of computing its number of accepting paths can be reduced to this problem.[citation needed]

Very often the reductions are "parsimonious," i.e., they preserve the number of solutions.[citation needed]

Examples of #P-complete problems include:

  • How many different variable assignments will satisfy a given general boolean formula? (#SAT)
  • How many different variable assignments will satisfy a given DNF formula?
  • How many different variable assignments will satisfy a given 2SAT formula?
  • How many perfect matchings are there for a given bipartite graph?
  • What is the value of the permanent of a given matrix whose entries are 0 or 1? (See Permanent is sharp-P-complete.)
  • How many graph colorings using k colors are there for a particular graph G?
  • How many different linear extensions are there for a given partial order, or, equivalently, how many different topological orderings are there for a given directed acyclic graph?[1]

A polynomial-time algorithm for solving a #P-complete problem, if it existed, would imply P = NP, and thus P = PH. No such algorithm is currently known.

Contents

Easy problems with hard counting versions

It is surprising that some #P-complete problems correspond to easy P problems. Its very easy to determine the satisfiability of a boolean formula in DNF: such a formula is satisfiable if and only if it contains a satisfiable conjunction (one that does not contain a variable and its negation), whereas counting the number of satisfying assignments is #P-complete. Also deciding 2-SAT is easy in contrast to counting the number of satisfying assignments. Topologically sorting is easy in contrast to counting the number of topological sortings. The same observation can be made for the perfect matching problem. It was known before that the decision problem "Is there a perfect matching for a given bipartite graph?" can be solved in polynomial time, and in fact, for a graph with V vertices and E edges, it can be solved in O(VE) time. The corresponding question "How many perfect matchings does the given bipartite graph have?" is already #P-complete. The problem of counting the number of perfect matchings (or in directed graphs: the number of vertex cycle covers) is known to be equivalent to the problem of the computation of the permanent of a matrix. The perfect matching counting problem was the first counting problem corresponding to an easy P problem shown to be #P-complete, in a 1979 paper by Leslie Valiant which also defined the classes #P and #P-complete for the first time.[2]

Approximation

There are probabilistic algorithms that return good approximations to some #P-complete problems with high probability. This is one of the demonstrations of the power of probabilistic algorithms.

Many #P-complete problems have a fully polynomial-time randomized approximation scheme, or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required. Jerrum, Valiant, and Vazirani showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.[3]

References

  1. ^ Brightwell, Graham R.; Winkler, Peter (1991). "Counting linear extensions". Order 8 (3): 225–242. doi:10.1007/BF00383444 .
  2. ^ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science (Elsevier) 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6. 
  3. ^ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science (Elsevier) 32: 169–188. 

Further reading

  • Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3540653678. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Permanent is sharp-P-complete — The correct title of this article is Permanent is #P complete. The substitution or omission of the # sign is because of technical restrictions. In a 1979 paper Leslie Valiant proved[1] that the problem of computing the permanent of a matrix is #P …   Wikipedia

  • Sharp Solar — produces both single and multi crystalline solar cells and for some years has been the world s leading manufacturer of photovoltaic (PV) modules. Sharp s solar cells are used for many applications, from satellites to lighthouses, and industrial… …   Wikipedia

  • Sharp-P — The correct title of this article is #P. The substitution or omission of the # sign is because of technical restrictions. In computational complexity theory, the complexity class #P (pronounced number P or, sometimes sharp P or hash P ) is the… …   Wikipedia

  • Sharp-shinned Hawk — Taxobox name = Sharp shinned Hawk status = LC | status system = IUCN3.1 image caption = Sharp shinned Hawk (nominate group). regnum = Animalia phylum = Chordata classis = Aves ordo = Falconiformes familia = Accipitridae genus = Accipiter species …   Wikipedia

  • C Sharp (programming language) — The correct title of this article is C# (programming language). The substitution or omission of the # sign is because of technical restrictions. C# Paradigm(s) multi paradigm: structured, imperative …   Wikipedia

  • Beauchamp-Sharp-Tragödie — Jeroboam O. Beauchamp ermordet Solomon P. Sharp (Stich aus dem Jahre 1833, erschienen in The United States Criminal Calendar) Als Beauchamp Sharp Tragödie oder Kentucky Tragödie (engl. Kentucky Tragedy) wird der Mord an dem Politiker Solomon P.… …   Deutsch Wikipedia

  • Granville Sharp — (10 November 1735 6 July 1813) was a British campaigner for the abolition of the slave trade, and a classicist. LifeGranville Sharp was the 20th of the 31 children of Thomas Sharp (1693 1758), a prolific theological writer and biographer of his… …   Wikipedia

  • Beauchamp–Sharp Tragedy — The Beauchamp Sharp Tragedy (sometimes called The Kentucky Tragedy) refers to the murder of Kentucky legislator Solomon P. Sharp by Jereboam O. Beauchamp. As a young lawyer, Beauchamp had been an admirer of Sharp s until the latter allegedly… …   Wikipedia

  • Becky Sharp — Miriam Hopkins dans le rôle titre Données clés Réalisation …   Wikipédia en Français

  • National Register of Historic Places listings in Sharp County, Arkansas — Location of Sharp County in Arkansas This is a list of the National Register of Historic Places listings in Sharp County, Arkansas. This is intended to be a complete list of the properties and districts on the National Register of Historic Places …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”