Probably the last post of the year- enjoy the holidays, everyone!
The problem: Periodic Solution Recurrence Relation. This is problem AN12 in the appendix.
The description: Given a set of m ordered pairs through with each >0, can we find a sequence though of integers, such that if we build the infinite sequence is periodic: that is, for all i?
Example: Here’s a super simple example: m=2 and the pairs are (1,1) and (2,2). This gives us the recurrence . If we start with 1,1, this gives the sequence 1,1,3,5,11,21,43,… which is periodic mod 10 (the last digit always repeats 1,1,3,5)
Reduction: This shows up in Plaisted’s 1984 paper. He mentions it as a corollary to his Theorem 5.1 which showed that Non-Trivial Greatest Common Divisor and Root of Modulus 1 were NP-Complete. Similar to the Root of Modulus 1 problem, we build a polynomial from a set of clauses that has 0’s on the unit circle. The polynomial also has a leading coefficient of 1. This means, apparently, that the recurrence relation corresponding to the polynomial has a periodic solution if and only if the polynomial has a root on the complex unit circle, which only happens if the original 3SAT formula was satisfiable.