Pruebas de grupo 📖 Wikipedia

En estadística y matemáticas combinatorias, las pruebas de grupo son procedimientos que dividen la tarea de identificar determinados objetos en pruebas sobre grupos de elementos, en lugar de sobre elementos individuales. Estudiada por primera vez por Robert Dorfman en 1943, la comprobación de grupos es un campo relativamente nuevo de la matemática aplicada que puede aplicarse a un amplio abanico de aplicaciones prácticas y es un área activa de investigación en la actualidad.

Un ejemplo conocido de prueba de grupos es el de una serie de bombillas conectadas en serie de las que se sabe que una está rota. El objetivo es encontrar la bombilla estropeada con el menor número posible de pruebas (donde una prueba es cuando alguna de las bombillas está conectada a una fuente de alimentación). Un método sencillo consiste en probar cada bombilla por separado. Sin embargo, cuando hay un gran número de bombillas, sería mucho más eficaz agruparlas. Por ejemplo, conectando la primera mitad de las bombillas a la vez, se puede determinar en qué mitad está la bombilla estropeada, descartando la mitad de las bombillas en una sola prueba.

Los esquemas para llevar a cabo las pruebas en grupo pueden ser simples o complejos y las pruebas implicadas en cada etapa pueden ser diferentes. Los esquemas en los que las pruebas de la etapa siguiente dependen de los resultados de las etapas anteriores se denominan procedimientos adaptativos, mientras que los esquemas diseñados para que todas las pruebas se conozcan de antemano se denominan procedimientos no adaptativos. La estructura del esquema de las pruebas implicadas en un procedimiento no adaptativo se conoce como diseño de agrupación.

Las pruebas de grupo tienen muchas aplicaciones, como la estadística, la biología, la informática, la medicina, la ingeniería y la ciberseguridad. El Proyecto Genoma Humano ha reavivado el interés moderno por estos esquemas de pruebas.^[1]​

A diferencia de muchas áreas de las matemáticas, los orígenes de las pruebas de grupo se remontan a un único informe^[2]​ escrito por una sola persona: Robert Dorfman.^[3]​ La motivación surgió durante la Segunda Guerra Mundial, cuando el Servicio de Salud Pública de Estados Unidos y el Servicio Selectivo se embarcaron en un proyecto a gran escala para eliminar a todos los hombres sifilíticos llamados a filas. La prueba de la sífilis consiste en extraer una muestra de sangre y analizarla para determinar la presencia o ausencia de sífilis. En aquella época, la realización de esta prueba era cara, y analizar a cada soldado individualmente habría sido muy costoso e ineficaz.^[3]​

Suponiendo que haya 𝑛 soldados, este método de análisis conduce a 𝑛 pruebas separadas. Si una gran proporción de personas están infectadas, este método sería razonable. Sin embargo, en el caso más probable de que sólo una proporción muy pequeña de los hombres estén infectados, se puede lograr un esquema de pruebas mucho más eficaz. La viabilidad de un plan de pruebas más eficaz depende de la siguiente propiedad: los soldados pueden agruparse y en cada grupo se pueden combinar las muestras de sangre. La muestra combinada puede analizarse para comprobar si al menos un soldado del grupo tiene sífilis. Esta es la idea central de las pruebas en grupo. Si uno o más de los soldados de este grupo tiene sífilis, se desperdicia una prueba (hay que realizar más pruebas para averiguar de qué soldado o soldados se trata). Por otro lado, si nadie del grupo tiene sífilis, entonces se ahorran muchas pruebas, ya que todos los soldados de ese grupo pueden ser eliminados con una sola prueba.^[3]​

Los elementos que hacen que un grupo dé positivo se denominan generalmente elementos defectuosos (son las bombillas rotas, los hombres sifilíticos, etc.). A menudo, el número total de elementos se denota como 𝑛 y 𝑑 representa el número de defectuosos si se supone que es conocido.^[3]​

Existen dos clasificaciones independientes para los problemas de pruebas en grupo; cada problema de pruebas en grupo es adaptativo o no adaptativo, y probabilístico o combinatorio.^[3]​

En los modelos probabilísticos, se supone que los elementos defectuosos siguen alguna distribución de probabilidad y el objetivo es minimizar el número esperado de pruebas necesarias para identificar la defectuosidad de cada elemento. En cambio, en las pruebas combinatorias de grupo, el objetivo es minimizar el número de pruebas necesarias en el peor de los casos, es decir, crear un algoritmo de minimización, y no se supone que se conozca la distribución de los elementos defectuosos.^[3]​

La otra clasificación, la adaptabilidad, se refiere a la información que puede utilizarse para elegir los elementos que se agrupan en una prueba. En general, la elección de qué elementos probar puede depender de los resultados de pruebas anteriores, como en el problema de la bombilla anterior. Un algoritmo que realiza una prueba y luego utiliza el resultado (y todos los resultados anteriores) para decidir qué prueba realizar a continuación se denomina adaptativo. Por el contrario, en los algoritmos no adaptativos, todas las pruebas se deciden de antemano. Esta idea puede generalizarse a los algoritmos multietapa, en los que las pruebas se dividen en etapas, y cada prueba de la etapa siguiente debe decidirse de antemano, con sólo el conocimiento de los resultados de las pruebas de las etapas anteriores. Aunque los algoritmos adaptativos ofrecen mucha más libertad en el diseño, se sabe que los algoritmos adaptativos de pruebas en grupo no mejoran a los no adaptativos en más de un factor constante en el número de pruebas necesarias para identificar el conjunto de elementos defectuosos.^[3]​^[4]​ Además de esto, los métodos no adaptativos suelen ser útiles en la práctica porque se puede proceder con pruebas sucesivas sin analizar primero los resultados de todas las pruebas anteriores, lo que permite distribuir eficazmente el proceso de pruebas.

Hay muchas formas de ampliar el problema de las pruebas de grupo. Una de las más importantes se denomina pruebas en grupo ruidosas, y aborda un gran supuesto del problema original: que las pruebas no contienen errores. Un problema de pruebas en grupo se denomina ruidoso cuando existe alguna posibilidad de que el resultado de una prueba en grupo sea erróneo (por ejemplo, que salga positivo cuando la prueba no contenía ningún defecto). El modelo de ruido Bernoulli asume que esta probabilidad es una constante, 𝑞, pero en general puede depender del número real de defectuosos en la prueba y del número de elementos probados.^[5]​ Por ejemplo, el efecto de la dilución puede modelarse diciendo que un resultado positivo es más probable cuando hay más defectuosos (o más defectuosos como fracción del número probado), presentes en la prueba.^[6]​ Un algoritmo ruidoso siempre tendrá una probabilidad distinta de cero de cometer un error (es decir, etiquetar mal un elemento).

Las pruebas de grupo pueden ampliarse considerando escenarios en los que hay más de dos resultados posibles de una prueba. Por ejemplo, una prueba puede tener los resultados ${\displaystyle 0,1}$ y ${\displaystyle 2^{+}}$, correspondientes a que no haya ningún defectuoso, un único defectuoso o un número desconocido de defectuosos mayor que uno. En términos más generales, es posible considerar que el conjunto de resultados de una prueba es ${\displaystyle {0,1,\ldots ,k^{+}}}$para algún ${\displaystyle k\in \mathbb {N} }$^[3]​

Otra extensión consiste en considerar restricciones geométricas sobre los conjuntos que pueden someterse a prueba. El problema de la bombilla es un ejemplo de este tipo de restricción: sólo se pueden probar las bombillas que aparecen consecutivamente. Del mismo modo, los elementos pueden disponerse en un círculo o, en general, en una red, donde las pruebas son caminos disponibles en el grafo. Otro tipo de restricción geométrica sería el número máximo de elementos que pueden probarse en un grupo,[a] o que el tamaño de los grupos sea par, etcétera. De forma similar, puede ser útil considerar la restricción de que un elemento determinado sólo pueda aparecer en un número determinado de pruebas.^[3]​

Hay infinitas formas de seguir remezclando la fórmula básica de las pruebas de grupo. Las siguientes elaboraciones darán una idea de algunas de las variantes más exóticas. En el modelo "bueno-mediocre-malo", cada elemento es "bueno", "mediocre" o “malo”, y el resultado de una prueba es el tipo del "peor" elemento del grupo. En las pruebas de grupo con umbral, el resultado de una prueba es positivo si el número de elementos defectuosos del grupo es superior a algún valor umbral o proporción.^[7]​ Las pruebas de grupo con inhibidores son una variante con aplicaciones en biología molecular. En este caso, existe una tercera clase de elementos denominados inhibidores, y el resultado de una prueba es positivo si contiene al menos un elemento defectuoso y ningún inhibidor.^[8]​

Robert Dorfman introdujo por primera vez el concepto de las pruebas de grupo en 1943 en un breve informe^[2]​ publicado en la sección de notas de Annals of Mathematical Statistics^[3]​[b]. El informe de Dorfman, al igual que todos los primeros trabajos sobre pruebas de grupo, se centraba en el problema probabilístico y pretendía utilizar la novedosa idea de las pruebas de grupo para reducir el número previsto de pruebas necesarias para eliminar a todos los sifilíticos de un grupo determinado de soldados. El método era sencillo: dividir a los soldados en grupos de un tamaño determinado y realizar pruebas individuales (pruebas en grupos de un tamaño) en los grupos positivos para averiguar cuáles estaban infectados. Dorfman tabuló los tamaños de grupo óptimos para esta estrategia en función de la tasa de prevalencia de la defectuosidad en la población.^[2]​ Stephen Samuels^[9]​ encontró una solución de forma cerrada para el tamaño de grupo óptimo en función de la tasa de prevalencia.

Después de 1943, las pruebas de grupo permanecieron prácticamente intactas durante varios años. En 1957, Sterrett introdujo una mejora en el procedimiento de Dorfman.^[10]​ Este nuevo proceso comienza realizando de nuevo pruebas individuales en los grupos positivos, pero se detiene en cuanto se identifica un defecto. A continuación, los demás elementos del grupo se prueban juntos, ya que es muy probable que ninguno de ellos sea defectuoso.

El primer tratamiento exhaustivo de las pruebas de grupo lo realizaron Sobel y Groll en su artículo de 1959 sobre el tema,^[11]​ en el que describían cinco nuevos procedimientos -además de generalizaciones para cuando se desconoce la tasa de prevalencia- y, para el óptimo, proporcionaban una fórmula explícita del número previsto de pruebas que utilizaría. En el artículo también se establece por primera vez la conexión entre las pruebas de grupo y la teoría de la información, además de analizar varias generalizaciones del problema de las pruebas de grupo y proporcionar algunas aplicaciones nuevas de la teoría.

El resultado fundamental de Peter Ungar en 1960 muestra que si la tasa de prevalencia ${\displaystyle p>p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$, entonces la prueba individual es el procedimiento de prueba de grupo óptimo con respecto al número esperado de pruebas, y si p${\displaystyle p<p_{u}}$, entonces no es óptimo. Sin embargo, es importante señalar que, a pesar de 80 años de esfuerzos de investigación, el procedimiento óptimo aún se desconoce para p${\displaystyle p<p_{u}}$ y un tamaño de población general n ${\displaystyle n>2}$^[12]​

Las pruebas de grupo fueron estudiadas por primera vez en el contexto combinatorio por Li en 1962,^[13]​ con la introducción del algoritmo de Li 𝑠-stage.^[3]​ Li propuso una extensión del "algoritmo de 2 etapas" de Dorfman a un número arbitrario de etapas que requerían no más de ${\displaystyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$ pruebas para garantizar encontrar 𝑑 o menos defectuosos entre 𝑛 elementos. La idea era eliminar todos los ítems en pruebas negativas, y dividir los ítems restantes en grupos como se hizo con el pool inicial. Esto debía hacerse 𝑠-1 veces antes de realizar las pruebas individuales.

Las pruebas combinatorias de grupo en general fueron estudiadas más a fondo por Katona en 1973.^[14]​ Katona introdujo la representación matricial de las pruebas de grupo no adaptativas y elaboró un procedimiento para encontrar los defectuosos en el caso 1-defectuoso no adaptativo en no más de ${\displaystyle t=\lceil \log _{2}(n)\rceil }$pruebas, que también demostró ser óptimo.

En general, es difícil encontrar algoritmos óptimos para la prueba combinatoria adaptativa de grupos y, aunque no se ha determinado la complejidad computacional de la prueba de grupos, se sospecha que es difícil en alguna clase de complejidad.^[3]​ Sin embargo, en 1972 se produjo un avance importante, con la introducción del algoritmo de división binaria generalizada.^[15]​ El algoritmo de división binaria generalizada funciona realizando una búsqueda binaria en los grupos que dan positivo y es un algoritmo sencillo que encuentra un único defectuoso en un número de pruebas no superior al límite inferior de información.

En situaciones en las que hay dos o más defectuosos, el algoritmo de división binaria generalizada sigue produciendo resultados casi óptimos, requiriendo como máximo 𝑑-1 pruebas por encima del límite inferior de información, donde 𝑑 es el número de defectuosos.^[15]​ Allemann realizó mejoras considerables en 2013, consiguiendo que el número de pruebas necesarias fuera inferior a ${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$ por encima del límite inferior de información cuando n${\displaystyle n/d\geq 38}$y ${\displaystyle d\geq 10}$.^[16]​ Esto se consiguió cambiando la búsqueda binaria en el algoritmo de división binaria por un conjunto complejo de subalgoritmos con grupos de pruebas superpuestos. De este modo, el problema de la prueba combinatoria adaptativa de grupos -con un número conocido o un límite superior en el número de defectuosos- ha quedado esencialmente resuelto, con poco margen para nuevas mejoras.

Queda abierta la cuestión de cuándo las pruebas individuales son mínimas. Hu, Hwang y Wang demostraron en 1981 que la prueba individual es minima cuando ${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$, y que no es minima cuando ${\displaystyle n/d\geq 38}$.^[17]​ Actualmente se conjetura que este límite es agudo: es decir, la prueba individual es minmax si y sólo si ${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$.^[18]​[c] En 2000 Riccio y Colbourn hicieron algunos progresos, demostrando que para grandes 𝑛, la prueba individual es minmax cuando d${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$.^[19]​

Una de las ideas clave de las pruebas de grupo no adaptativas es que se pueden obtener beneficios significativos eliminando el requisito de que el procedimiento de prueba de grupo tenga un éxito seguro (el problema "combinatorio"), sino permitiendo que tenga una probabilidad baja pero no nula de etiquetar mal cada elemento (el problema "probabilístico"). Se sabe que, a medida que el número de elementos defectuosos se aproxima al número total de elementos, las soluciones combinatorias exactas requieren muchas más pruebas que las soluciones probabilísticas, e incluso las soluciones probabilísticas solo permiten una probabilidad de error asintóticamente pequeña.^[4]​

En esta línea, Chan et al. (2011) introdujeron COMP, un algoritmo probabilístico que no requiere más de ${\displaystyle t=ed(1+\delta )\ln(n)}$ pruebas para encontrar hasta ${\displaystyle d}$ defectuosos en ${\displaystyle n}$ elementos con una probabilidad de error no superior a n${\displaystyle n^{-\delta }}$.^[5]​ Esto está dentro de un factor constante del límite inferior de ${\displaystyle t=O(d\log _{2}n)}$.^[4]​

Chan et al. (2011) también proporcionaron una generalización de COMP a un modelo ruidoso simple, y de manera similar produjeron un límite de rendimiento explícito, que era de nuevo sólo una constante (dependiente de la probabilidad de una prueba fallida) por encima del límite inferior correspondiente.^[4]​^[5]​ En general, el número de pruebas necesarias en el caso de ruido Bernoulli es un factor constante mayor que en el caso sin ruido.^[5]​

Aldridge, Baldassini y Johnson (2014) produjeron una extensión del algoritmo COMP que añadía pasos adicionales de posprocesamiento.^[20]​ Demostraron que el rendimiento de este nuevo algoritmo, denominado DD, supera estrictamente al de COMP, y que DD es "esencialmente óptimo" en escenarios en los que ${\displaystyle d^{2}\geq n}$, comparándolo con un algoritmo hipotético que define un óptimo razonable. El rendimiento de este algoritmo hipotético sugiere que hay margen de mejora cuando ${\displaystyle d^{2}<n}$, además de sugerir cuánto podría mejorar.^[20]​

En esta sección se definen formalmente las nociones y términos relacionados con las pruebas de grupo.

• El vector de entrada, x${\displaystyle \mathbf {x} =(x_{1},x_{2},\dots ,x_{n})}$, se define como un vector binario de longitud 𝑛 (es decir, ${\displaystyle \mathbf {x} \in \{0,1\}^{n}}$, siendo el j-ésimo elemento llamado defectuoso si y sólo si ${\displaystyle x_{j}=1}$Además, cualquier ítem no defectuoso se denomina ítem "bueno".

𝑥 pretende describir el conjunto (desconocido) de artículos defectuosos. La propiedad clave de 𝑥 es que es una entrada implícita. Es decir, no hay conocimiento directo de cuáles son las entradas de 𝑥, salvo el que se puede inferir a través de una serie de 'pruebas'. Esto nos lleva a la siguiente definición.

• Sea 𝑥 un vector de entrada. Un conjunto, ${\displaystyle S\subseteq \{1,2,\dots ,n\}}$ se denomina prueba. Cuando las pruebas no tienen ruido, el resultado de una prueba es positivo cuando existe ${\displaystyle j\in S}$ tal que

${\displaystyle x_{j}=1}$ y el resultado es negativo en caso contrario.

Por lo tanto, el objetivo de las pruebas de grupo es idear un método para elegir una serie "corta" de pruebas que permitan determinar 𝑥, ya sea exactamente o con un alto grado de certeza.

• Se dice que un algoritmo de pruebas en grupo comete un error si etiqueta incorrectamente un elemento (es decir, etiqueta cualquier elemento defectuoso como no defectuoso o viceversa). Esto no es lo mismo que el resultado de una prueba de grupo sea incorrecto. Un algoritmo se denomina de error cero si la probabilidad de que cometa un error es cero.[e]
• ${\displaystyle t(d,n)}$ denota el número mínimo de pruebas necesarias para encontrar siempre 𝑑 defectuosos entre 𝑛 elementos con probabilidad cero de error por cualquier algoritmo de prueba de grupo. Para la misma cantidad, pero con la restricción de que el algoritmo no es adaptativo, se utiliza la notación ${\displaystyle {\bar {t}}(d,n)}$ es usado.

Dado que siempre es posible recurrir a pruebas individuales estableciendo ${\displaystyle S_{j}=\{j\}}$ para cada ${\displaystyle 1\leq j\leq n}$, debe ser que ${\displaystyle {\bar {t}}(d,n)\leq n}$. Además, dado que cualquier procedimiento de prueba no adaptativo puede escribirse como un algoritmo adaptativo simplemente realizando todas las pruebas sin tener en cuenta su resultado,${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$. Por último, cuando ${\displaystyle 0\neq d\neq n}$, hay al menos un elemento cuya defectuosidad debe determinarse (mediante al menos una prueba), y así ${\displaystyle 0\neq d\neq n}$

En resumen (cuando se asume ${\displaystyle 0\neq d\neq n}$ ${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$.

Un límite inferior en el número de pruebas necesarias puede describirse utilizando la noción de espacio muestral, denotado 𝑆, que es simplemente el conjunto de posibles colocaciones de defectuosos. Para cualquier problema de prueba en grupo con espacio muestral 𝑆 y cualquier algoritmo de prueba en grupo, puede demostrarse que ${\displaystyle t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil }$, donde 𝑡 es el número mínimo de pruebas necesarias para identificar todos los defectos con una probabilidad de error cero. Este límite se deriva del hecho de que, después de cada prueba, 𝑆 se divide en dos subconjuntos disjuntos, cada uno de los cuales corresponde a uno de los dos resultados posibles de la prueba.

Sin embargo, el límite inferior de información en sí suele ser inalcanzable, incluso para problemas pequeños[4]. Esto se debe a que la división de 𝑆 no es arbitraria, ya que debe ser realizable mediante alguna prueba.

De hecho, la cota inferior de información puede generalizarse al caso en que exista una probabilidad distinta de cero de que el algoritmo cometa un error. En esta forma, el teorema nos da una cota superior de la probabilidad de éxito basada en el número de pruebas. Para cualquier algoritmo de prueba en grupo que realice 𝑡 pruebas, la probabilidad de éxito, ${\displaystyle \mathbb {P} ({\textrm {success}})}$, satisface ${\displaystyle \mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}}$. Puede reforzarse: ${\displaystyle \mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}}$.^[5]​^[21]​

Los algoritmos para pruebas de grupo no adaptativas constan de dos fases distintas. En primer lugar, se decide cuántas pruebas realizar y qué elementos incluir en cada prueba. En la segunda fase, a menudo denominada etapa de descodificación, se analizan los resultados de cada prueba de grupo para determinar qué artículos son probablemente defectuosos. La primera fase suele codificarse en una matriz de la siguiente manera.^[5]​

• Supongamos un procedimiento de prueba de grupo no adaptativo para 𝑛 consta de las pruebas ${\displaystyle S_{1},S_{2},\dots ,S_{t}}$ para algunos ${\displaystyle t\in \mathbb {N} _{\geq 0}}$. La matriz de comprobación de este esquema es la${\displaystyle t\times n}$ matriz binaria, donde ${\displaystyle (M)_{ij}=1}$ si y sólo si ${\displaystyle j\in S_{i}}$(y es cero en caso contrario).

Por lo tanto, cada columna de 𝑀 representa un ítem y cada fila representa una prueba, con a 1 en el ${\displaystyle (i,j){\textrm {-th}}}$ que indica que ${\displaystyle i{\textrm {-th}}}$ incluye la ${\displaystyle j{\textrm {-th}}}$ y un 0 en caso contrario.

Así como el vector 𝑥 (de longitud 𝑛) que describe el conjunto defectuoso desconocido, es habitual introducir el vector de resultados, que describe los resultados de cada prueba.

• Sea 𝑡 el número de pruebas realizadas por un algoritmo no adaptativo. El vector de resultados, ${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$es un vector binario de longitud 𝑡 (es decir, ${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$tal que ${\displaystyle y_{i}=1}$ si y sólo si el resultado de 𝑖- es positivo (es decir, contiene al menos un defecto)[g].

Con estas definiciones, el problema no adaptativo puede replantearse de la siguiente manera: primero se elige una matriz de prueba, 𝑀tras lo cual se elige el vector 𝑦. A continuación, el problema consiste en analizar 𝑦 para encontrar una estimación de 𝑥.

En el caso ruidoso más simple, donde hay una probabilidad constante, 𝑞de que una prueba de grupo tenga un resultado erróneo, se considera un vector binario aleatorio, 𝑣donde cada entrada tiene una probabilidad 𝑞 de ser 1y es 0 en caso contrario. El vector que se devuelve es entonces ${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$ con la adición habitual en ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ (equivalentemente, es la operación XOR entre elementos). Un algoritmo ruidoso debe estimar 𝑥 utilizando 𝑦^ (es decir, sin conocimiento directo de 𝑦).^[5]​

La representación matricial permite demostrar algunos límites en las pruebas de grupo no adaptativas. El enfoque refleja el de muchos diseños deterministas, donde 𝑑-como se define a continuación.^[3]​

• Una matriz binaria, 𝑀 se denomina 𝑑-si cada suma booleana (OR lógico) de cualquiera de las matrices binarias 𝑑 de sus columnas es distinta. Además, la notación 𝑑¯-separable indica que cada suma de cualquiera de hasta ${\displaystyle M}$ es distinta. (Esto no es lo mismo que 𝑀 sea 𝑘-para cada ${\displaystyle k\leq d}$)

Cuando 𝑀 es una matriz de prueba, la propiedad de ser ${\displaystyle {\bar {d}}}$- separable (${\displaystyle {\bar {d}}}$-separable) es equivalente a ser capaz de distinguir entre (hasta) 𝑑 defectuosos. Sin embargo, no garantiza que esto sea sencillo. Una propiedad más fuerte, llamada disyunción, sí lo hace.

• Una matriz binaria, 𝑀 se denomina 𝑑-disyuntiva si la suma booleana de cualquier 𝑑 no contiene ninguna otra columna. (En este contexto, se dice que una columna A contiene a una columna B si para cada índice en el que B tiene un 1, A también tiene un 1).

Una propiedad útil de 𝑑-es que, con un máximo de 𝑑 defectuosos, cada elemento no defectuoso aparecerá en al menos una prueba cuyo resultado sea negativo. Esto significa que hay un procedimiento sencillo para encontrar los defectuosos: basta con eliminar todos los elementos que aparecen en una prueba negativa.

Utilizando las propiedades de 𝑑-separable y 𝑑-se puede demostrar lo siguiente para el problema de identificar 𝑑 defectuosas entre

𝑛 elementos totales.^[4]​

1. El número de pruebas necesarias para una probabilidad media de error asintóticamente pequeña escala como ${\displaystyle O(d\log _{2}n)}$.
2. El número de pruebas necesarias para una probabilidad máxima de error asintóticamente pequeña escala como ${\displaystyle O(d^{2}\log _{2}n)}$.
3. El número de pruebas necesarias para una probabilidad de error nula escala como ${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$.

El algoritmo de división binaria generalizado es un algoritmo de prueba de grupo adaptativo esencialmente óptimo que encuentra 𝑑 o menos defectuosos entre 𝑛 elementos de la siguiente manera:^[3]​^[15]​

1. Si ${\displaystyle n\leq 2d-2}$ prueba el 𝑛 individualmente. En caso contrario, establezca ${\displaystyle l=n-d+1}$ y ${\displaystyle \alpha =\lfloor \log _{2}{l/d}\rfloor }$.
2. Probar un grupo de tamaño 2𝛼. Si el resultado es negativo, todos los elementos del grupo se declaran no defectuosos; establezca ${\displaystyle n:=n-2^{\alpha }}$ y vaya al paso 1. En caso contrario, utilice una búsqueda binaria para identificar un defectuoso y un número noespecificado, denominado 𝑥 de elementos no defectuosos. Ponga ${\displaystyle n:=n-1-x}$ y ${\displaystyle d:=d-1}$. Vaya al paso 1.

El algoritmo generalizado de división binaria no requiere más de 𝑇 pruebas donde ${\displaystyle T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}}$

Para ${\displaystyle n/d}$ grande, se puede demostrar que ${\displaystyle T\rightarrow d\log _{2}(n/d)}$,^[3]​ que se compara favorablemente con la pruebas necesarias ${\displaystyle t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)}$ para Li 𝑠-de Li. De hecho, el algoritmo de división binaria generalizado se aproxima al óptimo en el siguiente sentido. Cuando ${\displaystyle d\geq 2}$ se puede demostrar que ${\displaystyle T-B_{I}(d,n)\leq (d-1)}$ donde ${\displaystyle B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil }$s el límite inferior de información.^[3]​^[15]​

Los algoritmos de prueba en grupo no adaptativos tienden a asumir que se conoce el número de defectuosos, o al menos una buena cota superior de los mismos.^[5]​𝑑 en esta sección. Si no se conocen los límites, existen algoritmos no adaptativos con baja complejidad de consulta que pueden ayudar a estimar 𝑑.^[22]​

Combinatorial Orthogonal Matching Pursuit, o COMP, es un algoritmo sencillo no adaptativo de comprobación de grupos que constituye la base de los algoritmos más complicados que siguen en esta sección.

En primer lugar, cada entrada de la matriz de comprobación se elige i.i.d. Para que sea 1 con probabilidad ${\displaystyle 1/d}$ y 0 en caso contrario.

La descodificación se realiza por columnas (es decir, por elementos). Si todas las pruebas en las que aparece un elemento son positivas, el elemento se declara defectuoso; en caso contrario, se supone que el elemento no es defectuoso. O, lo que es lo mismo, si un elemento aparece en cualquier prueba cuyo resultado sea negativo, el elemento se declara no defectuoso; en caso contrario, se supone que el elemento es defectuoso. Una propiedad importante de este algoritmo es que nunca crea falsos negativos, aunque se produce un falso positivo cuando todas las ubicaciones con unos en la j-ésima columna de 𝑀 (correspondiente a un artículo j no defectuoso) quedan "ocultos" por los unos de otras columnas correspondientes a artículos defectuosos.

El algoritmo COMP no requiere más de ${\displaystyle ed(1+\delta )\ln(n)}$ para tener una probabilidad de error menor o igual a ${\displaystyle n^{-\delta }}$.^[5]​ Esto está dentro de un factor constante del límite inferior para la probabilidad media de error anterior.

En el caso ruidoso, se relaja el requisito en el algoritmo COMP original de que el conjunto de ubicaciones de unos en cualquier columna de 𝑀 correspondiente a un elemento positivo esté completamente contenido en el conjunto de ubicaciones de unos en el vector de resultados. En su lugar, se permite un cierto número de "desajustes" - este número de desajustes depende tanto del número de unos en cada columna, como del parámetro de ruido, 𝑞. Este algoritmo COMP ruidoso no requiere más de ${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$pruebas para alcanzar una probabilidad de error como máximo 𝑛-𝛿.^[5]​

El método de los defectos definidos (DD) es una extensión del algoritmo COMP que intenta eliminar los falsos positivos. Se ha demostrado que las garantías de rendimiento de DD superan estrictamente las de COMP.^[20]​

El paso de descodificación utiliza una propiedad útil del algoritmo COMP: que cada elemento que COMP declara no defectuoso es ciertamente no defectuoso (es decir, no hay falsos negativos). El procedimiento es el siguiente:

1. En primer lugar, se ejecuta el algoritmo COMP y se eliminan los elementos no defectuosos que detecta. Todos los elementos restantes son ahora "posiblemente defectuosos".
2. A continuación, el algoritmo examina todas las pruebas positivas. Si un elemento aparece como el único "posiblemente defectuoso" en una prueba, entonces debe ser defectuoso, por lo que el algoritmo lo declara defectuoso.
3. Todos los demás elementos se consideran no defectuosos. La justificación de este último paso se basa en la suposición de que el número de artículos defectuosos es mucho menor que el número total de artículos.

Tenga en cuenta que los pasos 1 y 2 nunca se equivocan, por lo que el algoritmo sólo puede equivocarse si declara un artículo defectuoso como no defectuoso. Por lo tanto, el algoritmo DD sólo puede crear falsos negativos.

SCOMP (Sequential COMP) es un algoritmo que aprovecha el hecho de que DD no comete errores hasta el último paso, en el que se supone que los elementos restantes no son defectuosos. Sea el conjunto de defectuosos declarados 𝐾. Una prueba positiva se denomina explicada por 𝐾 si contiene al menos un elemento en 𝐾. La observación clave con SCOMP es que el conjunto de defectuosos encontrados por DD puede no explicar cada prueba positiva, y que cada prueba no explicada debe contener un defectuoso oculto.

El algoritmo procede como sigue.

1. Realizar los pasos 1 y 2 del algoritmo DD para obtener 𝐾una estimación inicial del conjunto de defectuosos.
2. Si 𝐾 explica todas las pruebas positivas, termina el algoritmo: 𝐾 es la estimación final del conjunto de defectuosos.
3. Si hay pruebas sin explicación, busque el "posible defectuoso" que aparezca en el mayor número de pruebas sin explicación y declárelo defectuoso (es decir, añádalo al conjunto 𝐾). Vaya al paso 2.

En simulaciones, se ha demostrado que SCOMP tiene un rendimiento cercano al óptimo.^[20]​

Un algoritmo determinista que está garantizado para identificar exactamente hasta 𝑑 positivos es Polynomial Pools (PP).^[23]​ El algoritmo consiste en la construcción de la matriz de agrupación 𝑀que puede utilizarse directamente para decodificar las observaciones en 𝑦. De forma similar al COMP, una muestra se descodifica según la relación ${\displaystyle x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)}$ donde .∗ representa la multiplicación por elementos y ${\displaystyle M(:,i)}$ es el 𝑖columna de 𝑀. Dado que el paso de descodificación no es difícil, PP está especializado en generar ${\displaystyle M}$.

Un grupo ℓ se genera mediante una relación polinómica que especifica los índices de las muestras contenidas en cada pool. Un conjunto de parámetros de entrada determina el algoritmo. Para un número primo ${\displaystyle p>1}$ y un número entero ${\displaystyle n\geq 1}$ cualquier potencia prima se define por ${\displaystyle q=p^{n}}$. Para un parámetro de dimensión ${\displaystyle c\geq 2}$ el número total de muestras es ${\displaystyle n=q^{c}}$ y el número de muestras por pool es ${\displaystyle q^{c-1}}$. Además, el campo finito de orden 𝑞 se denota por ${\displaystyle \mathbb {F} _{q}}$ (es decir, los enteros ${\displaystyle \{0,1,2,\ldots ,q-1\}}$ definidas por operaciones aritméticas especiales que aseguran que la suma y la multiplicación en ${\displaystyle \mathbb {F} _{q}}$ se mantienen en ${\displaystyle \mathbb {F} _{q}}$). El método dispone cada muestra en una cuadrícula y la representa mediante coordenadas ${\displaystyle x=(u,v)}$. Las coordenadas se calculan según una relación polinómica utilizando los enteros${\displaystyle 1\leq l\leq c-1}$${\displaystyle 0\leq u_{i_{l}}\leq q-1}$${\displaystyle v~=~a^{c-1}~u_{i_{c-1}}+\cdots +a~u_{i_{1}}+b,\quad a,b,u_{i_{l}}\in \mathbb {F} _{q}.}$ La combinación de bucle a través de la ${\displaystyle u_{i_{l}}}$ está representada por un conjunto con ${\displaystyle q^{c-1}}$ elementos de una secuencia de ${\displaystyle d-1}$ enteros, es decir ${\displaystyle u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}}$ donde ${\displaystyle 0\leq i_{l}\leq q-1}$. Sin pérdida de generalidad, la combinación es tal que ${\displaystyle i_{d-1}}$ cicla cada 𝑞 veces, ${\displaystyle i_{d-2}}$ ciclos cada ${\displaystyle q^{2}}$ veces hasta 𝑖1 circule sólo una vez. Las fórmulas que calculan los índices muestrales, y por tanto las agrupaciones correspondientes, para valores fijos de 𝑎 y 𝑏vienen dadas por

${\displaystyle {\begin{aligned}u_{i}&=\sum _{l=1}^{c-1}~q^{d-1-l}~i_{l}\\v_{u_{i}}&=\sum _{l=1}^{c-1}~a^{l}~i_{l}+b\quad ({\text{computed in }}\mathbb {F} _{q})\\x_{qu_{i}+v_{u_{i}}}&=(u_{i},v_{u_{i}})\end{aligned}}}$

Los cálculos en 𝐹𝑞 pueden implementarse con bibliotecas de software disponibles públicamente para campos finitos, cuando

𝑞 es una potencia prima. Cuando 𝑞 es un número primo, entonces los cálculos en 𝐹𝑞 se simplifican a la aritmética del módulo, es decir, ${\displaystyle v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q}$. Un ejemplo de cómo generar un pool ℓ cuando ${\displaystyle a=1,b=0,c=2}$ se muestra en la tabla siguiente, mientras que la selección de muestras correspondiente se muestra en la figura anterior.

Cálculo de un fondo común ℓ utilizando PP con ${\displaystyle c=3}$${\displaystyle q=3}$${\displaystyle a=1}$${\displaystyle b=0}$

${\displaystyle i_{1}}$	${\displaystyle i_{2}}$	${\displaystyle u_{i}}$	${\displaystyle v_{u_{i}}}$	${\displaystyle qu_{i}+v_{u_{i}}}$	${\displaystyle \ell }$
${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle 0}$	${\displaystyle x_{0}}$
${\displaystyle 0}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle x_{4}}$
${\displaystyle 0}$	${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 8}$	${\displaystyle x_{8}}$
${\displaystyle 1}$	${\displaystyle 0}$	${\displaystyle 3}$	${\displaystyle 1}$	${\displaystyle 10}$	${\displaystyle x_{10}}$
${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 4}$	${\displaystyle 2}$	${\displaystyle 14}$	${\displaystyle x_{14}}$
${\displaystyle 1}$	${\displaystyle 2}$	${\displaystyle 5}$	${\displaystyle 0}$	${\displaystyle 15}$	${\displaystyle x_{15}}$
${\displaystyle 2}$	${\displaystyle 0}$	${\displaystyle 6}$	${\displaystyle 2}$	${\displaystyle 20}$	${\displaystyle x_{20}}$
${\displaystyle 2}$	${\displaystyle 1}$	${\displaystyle 7}$	${\displaystyle 0}$	${\displaystyle 21}$	${\displaystyle x_{21}}$
${\displaystyle 2}$	${\displaystyle 2}$	${\displaystyle 8}$	${\displaystyle 1}$	${\displaystyle 25}$	${\displaystyle x_{25}}$

Este método utiliza pruebas ${\displaystyle q(c-1)(d+1)}$ para identificar exactamente hasta 𝑑 positivos entre muestras ${\displaystyle n=q^{c}}$. Debido a esto PP es particularmente eficaz para grandes tamaños de muestra, ya que el número de pruebas crece sólo linealmente con respecto a 𝑐 mientras que las muestras crecen exponencialmente con este parámetro. Sin embargo, el PP también puede ser eficaz para tamaños de muestra pequeños.^[23]​

La generalidad de la teoría de las pruebas de grupo la presta a muchas aplicaciones diversas, como el cribado de clones, la localización de cortocircuitos eléctricos;^[3]​redes informáticas de alta velocidad;^[24]​ exámenes médicos, búsqueda de cantidades, estadística;^[17]​ aprendizaje automático, secuenciación de ADN;^[25]​ criptografía;^[26]​^[27]​ y análisis forense de datos.^[28]​ Esta sección ofrece una breve visión general de una pequeña selección de estas aplicaciones.

Un canal multiacceso es un canal de comunicación que conecta a muchos usuarios a la vez. Cada usuario puede escuchar y transmitir en el canal, pero si más de uno transmite al mismo tiempo, las señales chocan y se reducen a ruido ininteligible. Los canales multiacceso son importantes para varias aplicaciones del mundo real, sobre todo las redes informáticas inalámbricas y las redes telefónicas.^[29]​

Un problema importante de los canales multiacceso es cómo asignar tiempos de transmisión a los usuarios para que sus mensajes no colisionen. Un método sencillo consiste en dar a cada usuario su propio intervalo de tiempo para transmitir, lo que requiere 𝑛 intervalos. Sin embargo, este método es muy ineficaz, ya que asigna intervalos de transmisión a usuarios que pueden no tener un mensaje, y normalmente se asume que sólo unos pocos usuarios querrán transmitir en un momento dado (de lo contrario, un canal multiacceso no sería práctico).

En el contexto de las pruebas de grupo, este problema suele abordarse dividiendo el tiempo en "épocas" de la siguiente manera.^[3]​Un usuario se considera "activo" si tiene un mensaje al comienzo de una época. (Si se genera un mensaje durante una época, el usuario sólo pasa a estar activo al comienzo de la siguiente). Una época termina cuando todos los usuarios activos han transmitido su mensaje. El problema consiste entonces en encontrar a todos los usuarios activos en una época determinada y programar una hora para que transmitan (si no lo han hecho ya con éxito). En este caso, una prueba sobre un conjunto de usuarios corresponde a aquellos usuarios que intentan una transmisión. El resultado de la prueba es el número de usuarios que han intentado transmitir, ${\displaystyle 0,1,}$ y ${\displaystyle 2^{+}}$correspondientes, respectivamente, a ningún usuario activo, exactamente un usuario activo (mensaje correcto) o más de un usuario activo (colisión de mensajes). Por lo tanto, utilizando un algoritmo de prueba de grupo adaptativo con resultados ${\displaystyle \{0,1,2^{+}\}}$ se puede determinar qué usuarios desean transmitir en la época. Entonces, a cualquier usuario que aún no haya realizado una transmisión con éxito se le puede asignar una franja horaria para transmitir, sin malgastar tiempos asignados a usuarios inactivos.

El aprendizaje automático es un campo de la informática que tiene muchas aplicaciones informáticas, como la clasificación del ADN, la detección del fraude y la publicidad dirigida. Uno de los principales subcampos del aprendizaje automático es el problema del "aprendizaje mediante ejemplos", en el que la tarea consiste en aproximar alguna función desconocida cuando se da su valor en una serie de puntos concretos.^[3]​ Como se expone en esta sección, este problema de aprendizaje de funciones puede abordarse con un planteamiento de pruebas en grupo.

En una versión simple del problema, existe una función desconocida, ${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$ donde ${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$ y ${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$(utilizando aritmética lógica: la suma es OR lógico y la multiplicación es AND lógico). Aquí ${\displaystyle {\textbf {a}}}$ es ' disperso', lo que significa que como máximo ${\displaystyle d\ll N}$ de sus entradas son 1. El objetivo es construir una aproximación a 𝑓 utilizando 𝑡 evaluaciones puntuales, donde 𝑡 es lo más pequeño posible.^[4]​ (Recuperando exactamente 𝑓 corresponde a algoritmos de error cero, mientras que 𝑓 se aproxima mediante algoritmos que tienen una probabilidad de error distinta de cero).

En este problema, recuperar ${\displaystyle f}$ es equivalente a encontrar ${\displaystyle {\textbf {a}}}$. Además, ${\displaystyle f({\textbf {p}})=1}$ si y sólo si existe algún índice ${\displaystyle n}$ en el que ${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$. Por tanto, este problema es análogo a un problema de prueba de grupo con 𝑑 defectuosos y 𝑛 elementos totales. Las entradas de a son los artículos defectuosos si son ${\displaystyle 1}$, ${\displaystyle {\textbf {p}}}$ especifica una prueba, y una prueba es positiva si y sólo si ${\displaystyle f({\textbf {p}})=1}$.^[4]​

En realidad, a menudo uno estará interesado en funciones que son más complicadas, tales como ${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$, de nuevo donde ${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$. La detección comprimida, estrechamente relacionada con las pruebas de grupo, puede utilizarse para resolver este problema.^[4]​

En la detección comprimida, el objetivo es reconstruir una señal, ${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$tomando una serie de medidas. Estas mediciones se modelizan como si se tomara el producto punto de v El objetivo es utilizar un número reducido de mediciones, aunque esto no suele ser posible a menos que se asuma algo sobre la señal. Una de esas suposiciones (habitual)^[30]​^[31]​ es que sólo un pequeño número de entradas de v sean significativas, es decir, que tengan una gran magnitud. Dado que las mediciones son productos escalares de vla ecuación ${\displaystyle M{\textbf {v}}={\textbf {q}}}$ donde ${\displaystyle M}$ es una ${\displaystyle t\times N}$ matriz que describe el conjunto de mediciones que se han elegido y ${\displaystyle \mathbf {q} }$ es el conjunto de resultados de las mediciones. Esta construcción demuestra que la detección comprimida es un tipo de prueba de grupo "continua".

La principal dificultad de la detección comprimida es identificar qué entradas son significativas.^[30]​ Una vez hecho esto, existen diversos métodos para estimar los valores reales de las entradas.^[32]​ Esta tarea de identificación puede abordarse con una sencilla aplicación de pruebas de grupo. En este caso, una prueba de grupo produce un número complejo: la suma de las entradas que se prueban. El resultado de una prueba se llama positivo si produce un número complejo con una gran magnitud, lo que, dada la suposición de que las entradas significativas son dispersas, indica que al menos una entrada significativa está contenida en la prueba.

Existen construcciones deterministas explícitas para este tipo de algoritmo de búsqueda combinatoria, que requieren ${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$ .^[33]​ Sin embargo, al igual que ocurre con las pruebas de grupo, éstas no son óptimas, y las construcciones aleatorias (como COMP) pueden recuperar a menudo ${\displaystyle f}$ de forma sublineal en ${\displaystyle N}$.^[32]​

Durante una pandemia como el brote de COVID-19 en 2020, los ensayos de detección de virus a veces se ejecutan utilizando diseños de ensayos de grupo no adaptativos.^[34]​^[35]​^[36]​ Un ejemplo fue proporcionado por el proyecto Origami Assays, que publicó diseños de ensayos de grupo de código abierto para ejecutar en una placa de 96 pocillos estándar de laboratorio.^[37]​

En un entorno de laboratorio, uno de los retos de las pruebas de grupo es que la construcción de las mezclas puede llevar mucho tiempo y ser difícil de hacer a mano con precisión. Los ensayos Origami ofrecieron una solución a este problema de construcción proporcionando plantillas de papel para guiar al técnico sobre cómo distribuir las muestras de los pacientes en los pocillos de ensayo.^[38]​

Utilizando los diseños de prueba de grupo más grandes (XL3) fue posible probar 1120 muestras de pacientes en 94 pocillos de ensayo. Si la tasa de verdaderos positivos era lo suficientemente baja, no era necesario realizar pruebas adicionales.

Véase también: Lista de países que aplican la estrategia de pruebas de grupo contra COVID-19

El análisis forense de datos es un campo dedicado a encontrar métodos para recopilar pruebas digitales de un delito. Estos delitos suelen implicar que un adversario modifique los datos, documentos o bases de datos de una víctima, con ejemplos como la alteración de registros fiscales, un virus que oculta su presencia o un ladrón de identidad que modifica datos personales.^[28]​

Una herramienta habitual en el análisis forense de datos es el hash criptográfico unidireccional. Se trata de una función que toma los datos y, mediante un procedimiento difícil de revertir, produce un número único llamado hash[i]. Los hash, que a menudo son mucho más cortos que los datos, nos permiten comprobar si los datos se han modificado sin tener que almacenar copias completas de la información: el hash de los datos actuales puede compararse con un hash pasado para determinar si se ha producido algún cambio. Una propiedad desafortunada de este método es que, aunque es fácil saber si los datos se han modificado, no hay forma de determinar cómo: es decir, es imposible recuperar qué parte de los datos ha cambiado.^[28]​

Una forma de sortear esta limitación es almacenar más hashes -ahora de subconjuntos de la estructura de datos- para acotar dónde se ha producido el ataque. Sin embargo, para encontrar la ubicación exacta del ataque con un enfoque ingenuo, sería necesario almacenar un hash para cada dato de la estructura, lo que anularía el objetivo de los hashes en primer lugar. (Las pruebas de grupo pueden utilizarse para reducir drásticamente el número de hashes que deben almacenarse. Una prueba se convierte en una comparación entre los hashes almacenados y los actuales, que es positiva cuando hay un desajuste. Esto indica que al menos un dato editado (que se toma como defectuoso en este modelo) está contenido en el grupo que generó el hash actual.^[28]​

De hecho, la cantidad de hashes necesarios es tan baja que éstos, junto con la matriz de pruebas a la que hacen referencia, pueden incluso almacenarse dentro de la estructura organizativa de los propios datos. Esto significa que, en lo que respecta a la memoria, la prueba puede realizarse "gratis". (Esto es cierto con la excepción de una clave maestra/contraseña que se utiliza para determinar en secreto la función hash).^[28]​

• Problema de las doce monedas

• Ding-Zhu, Du; Hwang, Frank K. (1993). Combinatorial group testing and its applications. Singapore: World Scientific. ISBN 978-9810212933.

• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2007), Lectures 7.
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Spring 2010), Lectures 10, 11, 28, 29
• Du, D.; Hwang, F. (2006). Pooling Designs and Nonadaptive Group Testing. World Scientific. ISBN 9789814477864.
• Aldridge, M.; Johnson, O.; Scarlett, J. (2019). "Group Testing: An Information Theory Perspective" (PDF). Foundations and Trends in Communications and Information Theory. 15 (3–4): 196–392. doi:10.1561/0100000099. S2CID 62841593.
• Porat, E.; Rothschild, A. (2011). "Explicit nonadaptive combinatorial group testing schemes". IEEE Transactions on Information Theory. 57 (12): 7982–89. arXiv:0712.3876. doi:10.1109/TIT.2011.2163296. S2CID 8815474.
• Kagan, Eugene; Ben-gal, Irad (2014), "A group testing algorithm with online informational learning", IIE Transactions, 46 (2): 164–184, doi:10.1080/0740817X.2013.803639, ISSN 0740-817X, S2CID 18588494