Conjunctive Satisfiability with Functions and Inequalities

The problem: Conjunctive Satisfiability with Functions and Inequalities.  This is problem LO16 in the appendix.

The description: Given a set U of variables, a set F of functions on 1 variable, a collection C of clauses connecting 2 statements U and V with either:

  • >
  • =

.. and U and V are either

  • A constant 0 or 1
  • f(0) or f(1) for some f in F
  • f(u) for some u in U, and some f in F

.. can we find integer values to all variables in U that make all of the clauses in C true?

Example:

Let F = {f,g}, f(x) = x2, g(x) = x3.  Let U = {a,b}

Let our clauses be:

  • f(a) > g(b)
  • a ≤ b

We can satisfy the clauses by choosing a = -2 and b = 1.  If we had another clause that said a > 2 then the clauses would not be satisfiable.

Reduction: G&J point you to an “unpublished manuscript” by Pratt, which I found online.  Some people who reference this paper just call it a “manuscript” and some people call it a Tech Report from MIT.  I looked at the MIT tech report list and couldn’t find this.  But that doesn’t really mean anything since not all of the tech reports from the 1970s have been indexed online at a lot of places.  Anyway, you can find the paper online.

I do wish the paper had gone through an editing pass because it has what to me look like bugs or ambiguities.  Maybe I’m not understanding things, though.

Here’s the basic idea: Given a Satisfiability formula P, build a formula H(P) in this new construction.  The clauses are:

  • Each variable has to be 0 or 1 (so, 0 ≤ u and u ≤1 for all u in U)
  •  Each literal i has a distinct function fi.  If the literal is positive then we will be using fi(0) in what’s to come.  If the literal is negative then we will be using fi(1) in what’s to come.
  • If 2 literals P and Q are connected by ∧, create clauses for the inequalities:
    • fp(0 or 1) ≤ fq (0 or 1)  (0 or 1 depending on whether the literal is positive or negative
    • fp(P) ≤ fq(Q)
  • If 2 literals P and Q are connected by ∨ (the paper uses the | symbol for “or” which I’d never seen before), create a clause for the inequalities:
    • fp(P) ≤ fq (0 or 1)
  • f0 (0 or 1) > fP(P) for some(?) (maybe all?) variable P.

In the description, Pratt says that they’re building a graph to represent the formula connected by inequalities.  If we hit a ∧ symbol, it will connect the graphs of the two parts of the formula together with a parallel connection, so that there is always a way to get from one subgraph to another.  If we hit a ∨ symbol, the subgraphs are connected by a series connection.  He says “We hope that this informal discussion will make a more formal argument unnecessary”.  I for one wish there was some more detail here.

The examples he uses to explain what’s happening are just on the trivial formulas “a” and “a ∧ ~a”.  I can sort of see how the clauses he creates come out of those formulas.  But since none of his examples use the ∨ operation, or use more complex clauses, it’s hard for me to see what happens there.  I’m probably missing something.

It also seems like he wants to let the definition of the functions be part of the satisfiability argument (i.e. not only do we have to find truth values for all of he variables, we also have to create functions that make all of the clauses become true), which seems to not be the definition provided in G&J.

Difficulty: 8.  There is probably a much simpler reduction out there.  I wish I knew what it was.

Leave a Reply

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