SatisfactionProblems.hpp File Reference

Plans for satisfaction problems (in general) More...

Go to the source code of this file.

Detailed Description

Plans for satisfaction problems (in general)

  • The set of all variables in some context is Var.
  • However, it seems to be to use this concept only "implicitely".
Value set
  • The set of all possible values for the variable in Var (in some context) is Val.
  • Again, likely this is best only used implicitely.
Total assignments
  • One total assignment: f: Var -> Val, just treated as a function which can be evaluated on all elements of Var (while otherwise behaviour is undefined) and yields and element of Val.
  • The set of all total assignments is TASS (again, likely only to be used implicitely).
Domain association and allowed total assignments
  • A domain association is a special kind of condition, given by a set of signed literals, which either specify the set of allowed or forbidden values for some variables.
  • So a "domain association" is nothing than a partial assignment, and perhaps we should drop this notion at all --- there is a set of variables and its associated value set (the set of possible values for any variable), and if one wishes to introduce restricted variable domains, then a partial multiassigment is to be considered ?!
  • So a "problem" typically is given as a pair (P, phi), where P is a problem instance and phi is a partial multiassignment. One can speak of phi as the "domain association".
The notion of "condition"
  • See ComputerAlgebra/Satisfiability/Lisp/ConstraintProblems/plans/Conditions.hpp for the realisation of these concepts.
  • A condition is a map from TASS to {false,true}.
  • A solution is a total assignment evaluating to true; perhaps better, a "satisfying assignment", since as interesting (in general) are the "falsifying assignments".
  • So for a most general condition, all what can be done (at first) is to run through all total assignment; this is the "oracle model".
  • The fundamental task (for the theory of generalised satisfiability(!)) for a condition P (like "problem"):
    Represent P^{-1}(false) and P^{-1}(true).
    "Representation" of sets of total assignments can mean different things:
    1. Measure the set, either with its natural probability in the product probability space TASS, or just classifying it as empty or non-empty.
    2. Give a power-clause-set representation, i.e., a signed CNF-representation of P^{-1}(false) resp. a signed DNF-representation of P^{-1}(true), where we have several refinements:
      1. A prime power-clause-set, that is, a prime signed CNF resp. a prime signed DNF: no clause can be replaced by a smaller one (where for CNF-clauses C,D it is C smaller than D iff C semantically implies D).
      2. A hitting power-clause-set, that is, a hitting signed CNF resp. a hitting signed DNF: each pair of clauses clash, i.e., the sets of represented total assignments are disjoint.
      3. A special case of a hitting clause-set is a full clause-set, where each pair of clauses contains (exactly) the same variables. A full DNF representation is just how "constraint satisfaction problems" are commonly understood.
      The power-clause-set can be given either explicitly listed, or "online", one clause after another.
    3. Give a BDD representation; this represents directly P^{-1}(false) and P^{-1}(true) together.
    In each case, also partial information is important:
    1. Regarding measurement, we can have
      1. upper bounds
      2. lower bounds
      3. approximations
    2. For power-clause-set representations, we can have sub-clause-sets.
    3. BDD representations are harder to make partial, since it represents satisfying and falsifying assignments at the same time.
  • Given a partial multi-assignment phi, the most fundamental operation is the application phi*P, which is the condition which is false for total assignments f not covered by phi, and P(f) otherwise.
    1. So phi*P in general is just the pair (P,phi) explained above as "problem". The fact, that a variable v has been eliminated, since phi assigned a specific value to v (in general phi might only restrict v to a subset of its domain), can be recorded explicitely; forgetting this explicit recording, we arrive at the usual notion of the application of a partial assignment to a generalised clause-set.
    2. For clause-sets we can forget the variables which already have been assigned, since we can define a composition of partial assignments where the first assignments always renders a later assignment void; however in the present of multi-assignments this is not possible.
    3. This notion of phi*P is satisfiability centered, we also need phi*'P, which renders every total assignment not covered by phi true.
  • Now the above fundamental task is to be considered for phi * P (and phi *' P).
  • Compare with ComputerAlgebra/Satisfiability/Lisp/plans/PartialAssignments.hpp.
  • The "point of view of satisfiability" is the emphasise on partial assignments and clause-sets relative to a notion of "literal":
    1. A "literal" is a special condition such that "x implies y" can always be decided "very quickly" for literals x, y, and such that all fundamental tasks can be performed "very quickly".
    2. A "clause" is a finite set of literals, either interpreted as CNF-clause ("or") or as DNF-clause ("and"). There are three normalising conditions on clauses:
      1. No literal implies another literal.
      2. Stronger: Two literals cannot be combined into an equivalent literal.
      3. The clause does not represent a constant condition.
      It must hold for normalised clauses, that a CNF-clause C implies a CNF-clause D iff for all x in C there is a literal y in D such that x implies y. This restricts the notion of literals.
    3. "Parallel" to clauses one has partial assignments, which semantically correspond to DNF-clauses for satisfiability testing, and to CNF-clauses for falsifiability testing, but which have a different meaning: Partial assignments steer the backtracking process.
    4. Clause-sets are set of clauses (with finitely many variables).
    5. The fundamental tasks are solved by returning clause-sets, where typically only the cumulative k-section (all clauses up to length k) is of interest: k = 0 is just the sat-problem, k = 1 yields all implied unit-clauses (or some of them), and so on.
    6. One problem is, how to call these generalised "literals", "clauses", "clause-sets":
      • "abstract" literals, ... ?
      • "active" literals, ... ?
      As examples for such "abstract literals" we have already
      1. boolean literals
      2. (generalised) literals
      3. signed (or power-) literals.
      See ComputerAlgebra/Satisfiability/Lisp/plans/Literals.hpp.
    7. For an "effective condition" we have one associated literal type, and "most" basic tasks can be solved "efficiently" (generalised clauses).
      1. These would be the "active clauses".
      2. While the fundamental tasks can be performed in constant time for active literals, now we can do then in polynomial time.
      3. Having a OBDD representation should mean that we have an active clause.
      4. And perhaps also representations as hitting clause-sets imply "active clause".
      This kind of discussion needs clean-up (should be moved to Satisfiability/ProblemInstances/concepts/plans).
    8. A "condition set" is a set of effective conditions, either a conjunction or a disjunction (generalising clause-sets).
    9. Finally we have "alliances of condition sets", which are combinations of condition sets, allowing for different literal types to be used.
Constructing conditions
  • We have the propositional connectives.
  • And the quantifiers "for all" and "exists".
Functions for conditions
  • var(P) yields a set of variables, such that P does not depend on variables not in var(P).
  • A set of variables V is a "backdoor" for condition P regarding one of the above fundamental tasks, if for every assignment of values to the variables in V the task can be "efficiently" solved. The knowledge about some such backdoors is important structural information, either given with the problem instance itself (a priori), or computed later (a posteriori). Given some set of variables, an interesting task is to find a smallest backdoor (from the ones we know) which includes this set.
    1. Consider as an example the condition given by AES (see Cryptanalysis/plans/Rijndael.hpp): This is a condition on n+n+k boolean variables, where n is block length and k the key length. Given n+?+k or ?+n+k variables, the remaining variables are uniquely determined and can be efficiently computed by the encryption resp. decryption algorithm.
    2. So we have two backdoors for computing a full DNF representation.

Definition in file SatisfactionProblems.hpp.