Hacker News new | past | comments | ask | show | jobs | submit
If I can "count the satisfying assignments of a k-CNF in subexponential time and polynomial space", could I just count the the solutions for assignments of 0 and 1 to x_1, then proceed with whichever is greater (or nonzero), counting the solutions for x_2=0, and so on.

Doesn't that lead me to an existence proof (i.e., a solution) to a k-SAT problem in N*(subexponential_time and polynomial_space)?

And with constant folding, N is reduced by 1 on each iteration.

What obvious thing am I missing here?