Colloquia: Victor W. Marek/Department of Computer Sciences University of Kentucky Autarkies their properties and use in TAY 3.128

Contact Name: 
Jenna Whitney
Apr 6, 2006 5:00pm - 6:00pm

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
on the complexity of algorithms than ones that are obtained fro

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.