<p>GapP is exactly the closure of #P under subtraction. On the other hand, #P is not closed under subtraction unless UP=PP. I believe that answers your questions.  </p>

CC BY-SA 3.0
2011-09-13T00:09:06.890Z
If you voted it down, at least explain why it is wrong.. Thanks
Tayfun Pay
CC BY-SA 3.0
2011-09-13T13:23:43.193Z
I agree. As far as I can tell the answer makes two correct statements and answers the original question (although my searching revealed that UP=PH is the desired conditional?)
Suresh Venkat
CC BY-SA 3.0
2011-09-13T14:06:57.053Z
@Suresh: How does this post answer the original question?  The question is not about a GapP-complete problem.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-13T15:09:24.310Z
part (2) in the update asks: "what are the prospects of GapP not being equal to #P". this answer points out that unless a collapse happens, #P is not closed under subtraction and so there's no point even talking about equality.
Suresh Venkat
CC BY-SA 3.0
2011-09-13T18:37:08.613Z
@Suresh: I see.  I thought that by “original question,” you meant the part which was not added afterward.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-14T23:38:33.320Z
I am loving the fact that I am getting cyber bullied. There is a gang of several people on this site and they are always right, even if they are wrong..
Tayfun Pay
CC BY-SA 3.0
2011-09-14T23:44:24.730Z
@Suresh: This is the paper. M.Ogiwara & L. Hemachandra. “A complexity theory for feasible closure properties.” Journal of Computer and System Sciences Volume 46 Pages 295-325. 1993.
Tayfun Pay
CC BY-SA 3.0
2011-09-12T23:54:31.657Z
2011-09-14T23:45:13.060Z
2011-09-14T23:45:13.060Z
Tayfun Pay
<p>This area has grown immensely in the 12 years since I asked the question. In particular, <a href="https://arxiv.org/abs/2207.05423" rel="nofollow noreferrer">Ikenmeyer, Pak and Panova</a> have shown that the squares of symmetric group characters are not in #(P), unless the polynomial hierarchy collapses. See <a href="https://arxiv.org/abs/2306.17511" rel="nofollow noreferrer">Panova's survey</a> for other major progress in the area.</p>

CC BY-SA 4.0
2024-02-13T20:28:28.030Z
2024-02-13T20:28:28.030Z
David E Speyer
<p>The question of  computing Characters of irreducible representations of the symmetric group might be a natural candidate.</p>

<p>I think Charles Hepler shows it is  Gap-P complete, but I'm not sure: for a link to his Master's thesis, see 
<a href="https://dspace.ucalgary.ca/handle/1880/45530?mode=full" rel="nofollow">https://dspace.ucalgary.ca/handle/1880/45530?mode=full</a></p>

CC BY-SA 3.0
2012-04-17T22:45:31.437Z
2012-04-18T04:42:30.527Z
2012-04-18T04:42:30.527Z
Hari
<p>I'd suggest looking at properties of #P functions that are different than Gap-P functions. For example, determining if a #P function is zero is in co-NP. If you could show determining whether the Kronecker coefficients is zero is UP-hard then you would have "Kronecker coefficients in #P implies UP in co-NP", an unlikely conclusion. </p>

CC BY-SA 3.0
2011-09-11T22:26:12.343Z
2011-09-11T22:26:12.343Z
Lance Fortnow
<p>There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take computing <a href="http://en.wikipedia.org/wiki/Kronecker_coefficient">Kronecker coefficients</a> as my example. Usually, the notion of "positive formula" is not precisely defined in combinatorics, but it roughly means "a description as the cardinality of seem reasonably explicit set". Recently, I've been talking to Jonah Blasiak, and he's been convincing me that the right definition of "positive formula" is <a href="http://en.wikipedia.org/wiki/Sharp-P">#P</a>. I'm going to assume that, on this site, I don't need to define #P.</p>

<p><a href="http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAJ0131/2487">Buergisser and Ikenmeyer</a> show that Kronecker coefficients are #P hard. (They are also always positive, because they are tensor product multiplicities.) But I am reasonably sure that no one knows a way of computing them which even gets them into #P.</p>

<p>So, suppose that I were to actually make an attempt at proving Kronecker coefficients aren't in #P. I assume that what I would do is assume some complexity theoretic conjecture and then reduce Kronecker product to some other problem which is known to be complete for a class larger than #P. </p>

<blockquote>
  <p>What conjecture might I assume, and what problem might I try to reduce to?</p>
</blockquote>

<p><hr> 
<strong>ADDED:</strong> As has been pointed out in the comments, Buergisser and Ikenmeyer show that Kronecker coefficients are in Gap-P, which is pretty close to #P. So it sounds like the questions I should be asking are (1) What are some Gap-P-complete problems I could plausibly reduce to and (2) what are the prospects of showing that Gap-P is not #P? I guess (2) should break up into two parts (2a) do experts believe these classes are different? and (2b) are there any likely strategies to prove it?</p>

<p>I hope that this much editing of the question is not frowned on. </p>

CC BY-SA 3.0
2011-09-11T13:42:45.920Z
By the way, I can't create a #P tag because I have less than 300 rep. It would be nice if someone would add that for me.
David E Speyer
CC BY-SA 3.0
2011-09-11T13:53:03.887Z
Welcome to cstheory! (I added [tag:counting-complexity] and [tag:lower-bounds] to the question).
Kaveh
CC BY-SA 3.0
2011-09-11T14:39:09.667Z
@Kaveh Bürgisser and Ikenmeyer [show](http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAJ0131/2487) that computing Kronecker coefficients is in GapP. David, are Kronecker coefficients always non-negative integers?
Tyson Williams
CC BY-SA 3.0
2011-09-11T15:11:22.767Z
Yes. They are multiplicites of tensor products, so they are always nonnegative.
David E Speyer
CC BY-SA 3.0
2011-09-11T17:34:29.567Z
You have a problem in GapP and you want to prove that it is outside #P.  An obvious approach is to show that the problem is GapP-complete under functional (Levin) reducibility, which will imply that the problem is outside #P assuming #P≠GapP.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-11T20:26:00.883Z
What I wrote in my previous comment is incorrect, because any problem in GapP is functional reducible to #P (if I am not mistaken this time).  In other words, the difference between #P and GapP is too delicate to handle by using functional reducibility.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-11T20:43:46.050Z
I think that the fact that the problem is known to be in GapP is integral part of the question.  Would you consider to include it as part of the question?  It might also worth stating it in the title.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-12T04:46:48.287Z
There's no problem in editing, but I believe that if you do too many edits, it might convert to CW ? this is different from MO.
Suresh Venkat
<cc.complexity-theory><counting-complexity><lower-bounds>
How can I show a Gap-P problem is outside #P
David E Speyer
# How can I show a Gap-P problem is outside #P

(Asked by: username_0 on 2011-09-11)

There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take computing [Kronecker coefficients](http://en.wikipedia.org/wiki/Kronecker_coefficient) as my example. Usually, the notion of "positive formula" is not precisely defined in combinatorics, but it roughly means "a description as the cardinality of seem reasonably explicit set". Recently, I've been talking to Jonah Blasiak, and he's been convincing me that the right definition of "positive formula" is [#P](http://en.wikipedia.org/wiki/Sharp-P). I'm going to assume that, on this site, I don't need to define #P.

[Buergisser and Ikenmeyer](http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAJ0131/2487) show that Kronecker coefficients are #P hard. (They are also always positive, because they are tensor product multiplicities.) But I am reasonably sure that no one knows a way of computing them which even gets them into #P.

So, suppose that I were to actually make an attempt at proving Kronecker coefficients aren't in #P. I assume that what I would do is assume some complexity theoretic conjecture and then reduce Kronecker product to some other problem which is known to be complete for a class larger than #P.

> What conjecture might I assume, and what problem might I try to reduce to?

---

**ADDED:** As has been pointed out in the comments, Buergisser and Ikenmeyer show that Kronecker coefficients are in Gap-P, which is pretty close to #P. So it sounds like the questions I should be asking are (1) What are some Gap-P-complete problems I could plausibly reduce to and (2) what are the prospects of showing that Gap-P is not #P? I guess (2) should break up into two parts (2a) do experts believe these classes are different? and (2b) are there any likely strategies to prove it?

I hope that this much editing of the question is not frowned on.

**Tags:** cc.complexity-theory, counting-complexity, lower-bounds
> **Comments:**
> **username_0**: By the way, I can't create a #P tag because I have less than 300 rep. It would be nice if someone would add that for me.  
> **username_1**: Welcome to cstheory! (I added [tag:counting-complexity] and [tag:lower-bounds] to the question).  
> **username_2**: @Kaveh Bürgisser and Ikenmeyer [show](http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewFile/dmAJ0131/2487) that computing Kronecker coefficients is in GapP. David, are Kronecker coefficients always non-negative integers?  
> **username_0**: Yes. They are multiplicites of tensor products, so they are always nonnegative.  
> **username_3**: You have a problem in GapP and you want to prove that it is outside #P.  An obvious approach is to show that the problem is GapP-complete under functional (Levin) reducibility, which will imply that the problem is outside #P assuming #P≠GapP.  
> **username_3**: What I wrote in my previous comment is incorrect, because any problem in GapP is functional reducible to #P (if I am not mistaken this time).  In other words, the difference between #P and GapP is too delicate to handle by using functional reducibility.  
> **username_3**: I think that the fact that the problem is known to be in GapP is integral part of the question.  Would you consider to include it as part of the question?  It might also worth stating it in the title.  
> **username_4**: There's no problem in editing, but I believe that if you do too many edits, it might convert to CW ? this is different from MO.  

---

## 4 answers

### Answer by username_7 on 2011-09-11. Score: 13 | Accepted answer

I'd suggest looking at properties of #P functions that are different than Gap-P functions. For example, determining if a #P function is zero is in co-NP. If you could show determining whether the Kronecker coefficients is zero is UP-hard then you would have "Kronecker coefficients in #P implies UP in co-NP", an unlikely conclusion.


---

### Answer by username_5 on 2011-09-12. Score: 4

GapP is exactly the closure of #P under subtraction. On the other hand, #P is not closed under subtraction unless UP=PP. I believe that answers your questions.

> **Comments:**
> **username_5**: If you voted it down, at least explain why it is wrong.. Thanks  
> **username_4**: I agree. As far as I can tell the answer makes two correct statements and answers the original question (although my searching revealed that UP=PH is the desired conditional?)  
> **username_3**: @Suresh: How does this post answer the original question?  The question is not about a GapP-complete problem.  
> **username_4**: part (2) in the update asks: "what are the prospects of GapP not being equal to #P". this answer points out that unless a collapse happens, #P is not closed under subtraction and so there's no point even talking about equality.  
> **username_3**: @Suresh: I see.  I thought that by “original question,” you meant the part which was not added afterward.  
> **username_5**: I am loving the fact that I am getting cyber bullied. There is a gang of several people on this site and they are always right, even if they are wrong..  
> **username_5**: @Suresh: This is the paper. M.Ogiwara & L. Hemachandra. “A complexity theory for feasible closure properties.” Journal of Computer and System Sciences Volume 46 Pages 295-325. 1993.  

---

### Answer by username_0 on 2024-02-13. Score: 3

This area has grown immensely in the 12 years since I asked the question. In particular, [Ikenmeyer, Pak and Panova](https://arxiv.org/abs/2207.05423) have shown that the squares of symmetric group characters are not in #(P), unless the polynomial hierarchy collapses. See [Panova's survey](https://arxiv.org/abs/2306.17511) for other major progress in the area.


---

### Answer by username_6 on 2012-04-17. Score: 1

The question of computing Characters of irreducible representations of the symmetric group might be a natural candidate.

I think Charles Hepler shows it is Gap-P complete, but I'm not sure: for a link to his Master's thesis, see
<https://dspace.ucalgary.ca/handle/1880/45530?mode=full>


---

