1

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.

Matt Samuel
  • 111
  • 3
  • 1
    A recent paper that discusses the question about what GapP functions are in #P is this one: https://www.math.ucla.edu/~pak/papers/Whatisin-FOCS.pdf – Eric Allender Dec 26 '23 at 19:39
  • @EricAllender Thanks. This paper actually presents the exact problem I have in mind as a candidate for not being in #P. – Matt Samuel Dec 26 '23 at 20:00

0 Answers0