[Date Prev][Date Next][Date Index]
Talk: "On complexity problems for disjunctive normal forms"
Date: Thursday, October 21th 2004, 11:30 s.t.
Place: Seminarroom of the Institute, Favoritenstraße 9-11/1842, 3rd floor
(when you leave the elevator turn left, go through the corridor, the
entrance is on the right side)
On complexity problems for disjunctive normal forms
We discuss some recent results on DNF.
1) The DNF exception problem: How much can the DNF size go up
if it is `revised' by changing some true points to false?
2) Extremal functions for the number of prime implicants:
It is known that a k-term DNF can have at most 2^k - 1 prime
implicants and this bound is sharp. We give an explicit
description of all functions having this many prime implicants
(as functions represented by a kind of decision tree).
3) Superpolynomial separation between disjoint (CNF,DNF) size
and decision tree size: A DNF is disjoint if every two terms
contain a complementary pair of literals. We also mention some
related results which contribute to a comprehensive picture
of the relationships between the different complexities of
disjoint and general DNF and decision trees in the search tree,
resp., decision tree models.
Joint work with Dhruv Mubayi, Bob Sloan, Balazs Szorenyi and Yi Zhao.