I want to show a specific GapP problem is likely not in #P, actually very closely related to this question in terms of the area of mathematics it is from: How can I show a Gap-P problem is outside #P

It's suggested in the accepted answer to use properties of #P functions to find some condition that will effectively (though not conclusively) rule it out. The answer suggests trying to show that determining whether the coefficient is $0$ is UP-hard (something I have no idea how to do, I don't know what a UP-hard problem looks like).

So in line with this, what specifically are some properties of #P functions that could be used to show that a certain GapP problem being in #P would cause some unlikely collapse of complexity classes?

I know the problem is #P-hard, there was a paper awhile ago that shows a very special case of the problem is #P-complete.

  • 1
    $\begingroup$ A recent paper that discusses the question about what GapP functions are in #P is this one: math.ucla.edu/~pak/papers/Whatisin-FOCS.pdf $\endgroup$ Dec 26, 2023 at 19:39
  • $\begingroup$ @EricAllender Thanks. This paper actually presents the exact problem I have in mind as a candidate for not being in #P. $\endgroup$ Dec 26, 2023 at 20:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.