Linked Fates: How Small of an Ambiguity Increase Can Make the Difference Between Equaling and Separating from P?

Benjamin Carleton, Michael C. Chavrimootoo, Lane A. Hemaspaandra +3

Ambiguity-bounded versions of $\mathrm{NP}$, denoted ${\mathrm{UP}}_{\le f(n)}$, bound by $f(n)$ the number of accepting paths the nondeterministic polynomial-time Turing machine ca…