论文标题
什么是#P，什么不是？
What is in #P and what is not?
论文作者
论文摘要
对于几个经典的非负整数函数，我们研究它们是否是计数复杂性类别#P的成员。我们在令人惊讶的情况下证明了#P成员资格，在其他情况下，我们依靠标准的复杂性假设或甲骨文分离证明了非会员职位。 我们启动#P对仿射品种的多项式闭合特性的研究，即，如果所有问题实例都满足代数约束。这直接与代数身份和不平等的经典组合证明有关。我们研究#TFNP并获得甲骨文分离，这些分离证明了#P在＃TFNP-1的所有标准句法亚类中严格包含。
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.
