In mathematics, a logical matrix may be described as d"-disjunct and/or d"-separable. These concepts play a pivotal role in the mathematical area of non-adaptive group testing.
In the mathematical literature, "d"-disjunct matrices may also be called super-imposed codes or "d"-cover-free families.
According to Chen and Hwang (2006),
The following relationships are "well-known":
Concrete examples.
The following formula_8 matrix is 2-separable, because each pair of columns has a distinct sum. For example, the boolean sum (that is, the bitwise OR) of the first two columns is formula_9; that sum is not attainable as the sum of any other pair of columns in the matrix.
However, this matrix is not 3-separable, because the sum of columns 1, 2, and 3 (namely formula_10) equals the sum of columns 1, 4, and 5.
This matrix is also not formula_11-separable, because the sum of columns 1 and 8 (namely formula_12) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be formula_1-separable for any formula_14.
formula_15
The following formula_16 matrix is formula_17-separable (and thus 2-disjunct) but not 3-disjunct.
formula_18
There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:
However, the sum of columns 2, 3, and 4 (namely formula_10) is a superset of column 1 (namely formula_12), which means that this matrix is not 3-disjunct.
Application of "d"-separability to group testing.
The non-adaptive group testing problem postulates that we have a test which can tell us, for any set of items, whether that set contains a "defective" item. We are asked to come up with a series of groupings that can exactly identify all the defective items in a batch of "n" total items, some "d" of which are defective.
A formula_3-separable matrix with formula_22 rows and formula_23 columns concisely describes how to use "t" tests to find the defective items in a batch of "n", where the number of defective items is known to be exactly "d".
A formula_3-disjunct matrix (or, more generally, any formula_1-separable matrix) with formula_22 rows and formula_23 columns concisely describes how to use "t" tests to find the defective items in a batch of "n", where the number of defective items is known to be no more than "d".
Practical concerns and published results.
For a given "n" and "d", the number of rows "t" in the smallest "d"-separable formula_28 matrix may (according to current knowledge) be smaller than the number of rows "t" in the smallest "d"-disjunct formula_28 matrix, but in asymptotically they are within a constant factor of each other. Additionally, if the matrix is to be used for practical testing, some algorithm is needed that can "decode" a test result (that is, a boolean sum such as formula_30) into the indices of the defective items (that is, the unique set of columns that produce that boolean sum). For arbitrary "d"-disjunct matrices, polynomial-time decoding algorithms are known; the naïve algorithm is formula_31. For arbitrary "d"-separable but non-"d"-disjunct matrices, the best known decoding algorithms are exponential-time.
Porat and Rothschild (2008) present a deterministic formula_31-time algorithm for constructing a "d"-disjoint matrix with "n" columns and formula_33 rows.