What is the computational complexity of generalized Long Live the Queen?

Consider the following model of computation: The computer's memory consists of $$n$$ registers denoted $$r_1, ..., r_n$$, each holding an integer.

In the following, an affine combination means an expression of the form $$c_0 + \sum_{i=1}^n c_i r_i$$, where $$c_i$$ are all constant integers.

The instructions are :

• Assignment : $$r_i \leftarrow$$an affine combination of the registers
• Conditional forward jump : If an affine combination of the registers is $$\leq, =$$ or $$\geq 0$$, jump forward to the given label. Note that only forward jumps are allowed, so the program will always terminate.
• Accept
• Reject

Note that $$c_0 + \sum_{i=1}^n c_i r_i \leq d$$ iff $$c_0 + \sum_{i=1}^n c_i r_i - d \leq 0$$, so the conditional jump can also be an inequality of two affine combinations.

The acceptance problem is : given a list of instructions and the number of registers, does there exist starting values for the registers that causes the machine to accept? Note that the starting values must all be integers.

Question: What is the computational complexity of the acceptance problem? This is at least NP-hard because it contains integer linear programming. I'm guessing it's NP-complete because it can be modeled as a combination of ILP's.

This is based on the video game Long Live the Queen. In this game, you train skills to increase your stats. Sometimes there are skill checks where the storyline branches based on whether or not your stats are above a certain number (corresponding to conditional forward jumps).

Note that I only allowed affine combinations and not arbitrary polynomials, to avoid introducing undecidability via Hilbert's 10th problem.

Here is an example program :

4 registers : reflexes, herbal medicine, time spent learning reflexes, time spent learning herbal medicine
instruction list:
reflexes = 0
herbal medicine = 0 // zero out stats at the start
if time spent learning reflexes +  time spent learning herbal medicine >= 6 jump to label_reject // can't spend more than 5 hours learning
reflexes = reflexes + time spent learning reflexes
herbal medicine = herbal medicine+ time spent learning herbal medicine // increase skills
// the player encounters a snake!
if 0 <= 0 jump to label_not_bitten_by_snake // this is always true, and is an unconditional jump
label label_bitten_by_snake
if herbal medicine <= 4 jump to label_reject // you die of snake venom
label label_not_bitten_by_snake
label label_healed_snake_bite
accept
label label_reject
reject


One possible solution is :

reflexes = 0, herbal medicine = 0, time spent learning reflexes = 5, time spent learning herbal medicine = 0

• Also NP-hard because we can easily translate a SAT formula to a computer in this model. Commented May 29 at 0:22

Fortunately, ultimately, it is known that ILP is NP-complete. See https://cs.stackexchange.com/q/165088/755. Therefore, a valid certificate to a yes-instance for your problem is a straight-line path through the program (i.e., listing for each conditional branch, which branch was taken) that ends in an accept instruction, together with a proof that the resulting ILP is satisfiable. Note that when you focus on a single straight-line path, you can express everything in ILP: at each point along the path, each register can be expressed as a known affine function of $$x$$, the vector of original values of all registers; and each conditional branch corresponds to an affine inequality on $$x$$; so we obtain a system of affine inequalities. Proving that there exists a solution $$x$$ is just a ILP instance, for which polynomial-sized certificates are already known.