Affiliations: Max Planck Institute for Software Systems (MPI-SWS), Germany. dch@mpi-sws.org | Moscow State University, Russia. fedorovavs@cs.msu.ru | Moscow State University, Russia. dm6@cs.msu.ru
Note: [] Part of this research was done while Dmitry Chistikov was affiliated with Moscow State University. Address for correspondence: MPI-SWS, Paul-Ehrlich-Str. 26, 67663 Kaiserslautern, Germany
Abstract: A certificate of non-membership for a Boolean function f with respect to a class ๐, f โ ๐, is a set S of input strings such that the values of f on strings from S are inconsistent with any function h โ ๐. We study certificates of non-membership with respect to several classes of read-once functions, generated by their bases. For the basis {&, โจ, $\neg$}, we determine the optimal certificate size for every function outside the class and deduce that 6 strings always suffice. For the same basis augmented with a function x1 ... xs โจ ${\bar x}_1$ ... ${\bar x}_s$, we show that there exist n-variable functions requiring ฮฉ(nsโ1) strings in a certificate as n โ โ. For s = 2, we show that this bound is tight by constructing certificates of size O(n) for all functions outside the class.
Keywords: certificate of non-membership, read-once function
