Encyclopedia > Sharp-P-Complete

  Article Content

Sharp-P-complete

Redirected from Sharp-P-Complete

#P-complete, pronounced "sharp P complete", is a complexity class in complexity theory. A problem is in #P-complete if and only if it is in #P, and every problem in #P can be reduced to it in polynomial time.

Examples of #P-complete problems include:

  • How many different variables assignments will satisfy a given DNF formula?
  • What is the permanent[?] of a given matrix?
  • How many perfect matchings are there for a given bipartite graph?

It is believed that there is no polynomial-time algorithm for solving #P-complete problems. If it is difficult to solve exactly, then can it even be approximated? No deterministic algorithm is known that can even find the approximate answer to within some reasonable error bound.

However, there are probabilistic algorithms that return good approximatations to some #P-complete problems with high probability. This is one of the most striking demonstrations of the power of probabilistic algorithms.

It is surprising that some #P-complete problems correspond to easy P problems. The third example problem above is in this category. The question "Is there a perfect matching for a given bipartite graph?" can be answered in polynomial time. In fact, for a graph with V vertices and E edges, it can be answered in O(VE) time. The corresponding question "how many perfect matchings does the given bipartite graph have?" is #P-complete.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Abu Bakr Mohammad Ibn Zakariya al-Razi

... a description of other methods and piratical [?] applications used in transmutation: the admixture and uses of solvent vehicles, the amount of heat (fire) used, ...