[Date Prev][Date Next][Date Index]

*From*: Therese Schwarz <sek@dbai.tuwien.ac.at>*Date*: Fri, 15 Oct 2004 15:04:53 +0200

Date: Thursday, October 21th 2004, 11:30 s.t.

On complexity problems for disjunctive normal forms Gyorgy Turan 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.