Approximate Polynomial Satisfiability is in the Counting HierarchyResearch Paper
An exact polynomial system asks for values making every output zero. Problems in algebraic complexity also ask whether zero can be approached by outputs of a polynomial map, even when no input gives zero exactly. Approximate polynomial satisfiability, abbreviated APS, expresses this second question using algebraic closure rather than numerical tolerances.…