Talk:♯P-complete

Implies P=NP

Just in case anyone's wondering why a poly-time algorithm for a #P-complete problem implies P=NP, it follows from Toda's theorem. We know P^#P contains PH, so if the P machine can simulate #P oracle queries in poly time, it can solve all of PH in P. Deco 19:29, 26 Jun 2005 (UTC)

Alternatively, we could just count the number of accepting paths, and if there's one or more, accept.137.149.156.4 (talk) 18:47, 14 July 2010 (UTC)

Solved? https://archive.org/details/mainIdeas

DNF is also in P

From the article: "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." Notice that this is also true for the first example (DNF), and is even a simpler example.

NP-complete problem corresponding to non-#P-complete problem?

Are there any problems X in NP-complete for which #X are not (believed to be) #P-complete? -- Myria 06:37, 25 April 2007 (UTC)

• YES, there are such problems. Take for instance, satisfiability in Boolean rings. The decision problem to know whether a Boolean ring term t is satisfiable (i.e., whether it evaluates to 1 under a good truth assignment) is NP-complete. However, counting the number of such satisfying assignments is in FP^NP[1], i.e., in the class of polynomial functions making only one oracle call to NP. The latter construction exploits Löwenhaim's Theorem of the representation of Boolean ring solutions.--Miki Hermann 15:42, 24 October 2007 (UTC)

Reduction

The sentence "A problem is #P-complete if and only if it is in #P, and every problem in #P can be reduced to it in logarithmic space" is incorrect. The problem 2SAT, as well as #Positive 2SAT, counting the number of satisfying truth assignments for all and positive Krom (2-satisfiability) formulas is #P-complete. However, there is no known logspace reduction from #3SAT to #2SAT, otherwise we would have the same reduction also for the decision problems from 3SAT to 2SAT, what implies P=NP. Hence, I changed the sentence to counting reductions, i.e., Turing reduction relating the cardinality of solutions.--Miki Hermann 15:49, 24 October 2007 (UTC)

Proposed deletion of "Permanent is sharp-P-complete"

Perhaps contributors to this article can also contribute to the discussion of whether the article titled "Permanent is sharp-P-complete" should be deleted. See Wikipedia:Articles for deletion/Permanent is sharp-P-complete. Michael Hardy (talk) 12:58, 19 December 2008 (UTC)

Special symbol in title

It looks like the title is currently "Sharp-P-complete" because of the technical restriction disallowing use of the pound sign in title text. I would suggest using the "sharp" symbol ♯ instead, which is allowed in title text. 128.104.3.101 (talk) 20:06, 9 January 2013 (UTC)