April 30: H. Vollmer


Subject: April 30: H. Vollmer
From: Helmut Veith (kgs-owner@dbai.tuwien.ac.at)
Date: Mon Apr 27 1998 - 15:53:36 MET DST


Lecture Announcement
-------------------------

Heribert Vollmer
=================================================
Universitaet Wuerzburg

The complexity of computing optimal assignments of
generalized propositional formulae
------------------------------------------
Thursday, April 30, 14:30

ABSTRACT:

We consider the problems of finding the lexicographically
minimal (or maximal) satisfying assignment of propositional
formulae for different restricted
formula classes. It turns out that for each class from our
framework, the above problem is either polynomial time solvable
or complete for OptP. We also consider the problem of
deciding if in the optimal assignment the largest variable gets
value 1. We show that this problem is either in P or
P^NP complete.

PLACE:

Seminarraum SEM 181A, Institut fuer Informationssysteme,
Paniglgasse 16, 1. Stock, 1040 Wien.

------------------------
Kurt-Goedel-Gesellschaft
Technische Universitaet Wien
Institut fuer Computersprachen E185.2
Resselgasse 3/1, A-1040 Wien

Tel: (+43 1) 588 01/4088
Fax: (+43 1) 504 15 89
email: mailto:kgs@logic.tuwien.ac.at
http://logic.tuwien.ac.at:80/kgs/home.html
listserver: mailto:listproc@dbai.tuwien.ac.at

Mit Unterstuetzung des
Bundesministeriums fuer Wissenschaft und Forschung



This archive was generated by hypermail 2b25 : Thu Apr 06 2000 - 16:19:20 MET DST