Non-membership conjecture for the sign-imbalance problem in #P

For a poset PP, its sign imbalance is the absolute difference between the numbers of even and odd linear extensions. The computational problem Sign Imbalance takes a poset PP as input and outputs its sign imbalance; the class #P\mathsf{\#P} consists of functions counting accepting paths of nondeterministic polynomial-time computations. Sign Imbalance non-membership conjecture.

\textscSignImbalance#P.\textsc{Sign Imbalance}\notin\mathsf{\#P}.

Sign imbalance is naturally in the counting-difference class GapP\mathsf{GapP}, but the source states that its non-membership in #P\mathsf{\#P} remains open.

Sources & referencesView supporting material

Primary source

David Soukup, “Complexity of sign imbalance, parity of linear extensions, and height 2 posets”, arXiv:2311.02203 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.