Talk:Sharp-P-complete
| WikiProject Mathematics (Rated Start-Class) | |||
|---|---|---|---|
 |
|||
| Mathematics rating: | Start Class | Low Priority | Field: Discrete mathematics |
|
Please update this rating as the article progresses, or if the rating is inaccurate. |
|||
| WikiProject Computer science | (Rated Start-class, Mid-importance) | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
||||||||||||||||||||||
Contents |
[edit] 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)
[edit] 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.
[edit] 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)
[edit] 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)
[edit] 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)
