Vereshchagin
Le Jeudi 18 Octobre 2001 à 14h30
au LRI,
Salle 101
(Lomonosov Moscow State University)
On cross intersecting families and
P vs NP
coNP in decision tree model
Résumé/Abstract :
Assume that any set in a finite family A of n-element sets
intersects with any sets in a finite family B of n-element
sets. Then there is an element that belongs to at least 1/2n fraction
of sets in A and to at least 1/2n fraction of sets in B.
This combinatorial statement has an interesting application to computational
complexity of decision trees.