Pith. sign in

REVIEW 2 cited by

What is in #P and what is not?

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2204.13149 v1 pith:DP3DWTVH submitted 2022-04-27 cs.CC math.CO

Christian Ikenmeyer , Igor Pak This is my paper · ORCID
classification cs.CCmath.CO
keywords provealgebraiccasesclassicalcomplexityinvestigateoracleseparations
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Equality conditions for correlation inequalities

    math.CO 2026-07 accept novelty 8.0 of 10

    Equality in the Ahlswede–Daykin and FKG inequalities holds if and only if the underlying lattice decomposes as a direct product and the functions cross-factor across the two components.

  2. Positivity of Schubert Coefficients

    math.CO 2024-12 conditional novelty 4.0 of 10

    Under GRH and the Miltersen-Vinodchandran assumption, the positivity of Schubert coefficients has a positive rule, equivalent to the problem being in NP.

Pith tools