Lune

FOCS2022顶会

What is in #P and what is not?

Christian Ikenmeyer, Igor Pak

2022年份
10被引次数
3顶会引用

摘要

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 也一样。你提问,回答直接引用原文。

可以从这些问题问起

智能体调用

Luneget_paper_fulltext

在 Lune 里问

免费开始,无需绑卡

lune papers fulltext 8b65d32a-0b0f-45e0-b611-bae0603d18ac

引用它的顶会 Paper3

问问它们各自怎么用它

它引用的顶会 Paper4

相关 Paper

黄昏的海面,两侧是细线勾勒的悬崖