pith. sign in

arxiv: 2204.13149 · v1 · pith:DP3DWTVHnew · submitted 2022-04-27 · 💻 cs.CC · math.CO

What is in #P and what is not?

classification 💻 cs.CC math.CO
keywords provealgebraiccasesclassicalcomplexityinvestigateoracleseparations
0
0 comments X
read the original 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-1.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Correlation inequalities for Schur positivity

    math.CO 2026-06 unverdicted novelty 7.0

    Generalizes Ahlswede-Daykin inequality to Schur-positive ADS inequality and resolves Mihalcea's conjecture on log-supermodularity of stable Grothendieck polynomials.

  2. On Variable-Bounded Non-Linear Expansions of Presburger Arithmetic

    cs.LO 2026-05 unverdicted novelty 7.0

    Decidability is shown for single-variable Presburger expansions with fixed powers via hyperelliptic Diophantine solvability and with degree-at-most-three polynomials via low-genus curves, with hardness results when re...