2026-07-21T23:20:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16855 2024-03-06T10:58:30Z ddc:004 open_access

Gaps, Ambiguity, and Establishing Complexity-Class Containments via Iterative Constant-Setting Hemaspaandra, Lane A. Juvekar, Mandar Nadjimzadah, Arian Phillips, Patrick A. structural complexity theory computational complexity theory ambiguity-limited NP counting classes P-printable sets Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕ P (and thus that FewP ⊆ ⊕ P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed "nongappy"-ness) of the easy-to-find "targets" used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra-Pomerance-Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lane A. Hemaspaandra and Mandar Juvekar and Arian Nadjimzadah and Patrick A. Phillips 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.57 urn:nbn:de:0030-drops-168552 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.57 eng https://creativecommons.org/licenses/by/4.0/legalcode