The sparse common-zero counter used by the SAT reduction
Fix k and c. The manuscript counter accepts ANY system of at most c n binary polynomial equations, each with degree at most k and at most (log n)^c monomials. It does not require that its zeros already equal the satisfying assignments of a SAT formula. High-incidence branching leaves polylogarithmic scope and incidence bounds. On each branch, use ell=n+1 from the original variable count and the lifted-degree/bit analysis with the checked layout. Since n_prime>=n/2, m and ell remain O(n_prime). The resulting stated time is 2^{O_{k,c}(rho(n))}, rho(n)=n(log log n)^2/sqrt(log n), and polynomial space. Failed finite checks fall back to exhaustive counting. This is an asymptotic manuscript result, not a demonstrated practical solver.
0
1
Tags
Math