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


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.


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

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
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