Tag Archives: 3SAT

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.

Consistency of Database Frequency Tables

The end of the Storage and Retrieval section is in sight!

The problem: Consistency of Database Frequency Tables.  This is problem SR35 in the appendix.

The description: I find G&J’s definition confusing, so this definition borrows a lot from the paper by Reiss that has the reduction. 

We have a set of “characteristics” (attributes) A.  Each attribute a in A has a domain Da.  A database is a set of “Objects” (tuples) O1..On where each object defines a value for each characteristic. (The result is a two-dimensional table where rows are objects and columns are attributes). We can define a frequency table  for each pair of attributes a and b in A.  The table has |Da| rows and |Db| columns, and each entry (x,y)  is “supposed” to represent the number of tuples in O that have x for its A attribute and y for its B attribute.

What the problem is asking is: Given a set of tables and a database table V, can we find a way to map the attributes in A to the tables such that the tables actually represent the frequencies in the database?

Example:
Since you need a frequency table for each pair of attributes, here is an example with 3 attributes, each taking 2 posible values.  Attribute a’s domain is {0,1}, b’s is {a,b}, and c’s is {>, <}.  Our set of objects is:

  • (0,a,>)
  • (0,b,>)
  • (1,b,>)
  • (0,b,<)

If we are handed a set of 3 frequency tables:

C1 vs C2:

1 0
2 1

C1 vs C3:

0 1
1 2

C2 vs C3:

1 2
0 1

These frequency tables are accurate if C1 is attribute a, C2 is attribute b, and C3 is attribute c.

The reduction: From 3SAT.  (Actually, this might be from regular CNF-SAT,  but there is no reason not to restrict the input to 3 literals per claue).  We take a SAT instance with p clauses and q variables and bake a database with 2 objects per variable (one for positive, one for negative) and p*q extra objects. We have one attribute per clause (“CLi“), one attribute per variable (“VRi“) and “VALUE” (which holds the truth value of the object in the final setting).  The frequency tables are set up to ensure that each variable has one value setting(true or false) and each clause is made true.  The way to make the database consistent with the table is to find a way to map the variables in the database to the tables in a way to make the formula satisfiable.

Difficulty: 5, because the reduction isn’t that hard to follow, or come up with, once you get how the frequency tables work.  But unlike most 5’s, I don’t think I’d assign it as a homework problem, because of how much extra work it would take to explain the frequency tables in the first place.

Tableau Equivalence

This is another problem where I’m going to supplement G&J’s problem description with definitions from the paper by Aho, Sagiv, and Ullman that has the reduction:

The problem: Tableau Equivalence.  This is problem SR32 in the appendix.

Definitions: Given a set of attributes A, and set F of ordered pairs of subsets of A (functional dependencies).  Most database queries ask for certain attributes (these are the “distinguished variables” in the G&J definition) that fill requirements defined by other attributes and values (anything new added are the “undistinguished variables” in the G&J definition).

A Tableau is a matrix that represents these attributes and variables.  The columns correspond to attributes, and the rows correspond to tuples that are returned by the query.   The first row of the tableau is the “summary” of the tableau and holds the distinguished variables we want to return (and possibly some constants)

Tableau example: This example comes from p. 223 of the paper.  For the query:

Find all values for variables a1 and a2 such that we can find values for variables b1 through b4 such that the following strings are all in our database instance (called “I” in the paper):  By convention in the paper, a variables are distinguished variables, and b variables are undistinguished.

  • a1b1b3
  • b2a21  (That’s the constant 1 at the end)
  • b2b1b4

If I was the strings {111,222, 121}, then all assignments of 1’s and 2’s to a1 and a2 work:

  • If a1 and a2 are both 1, then assigning all b variables to 1 generates the string 111 in all 3 cases above, which is in I
  • If a1 = 1 and a2 = 2, then we can assign 2 to b1 and 1’s to all over b variables and get 121 in all cases, which is in I.

Before I get to the 2 harder cases, let me show the tableau:

A B C
a1 a2
a1 b1 b3
b2 a2 1
b2 b1 b4

The first row lists the attributes we’re considering (a1 comes from A and only occurs in the first spot in the result string, a2 comes from B and only occurs in the second spot in the result string.  Our query doesn’t want any variables from C.  The summary lists the variables from the attributes that form our distinguished variables.

The rows below the summary show how to build legal strings (like my list above).

So now we can use the tableau to help see how to find legal values to the variables:

  • If a1 = 2 and a2 = 1, then we need to assign a 1 to b2 to make the second(non-summary) row 121.  We also need to assign a 2 to b1 and b3 to make the first row 222.  This means we need to assign a 1 to b4 to make the bottom row 121.
  • If a1 and a2 are both 2, we need to set b2 to 1 to make the middle row 121.  We need to set b1 and b3 to 2 to make the top row 222.  This means we need to set b4 to 4 to make the bottom row 121.

The problem: Given two Tableaux T1 and T2 which share the same A, F, X, and Y sets (as defined above), are they equivalent?  That is, do they generate the same sets of legal values for their distinguished variables for all possible I sets?

Example: This gets tricky, partially because of the need to worry about “all possible I sets”, and partially because adding functional dependencies makes things equivalent in subtle ways.  Here is the example from page 230 of the paper:

A B C D
a1 a2 a3 a4
a1 b1 b2 b3
b4 b1 a3 b5
a1 a2 b6 b7
a1 b8 b9 a4

If we have the functional dependencies B->A and A->C are true.  Then all strings with b1 in the second character must have the same value (a1) in the first character.  Similarly, A->C implies that the entire third column can be replaced by a3.  This gives us the equivalent tableau:

A B C D
a1 a2 a3 a4
a1 b1 a3 b3
a1 b1 a3 b5
a1 a2 a3 b7
a1 b8 a3 a4

And also, if the only difference between two rows is that one row has nondistinguished variables that don’t appear anywhere else, that row can be eliminated.  So we can get rid of the first row (with b3) because it is just like the second (with b5) But then we realize that the a1b1a3b5 row only differs from the row below it in b1 and b5 which now only appear in that row.  So we can remove that row too, to get the equivalent:

A B C D
a1 a2 a3 a4
a1 a2 a3 b7
a1 b8 a3 a4

 

Reduction: From 3SAT.  Given a formula, we build 2 tableaux.  The set A will have 1 attribute for each clause and variable in the formula.  The clause variables will be distinguished variables.  Our T1 tableau will be set up as follows:

For each clause, we will set a common undistinguished variable for the 3 variables in the row (so each clause that has that variable will have the same undistinguished variable in that column), and separate (only used once) undistinguished variable in the other columns.

The T2 tableau will have 7 rows for each row in T1.  In T2 we replace the common undistinguished variables with 7 sets constants(0 or 1)  that are the ways to set the variables to make the clause true.

They prove a bunch of lemmas after this, but it boils down to: If we have a truth assignment for the formula, we can map that to the tableau by setting the common variables in T1 to the truth values in the assignment.  All clauses will be true in both T1 and T2.  If the tableaux are equivalent, then we must have found a way to set those common variables, and that gives us a truth assignment for the formula.

Difficulty: 7.  This isn’t that hard of a reduction.  Even the lemmas aren’t too hard, though they do depend on a paper’s worth of previous results in equivalences (like the functional dependency thing I did in the example).  But there is a ton of definitions to get through before you can start.

Protected: Hitting String

This content is password protected. To view it please enter your password below: