4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Saeed Nov 14 '13 at 13:15
  • 1
    $\begingroup$ Well I just noticed that 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. $\endgroup$ – 4evergr8ful Nov 14 '13 at 15:37
  • $\begingroup$ 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. $\endgroup$ – Saeed Nov 15 '13 at 14:04
  • $\begingroup$ @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. $\endgroup$ – 4evergr8ful Nov 21 '13 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.