Non-membership conjecture for the sign-imbalance problem in #P
Non-membership conjecture for the sign-imbalance problem in #P
For a poset , its sign imbalance is the absolute difference between the numbers of even and odd linear extensions. The computational problem Sign Imbalance takes a poset as input and outputs its sign imbalance; the class consists of functions counting accepting paths of nondeterministic polynomial-time computations. Sign Imbalance non-membership conjecture.
Sign imbalance is naturally in the counting-difference class , but the source states that its non-membership in 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.