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 [1] or d-cover-free families. [2]
According to Chen and Hwang (2006), [3]
The following relationships are "well-known": [3]
The following 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 ; 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 ) equals the sum of columns 1, 4, and 5.
This matrix is also not -separable, because the sum of columns 1 and 8 (namely ) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be -separable for any .
The following matrix is -separable (and thus 2-disjunct) but not 3-disjunct.
There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:
columns | boolean sum | columns | boolean sum | |
---|---|---|---|---|
none | 000000 | 2,3 | 011110 | |
1 | 110000 | 2,4 | 101101 | |
2 | 001100 | 3,4 | 111011 | |
3 | 011010 | 1,2,3 | 111110 | |
4 | 100001 | 1,2,4 | 111101 | |
1,2 | 111100 | 1,3,4 | 111011 | |
1,3 | 111010 | 2,3,4 | 111111 | |
1,4 | 110001 |
However, the sum of columns 2, 3, and 4 (namely ) is a superset of column 1 (namely ), which means that this matrix is not 3-disjunct.
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 -separable matrix with rows and 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 -disjunct matrix (or, more generally, any -separable matrix) with rows and 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.
For a given n and d, the number of rows t in the smallest d-separable matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct matrix, but in asymptotically they are within a constant factor of each other. [3] 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 ) 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 . [4] For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time. [3]
Porat and Rothschild (2008) present a deterministic -time algorithm for constructing a d-disjoint matrix with n columns and rows. [5]
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 [1] or d-cover-free families. [2]
According to Chen and Hwang (2006), [3]
The following relationships are "well-known": [3]
The following 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 ; 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 ) equals the sum of columns 1, 4, and 5.
This matrix is also not -separable, because the sum of columns 1 and 8 (namely ) equals the sum of column 1 alone. In fact, no matrix with an all-zero column can possibly be -separable for any .
The following matrix is -separable (and thus 2-disjunct) but not 3-disjunct.
There are 15 possible ways to choose 3-or-fewer columns from this matrix, and each choice leads to a different boolean sum:
columns | boolean sum | columns | boolean sum | |
---|---|---|---|---|
none | 000000 | 2,3 | 011110 | |
1 | 110000 | 2,4 | 101101 | |
2 | 001100 | 3,4 | 111011 | |
3 | 011010 | 1,2,3 | 111110 | |
4 | 100001 | 1,2,4 | 111101 | |
1,2 | 111100 | 1,3,4 | 111011 | |
1,3 | 111010 | 2,3,4 | 111111 | |
1,4 | 110001 |
However, the sum of columns 2, 3, and 4 (namely ) is a superset of column 1 (namely ), which means that this matrix is not 3-disjunct.
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 -separable matrix with rows and 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 -disjunct matrix (or, more generally, any -separable matrix) with rows and 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.
For a given n and d, the number of rows t in the smallest d-separable matrix may (according to current knowledge) be smaller than the number of rows t in the smallest d-disjunct matrix, but in asymptotically they are within a constant factor of each other. [3] 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 ) 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 . [4] For arbitrary d-separable but non-d-disjunct matrices, the best known decoding algorithms are exponential-time. [3]
Porat and Rothschild (2008) present a deterministic -time algorithm for constructing a d-disjoint matrix with n columns and rows. [5]