Our old friend Bounded PCP is back for this reduction. What I actually originally wrote in that post was wrong (what I thought was the PCP reduction was actually their reduction for today’s problem), and I modified that post a little to reflect that. I’m still sad that I can’t find an easy Bounded PCP reduction, but at least for today, all we need is the knowledge that it’s NP-Complete.
The problem: Non-Freedom for Loop-Free Program Schemes. This is problem PO19 in the appendix.
The description: Suppose we have a set of instructions without loops (so just assignment of a variable, if statements that jump to other instructions, and halt. Kind of like our Ianov Scheme instructions, but possibly allowing more than one variable). “No loops” also means that our if statements cannot create a cycle.
Is there a directed path through this set of instructions that can never be followed by any actual computation? (A program is “free” if all paths are reachable, so “non-free” means some path is not reachable).
Example: Here’s a very simple program:
1: if p then I2 else I3
2: x = 1
3: x = 2
If “p” is a predicate that is always true, than the path I1-I3 can never be realized and the program is non-free. If p can be true or false, then all paths are possible and the program is free (and so this “non-free” instance is a “no”)
Reduction: As I alluded to at the start, Constable, Hunt, and Sahni reduce from Bounded PCP. The idea is that they will take a BPCP instance and build a program where all paths are possible if and only if the BPCP instance is unsolvable. The general idea is to build a scheme where we have 2 variables x1 and x2, which correspond to the two BPCP strings we are building. At the end of the scheme, we have two predicates: P(x1) and P(x2). If x1 and x2 are the same (which means we have built the same string) then we can’t get to a path that has true for one and false for the other.
The problem is that we could get that path if we choose a bad set of strings to make x1 and x2, and I’m not sure how we avoid that. Here’s the picture they put in the paper basically as the entire proof:
I think maybe it might be an example for an instance of BCPP bounded at 1 string from each side (which is why the end case is a set of P2 predicates), but they don’t say and I’m not sure. It’s not helped by the fact that they use “i” for the number of substrings used, and for an index in one of the strings, or that their font has the letter “l” look the same as the number “1”, or that they don’t explain anywhere why we have 2 levels of predicates, or what those predicates are supposed to be testing for. I think the top predicates (the P1 ones) are choosing whether we take substring 1,2, and so on to build our solution. But that means these “h” functions are appending the next character onto the string we’re building, and that’s not said anywhere either.
So, yeah, I don’t know what about this diagram doesn’t let me take incorrect choices for the BPCP problem, leading to a different x1 and x2, and creating a path that way. I definitely wish the paper had more explanation.
Difficulty: 8. I’m not terribly filled with confidence that my explanation is right, because the explanation in the proof doesn’t really explain much to me. Am I missing something?