What is in #P and what is not?
Christian Ikenmeyer, Igor Pak
Abstract
For several classical nonnegative integer functions we investigate if they are members of the counting complexity class # P or not. We prove # P membership in surprising cases, and in other cases we prove non-membership, relying on standard complexity assumptions or on oracle separations. We initiate the study of the polynomial closure properties of # P on affine varieties, i.e., if all problem instances satisfy algebraic constraints. This is directly linked to classical combinatorial proofs of algebraic identities and inequalities. We investigate # TFNP and obtain oracle separations that prove the strict inclusion of # P in all standard syntactic subclasses of # TFNP minus 1.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext 8b65d32a-0b0f-45e0-b611-bae0603d18acCited by top-tier papers3
- Positivity of the symmetric group characters is as hard as the polynomial time hierarchyChristian Ikenmeyer, Igor Pak, Greta PanovaSODA 2023 · 5 citations
- Vanishing of Schubert CoefficientsIgor Pak, Colleen RobichauxSTOC 2025 · 1 citation
- Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial HierarchySwee Hong Chan, Igor PakSTOC 2024 · 1 citation
Builds on4
- The complexity of gradient descent: CLS = PPAD ∩ PLSJohn Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul SavaniSTOC 2021 · 23 citations
- Constant inapproximability for PPAArgyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis MelissourgosSTOC 2022 · 8 citations
- On the Orbit Closure Containment Problem and Slice Rank of TensorsMarkus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey et al.SODA 2021 · 7 citations
- Implementing geometric complexity theory: on the separation of orbit closures via symmetriesChristian Ikenmeyer, Umangathan KandasamySTOC 2020 · 2 citations
Related papers
- #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?Max Bannach, Erik D. Demaine, Timothy Gomez, Markus HecherLICS 2025 · 5 citations
- A Dichotomy for Real Boolean Holant ProblemsShuai Shao, Jin-Yi CaiFOCS 2020 · 11 citations
- Separations in Proof Complexity and TFNPMika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre et al.FOCS 2022 · 8 citations
- Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism PolynomialsPrateek Dwivedi, Benedikt Pago, Tim SeppeltSTOC 2026 · 3 citations
- The amazing mixed polynomial closure and its applications to two-variable first-order logicThomas PlaceLICS 2022 · 3 citations
