Iterated Mod (IM)
Input
Integers $a, b_1, \ldots, b_n$.
Problem
Is $((\cdots((a \bmod b_1) \bmod b_2) \cdots) \bmod b_n) = 0$?
Status
$\P$-complete (Karloff and Ruzzo [1]).
Remarks
The reduction to show hardness is from NANDCVP.
The Polynomial Iterated Mod Problem is the problem in which $a(x), b_1(x), \ldots, b_n(x)$ are univariate polynomials over a field $F$ and the question is to determine if $$((\cdots((a(x) \bmod b_1(x)) \bmod b_2(x)) \cdots) \bmod b_n(x)) = 0?$$ This problem is in $\NC$ [1]. The proof technique used to show IM is $\P$-complete can be modified to show the Superincreasing Knapsack Problem is also $\P$-complete [1]. The Superincreasing Knapsack Problem is defined analogously to the Knapsack Problem (Garey and Johnson [2]) with weights $w_1, \ldots, w_n$, except for $2 \leq i \leq n$, $w_i > \sum_{j=1}^{i-1} w_j$. See Lin [3][4] for additional work on IM. Mayr describes a fully $\NC$ approximation scheme for the $0–1$ Knapsack Problem in [2].
References
- H. J. Karloffand W. L. Ruzzo (1989). The iterated mod problem.
- E. W. Mayr (1988). Parallel approximation algorithms.
- M. R. Garey and D. S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness.
- Y. Lin (1991). Parallel Computational Methods in Integer Linear Programming.
- Y. Lin-Kriz and V. Pan (1992). On parallel complexity of integer linear programming, GCD and the iterated mod function.
- Greenlaw, R., Hoover, H. J., and Ruzzo, W. L. (1995). Limits to Parallel Computation: P-Completeness Theory. Oxford University Press. Problem A.8.5.