グループテスト
↑ In fact it is possible to do much better. For example, Li's s {\displaystyle s} -stage algorithm gives an explicit construction were t ≤ e log 2  e d log 2  ( n / d ) {\displaystyle t\leq {\frac {e}{\log _{2}e}}d\log _{2}{(n/d)}} .
↑ Alternatively y {\displaystyle \mathbf {y} } can be defined by the equation y := M x {\displaystyle \mathbf {y} :=M\mathbf {x} } , where multiplication is logical AND ( ∧ {\displaystyle \wedge } ) and addition is logical OR ( ∨ {\displaystyle \vee } ). Here, y {\displaystyle \mathbf {y} } will have a 1 {\displaystyle 1} in position i {\displaystyle i} if and only if ( M ) i , j {\displaystyle (M)_{i,j}} and x j {\displaystyle \mathbf {x} _{j}} are both 1 {\displaystyle 1} for any j {\displaystyle j} .
That is to say, there is no direct knowledge of what the entries of x {\displaystyle \mathbf {x} } are, other than that which can be inferred via some series of 'tests'. This leads on to the next definition.
Let x {\displaystyle \mathbf {x} } be an input vector. A set, S ⊆ { 1 , 2 , ... , n } {\displaystyle S\subseteq \{1,2,\dots ,n\}} is called a test. When testing is noiseless, the result of a test is positive when there exists j ∈ S {\displaystyle j\in S} such that x j = 1 {\displaystyle x_{j}=1} , and the result is negative otherwise.
Therefore, the goal of group testing is to come up with a method for choosing a 'short' series of tests that allow x {\displaystyle \mathbf {x} } to be determined, either exactly or with a high degree of certainty.
Group testing was first studied in the combinatorial context by Li in 1962, with the introduction of Li’s s {\displaystyle s} -stage algorithm. Li proposed an extension of Dorfman's '2-stage algorithm' to an arbitrary number of stages that required no more than t = e log 2  ( e ) d log 2  ( n ) {\displaystyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)} tests to be guaranteed to find d {\displaystyle d} or fewer defectives among n {\displaystyle n} items. The idea was to remove all the items in negative tests, and divide the remaining items into groups as was done with the initial pool. This was to be done s − 1 {\displaystyle s-1} times before performing individual testing.