<p>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: <a href="https://cstheory.stackexchange.com/questions/8178/how-can-i-show-a-gap-p-problem-is-outside-p">How can I show a Gap-P problem is outside #P</a></p>
<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 <span class="math-container">$0$</span> is UP-hard (something I have no idea how to do, I don't know what a UP-hard problem looks like).</p>
<p>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?</p>
<p>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.</p>

CC BY-SA 4.0
2023-12-26T19:39:30.580Z
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
CC BY-SA 4.0
2023-12-26T20:00:09.787Z
@EricAllender Thanks. This paper actually presents the exact problem I have in mind as a candidate for not being in #P.
Matt Samuel
<cc.complexity-theory><counting-complexity>
Properties of #P functions that a GapP function may violate
Matt Samuel
# Properties of #P functions that a GapP function may violate

(Asked by: username_0 on 2023-12-24)

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](https://cstheory.stackexchange.com/questions/8178/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.

**Tags:** cc.complexity-theory, counting-complexity

> **Comments:**
> **username_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  
> **username_0**: @EricAllender Thanks. This paper actually presents the exact problem I have in mind as a candidate for not being in #P.  

---

## 0 answers

