KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №8, Moscow, 1999
Authors: Sachkov V.N.
Random set partitions
Abstract:
The first part of the article presents an overview of research history in the field of random set partitions, and describes a series of objects that can be treated as such partitions. The second part present's the author's results on contradictory partitions in application to the study of read-once conjunctive normal forms. We also consider m-set partitions that have a prescribed number of blocks in common with a fixed partition as well as random partitions with a prescribed number of blocks. We present a formula for the number of read-once conjunctive normal forms of a special type and an asymptotic estimate for the number of read-once conjunctive normal forms that depend essentially on every variable. The article also includes a formula for the size of the Boolean function subclass where the solution of corresponding equation systems has polynomial complexity.
Keywords:
random set partitions, fixed partition, contradictory partition, read-once conjunctive normal forms
Publication language: russian,  pages: 22 (p. 33-54)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Sachkov Vladimir Nikolaevich,  Академия криптографии РФ