|
#P-complete, pronounced "sharp P complete" or "number P complete" is a complexity class in computational complexity theory. By definition, 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. Equivalently, a problem is #P-complete if and only if it is in #P, and for any non-deterministic Turing machine, the problem of computing its number of accepting paths can be reduced to this problem. 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?〔.〕 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. == Easy problems with hard counting versions == It is surprising that some #P-complete problems correspond to easy P problems. It is 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. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sharp-P-complete」の詳細全文を読む スポンサード リンク
|