Speaker Name/Affiliation: Victor W. Marek/Departm

ent of Computer Sciences University of Kentucky

Talk Title: Autark

ies their properties and use

Date/Time: April 6 2006 at 5:00 p.m.

Coffee: 4:45 p.m.

Location: TAY 3.128 - South wall

Host: Warren Hunt

Talk Abstract:
Let F be a collection of clause

s. An autarky for F is a
partial valuation v of propositionsal variabl

es such that whenever
v touches a clause C in F then v satisfies C. Ac

tually this notion
is related to three valued logic of Kleene not two

-valued logic.

Autakies have appealing properties and lead to better
bounds
on the complexity of algorithms than ones that are obtained fro

m
the most important practical algorithm DPLL.

In our presentat

ion we will introduce autarkies present
their fundamental properties a

nd prove two new results. First:
that the problem HA (having autarkies)
is NP-complete and second:
that like in the case of satisfiability s

earch version of HA can be
obtained as an iteration of HA.

The l

ecture will be self-contained. The properties of autarkies
and all rela

ted concepts will be discussed in detail.

The reported research is j

oint with M. Truszczynski of the
same department.