Linear Bounded Automaton Acceptance

The next problem in the appendix is a doozy, and it needs this reduction, which is in Karp’s paper.

The problem: Linear Bounded Automaton Acceptance.  This is problem AL3 in the appendix.

The description: Given a Linear Bounded Automaton L, and a string x, does L accept x?

Example: A well-known context-sensitive language is L= anbncn.  If we had a definition for an LBA that accepts a string L, and a string such as aabbccc, the LBA should say “no” on this instance.  But if our string was aabbcc, the LBA would say “yes”.

Reduction: G&J say this is a “Generic reduction”, and I can see why.  Let me try to add some explanation and put it into something more like what we’re used to:

We start with a known NP-Complete (not NP-Hard) problem.  Let’s say 3SAT. 3SAT is in NP, which means we have a non-deterministic Turing Machine that takes an instance x and solves 3SAT in polynomial time, let’s say p(|x|).   Let’s assume that the alphabet of this Turing Machine is {0,1}.

Given this instance x of 3SAT, we build the following context-sensitive language (and it’s implied that we can go from there to an LBA in polynomial time).  {#p(log(|x|) x #p(log (|x|)} over the alphabet {0,1,#}.  So we have a number of # symbols before and after x equal to the polynomial on the log of the input.

To be honest, I’m not sure why you need the log here.  I think you can get away with just having p(|x|) symbols on each side, and the total length of the LBA acceptance instane is still polynomial in |x|.  The idea is that since we know that the TM completes in time p(|x|), it can only ever move its head p(|x|) tape symbols to the left or right before it runs out of time.  So we can use that as the “bound” on the LBA.

So, if our LBA uses the exact same states and transitions as the non-deterministic Turing Machine that solved 3SAT, we now have our LBA accept x exactly when x was satisfiable.

The reason this is a “generic” reduction is that nothing we did had anything to do with 3SAT specifically.  We could do this process for any problem in NP.  It’s more useful if we start with an NP-Complete problem, but we could do this for things in P as well since they are also in NP.

Difficulty: 5, mainly because this is a weird way of doing things, and Linear Bounded Automata are things that often get short shrift in Theory of Computation classes.

4 responses to “Linear Bounded Automaton Acceptance

  1. But I do not know whether this one is in NP? “Linear space” sounds badly for non-deterministic poly time!

  2. G&J have it listed as “not known to be in NP”. Which I think makes sense given what little I know about how LBA’s work. Certainly, you can imagine how a machine that travels over N tape cells can easily have 2^N state configurations..

  3. Thanks. And I think this problem is PSPACE-complete by the same reduction here. As already noticed in your post that SAT can be replaced by any problem in poly space.
    Btw, can I the archive passwd?

Leave a Reply

Your email address will not be published. Required fields are marked *