The Library
What is in# P and what is not?
Tools
Ikenmeyer, Christian and Pak, Igor (2022) What is in# P and what is not? In: FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science, Denver, USA, Oct 31 - Nov 3, 2022. Published in: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) pp. 860-871. doi:10.1109/FOCS54457.2022.00087
|
PDF
WRAP-what-is-in#-P-what-is-not-Ikenmeyer-2022.pdf - Accepted Version - Requires a PDF viewer. Download (1136Kb) | Preview |
Official URL: https://doi.ieeecomputersociety.org/10.1109/FOCS54...
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 minus 1.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
Library of Congress Subject Headings (LCSH): | Computational complexity, Combinatorial analysis -- Data processing, Computer science -- Mathematics, Discrete mathematics , Combinatorial analysis | ||||||
Journal or Publication Title: | 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) | ||||||
Publisher: | IEEE Computer Society | ||||||
Official Date: | 2022 | ||||||
Dates: |
|
||||||
Page Range: | pp. 860-871 | ||||||
DOI: | 10.1109/FOCS54457.2022.00087 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 8 November 2022 | ||||||
Date of first compliant Open Access: | 8 November 2022 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Denver, USA | ||||||
Date(s) of Event: | Oct 31 - Nov 3, 2022 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year