Despite much work over the previous decade, the Satisfiability Threshold
Conjecture remains open. Random k-SAT, for constant k >= 3,
is just one family of a large number
of constraint satisfaction problems that are conjectured to have exact
satisfiability thresholds, but for which the existence and location of these
thresholds has yet to be proven.
Of those problems for which we are able to prove
an exact satisfiability threshold, each seems to be fundamentally different
than random 3-SAT.
This thesis defines a new family of
constraint satisfaction problems with constant size
constraints and domains and which
contains problems that are NP-complete and a.s.\ have exponential
resolution complexity. All four of these properties hold for k-SAT, k >= 3,
and the
exact satisfiability threshold is not known for any constraint
satisfaction problem
that has all of these properties. For each problem in the
family defined in this
thesis, we determine
a value c such that c is an exact satisfiability threshold if a certain
multi-variable function has a unique maximum at a given point
in a bounded domain. We
also give numerical evidence that this latter condition holds.
In addition to studying the satisfiability threshold, this thesis
finds exact
thresholds for the efficient behavior of DPLL using the unit clause heuristic
and a variation of the generalized unit clause heuristic,
and this thesis proves an analog
of a conjecture on the satisfiability of (2+p)-SAT.
Besides having similar properties as k-SAT, this new family of
constraint satisfaction problems
is interesting to study in its own right because it generalizes the
XOR-SAT problem and it has close ties
to quasigroups.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/11192 |
| Date | 30 July 2008 |
| Creators | Connamacher, Harold |
| Contributors | Molloy, Michael |
| Source Sets | University of Toronto |
| Language | en_US |
| Detected Language | English |
| Type | Thesis |
| Format | 1368128 bytes, application/pdf |
Page generated in 0.0015 seconds