Talk:♯P-complete

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Low	This article has been rated as Low-priority on the project's priority scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]