What is in #P and what is not?
Christian Ikenmeyer, Igor Pak
摘要
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.
问问这篇 Paper
智能体会读完全文。
Lune 把这篇 Paper 索引到了最后一个公式,引用它的顶会 Paper 也一样。你提问,回答直接引用原文。
引用它的顶会 Paper3
- Positivity of the symmetric group characters is as hard as the polynomial time hierarchyChristian Ikenmeyer, Igor Pak, Greta PanovaSODA 2023 · 被引用 5 次
- Vanishing of Schubert CoefficientsIgor Pak, Colleen RobichauxSTOC 2025 · 被引用 1 次
- Equality Cases of the Alexandrov-Fenchel Inequality Are Not in the Polynomial HierarchySwee Hong Chan, Igor PakSTOC 2024 · 被引用 1 次
它引用的顶会 Paper4
- The complexity of gradient descent: CLS = PPAD ∩ PLSJohn Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul SavaniSTOC 2021 · 被引用 23 次
- Constant inapproximability for PPAArgyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis MelissourgosSTOC 2022 · 被引用 8 次
- On the Orbit Closure Containment Problem and Slice Rank of TensorsMarkus Bläser, Christian Ikenmeyer, Vladimir Lysikov, Anurag Pandey 等SODA 2021 · 被引用 7 次
- Implementing geometric complexity theory: on the separation of orbit closures via symmetriesChristian Ikenmeyer, Umangathan KandasamySTOC 2020 · 被引用 2 次
相关 Paper
- #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 次
- A Dichotomy for Real Boolean Holant ProblemsShuai Shao, Jin-Yi CaiFOCS 2020 · 被引用 11 次
- Separations in Proof Complexity and TFNPMika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre 等FOCS 2022 · 被引用 8 次
- Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism PolynomialsPrateek Dwivedi, Benedikt Pago, Tim SeppeltSTOC 2026 · 被引用 3 次
- The amazing mixed polynomial closure and its applications to two-variable first-order logicThomas PlaceLICS 2022 · 被引用 3 次
