کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6423786 1632593 2011 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On Extremal k-CNF Formulas
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On Extremal k-CNF Formulas
چکیده انگلیسی

The average sensitivity of a Boolean function is the expectation, given a uniformly random input, of the number of input bits which when flipped change the output of the function. A k-CNF is a CNF in which every clause contains at most k literals. It has recently been shown by the author [Amano, K., Tight Bounds on the Average Sensitivity of k-CNF, Theory of Computing, 7(4) (2011), 45-48] that the average sensitivity of a k-CNF is at most k. This bound is tight since the parity function on k variables has the average sensitivity k.In this paper, we consider the problem to determine the extremal formulas achieving this bound. We give a class of such formulas that contains a double exponential (in k) number of non-isomorphic ones. This class captures all formulas, with only one exception, that we have obtained so far. We also give the complete list for k=2 and 3 as well as several structural properties of such extremal formulas.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 38, 1 December 2011, Pages 37-42
نویسندگان
,