[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

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.