Algorithm

Prime power

Discrete mathematics

Boolean function

Prime (order theory)

Time complexity

Operating system

Computer science

Integer (computer science)

Upper and lower bounds

Mathematics

Mathematical analysis

Geometry

Combinatorics

Programming language

Modulo

Space (punctuation)

Reduction (mathematics)

Arithmetic

Proceedings - IEEE Conference on Computational Complexity/Proceedings

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for SAT. Let m be a positive integer, and define MOD_m- SAT to be the problem of determining if a given Boolean formula has exactly km satisfying assignments, for some integer k. We prove that for all primes p, except for possibly one of them, MOD_p-SAT is not solvable in nc time and n^o(1) space on RAMs, for c \geqslant 1 satisfying c^3 - c^2 - 2c + 1 \le 0 (c \le 1.801 suffices). That is, there is at most one prime p that does not satisfy the lower bound. Note that such a lower bound does not follow from the SAT time-space tradeoffs, as we do not know of an efficient deterministic reduction from SAT to MOD_p-SAT. The result is non-constructive, in that it does not provide an explicit prime for which the lower bound holds. However, we can prove that the same limitation holds for SAT and MOD_6-SAT, as well as MOD_m-SAT for any composite m that is not a prime power. Our main tool is a general method for rapidly simulating deterministic RAM computations with restricted space, by counting the number of solutions to NP predicates modulo primes. The simulation converts an ordinary RAM into a "canonical one" that runs in roughly the same amount of time and space, yet its configuration sequences have nice properties suitable for counting.

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers