1
$\begingroup$

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
  • Label to jump to
  • 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 reflexes <= 4 jump to label_bitten_by_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
if 0 <= 0 jump to label_healed_snake_bite
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
$\endgroup$
1
  • $\begingroup$ Also NP-hard because we can easily translate a SAT formula to a computer in this model. $\endgroup$
    – aschepler
    Commented May 29 at 0:22

1 Answer 1

1
$\begingroup$

The problem is NP-complete.

It is easy to show that it is NP-hard. For instance, it is easy to encode 3SAT in this language.

It is trickier to show that it is in NP. It is tempting to say that a certificate for a yes-instance just needs to list the initial value of all registers, but this is not correct, as it is possible that the only accepting solution requires integers that take exponential length to write down. So such a simple certificate doesn't suffice.

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.

$\endgroup$
2
  • $\begingroup$ Thank you, but I'm not sure what you mean by "Note that when you focus on a single straight-line path, you can express everything in ILP:". Are you associating an ILP to every instruction? $\endgroup$ Commented May 29 at 6:22
  • $\begingroup$ @NaomiZhang, I mean there exists an input that follows that path (ending in accept) iff there is a satisfying solution to the corresponding ILP. I am associating a linear inequality to each conditional branch in the path; the ILP is the system of all such linear inequalities. $\endgroup$
    – D.W.
    Commented May 29 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .