<p>Are there <em>weakly</em> NP-complete problems whose associated counting problem can be computed in <em>pseudo-polynomial</em> time? And if one were to be found (and assuming it is #P-complete), what would be the consequences on the polynomial hierarchy?</p>

<p>I'm aware of pseudo-polynomial time approximate counts to the knapsack problem. I'm only interested in exact ones.</p>

CC BY-SA 3.0
2013-11-14T13:15:57.267Z
I cannot see any relation between weekly NP-completeness and pseudo poly time algorithm for the corresponding #P problem. e.g 2-SAT is in P, but it's corresponding #P problem is #P-complete (in strong sense) that there is no pseudo-polynomial time algorithm, because otherwise there should be a polynomial algorithm for it, because it's a number problem and has nothing to do with magnitude of inputs, and just considers the size of input.
Saeed
CC BY-SA 3.0
2013-11-14T15:37:22.367Z
Well I just noticed that http://www.cs.utexas.edu/~klivans/focs11.pdf briefly mentions a pseudo-polynomial counting algorithm for the #P-complete version of Knapsack. It's not clear to me yet how this fits in the hierarchy. I'll have to pause and think about it one of these days.
4evergr8ful
CC BY-SA 3.0
2013-11-15T14:04:38.397Z
Actually I tried to say that, seems pseudo polynomial time algorithm for # version of some weakly NP-complete problem doesn't imply any general rule, I think if you are looking for a relation is better to look at structure of problem and a reason that this falls in pseudo polynomial time. Otherwise as I already mentioned there is a #P complete for P problem and it also seems to be in strong sense (no number plays role in #2SAT). Because of this I think even if there is a special hierarchy for this (which is good question), it shouldn't be related to weakly NP-completeness of original one.
Saeed
CC BY-SA 3.0
2013-11-21T06:20:23.537Z
@Saeed The potential hole that a pseudo-polynomial counting algorithm for #Knapsack poses is that you could conceivably have a polynomial transformation from #2SAT to #Knapsack and solve it efficiently; provided the resulting #Knapsack weights and capacity aren't too big. But apparently chap 18 of Papadimitriou's book proves that would indeed be the case.
4evergr8ful
<cc.complexity-theory><reference-request><np-hardness><counting-complexity>
The weakly NP-complete problems and their associated counting problem
4evergr8ful
# The weakly NP-complete problems and their associated counting problem

(Asked by: username_0 on 2013-11-14)

Are there *weakly* NP-complete problems whose associated counting problem can be computed in *pseudo-polynomial* time? And if one were to be found (and assuming it is #P-complete), what would be the consequences on the polynomial hierarchy?

I'm aware of pseudo-polynomial time approximate counts to the knapsack problem. I'm only interested in exact ones.

**Tags:** cc.complexity-theory, reference-request, np-hardness, counting-complexity
> **Comments:**
> **username_1**: I cannot see any relation between weekly NP-completeness and pseudo poly time algorithm for the corresponding #P problem. e.g 2-SAT is in P, but it's corresponding #P problem is #P-complete (in strong sense) that there is no pseudo-polynomial time algorithm, because otherwise there should be a polynomial algorithm for it, because it's a number problem and has nothing to do with magnitude of inputs, and just considers the size of input.  
> **username_0**: Well I just noticed that http://www.cs.utexas.edu/~klivans/focs11.pdf briefly mentions a pseudo-polynomial counting algorithm for the #P-complete version of Knapsack. It's not clear to me yet how this fits in the hierarchy. I'll have to pause and think about it one of these days.  
> **username_1**: Actually I tried to say that, seems pseudo polynomial time algorithm for # version of some weakly NP-complete problem doesn't imply any general rule, I think if you are looking for a relation is better to look at structure of problem and a reason that this falls in pseudo polynomial time. Otherwise as I already mentioned there is a #P complete for P problem and it also seems to be in strong sense (no number plays role in #2SAT). Because of this I think even if there is a special hierarchy for this (which is good question), it shouldn't be related to weakly NP-completeness of original one.  
> **username_0**: @Saeed The potential hole that a pseudo-polynomial counting algorithm for #Knapsack poses is that you could conceivably have a polynomial transformation from #2SAT to #Knapsack and solve it efficiently; provided the resulting #Knapsack weights and capacity aren't too big. But apparently chap 18 of Papadimitriou's book proves that would indeed be the case.  

---

## 0 answers

