Theoretical Computer Science
cc.complexity-theory counting-complexity lower-bounds
Updated Sun, 22 May 2022 08:51:49 GMT

How can I show a Gap-P problem is outside #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 Kronecker coefficients 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. I'm going to assume that, on this site, I don't need to define #P.

Buergisser and Ikenmeyer 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.


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.