มีการจำแนกประเภทอิสระสองแบบสำหรับปัญหาการทดสอบกลุ่ม ปัญหาการทดสอบกลุ่มทุกปัญหาจะเป็นแบบปรับตัวได้หรือไม่ปรับตัวได้ และจะเป็นแบบความน่าจะเป็นหรือแบบผสมผสาน^{[ 3 ]}

ในแบบจำลองความน่าจะเป็น รายการที่ชำรุดจะถือว่าเป็นไปตามการกระจายความน่าจะเป็น บางอย่าง และเป้าหมายคือการลด จำนวนการทดสอบ ที่คาดว่าจะต้องใช้ในการระบุความชำรุดของแต่ละรายการให้น้อยที่สุด ในทางกลับกัน สำหรับการทดสอบกลุ่มแบบผสมผสาน เป้าหมายคือการลดจำนวนการทดสอบที่จำเป็นใน 'สถานการณ์ที่เลวร้ายที่สุด' ให้น้อยที่สุด นั่นคือ สร้างอัลกอริทึม minmaxและไม่มีการสันนิษฐานถึงความรู้เกี่ยวกับการกระจายของรายการที่ชำรุด^{[ 3 ]}

การจำแนกประเภทอีกแบบหนึ่งคือ ความสามารถในการปรับตัว ซึ่งเกี่ยวข้องกับข้อมูลที่สามารถนำมาใช้ในการเลือกรายการที่จะจัดกลุ่มเพื่อทดสอบ โดยทั่วไป การเลือกรายการที่จะทดสอบนั้นอาจขึ้นอยู่กับผลลัพธ์ของการทดสอบก่อนหน้า ดังเช่นในปัญหาหลอดไฟข้างต้นอัลกอริทึมที่ดำเนินการโดยการทำการทดสอบ แล้วใช้ผลลัพธ์ (และผลลัพธ์ทั้งหมดในอดีต) เพื่อตัดสินใจว่าจะทำการทดสอบใดต่อไป เรียกว่า อัลกอริทึมแบบปรับตัว ในทางกลับกัน ในอัลกอริทึมแบบไม่ปรับตัว การทดสอบทั้งหมดจะถูกกำหนดไว้ล่วงหน้า แนวคิดนี้สามารถขยายไปสู่อัลกอริทึมแบบหลายขั้นตอนได้ โดยที่การทดสอบจะถูกแบ่งออกเป็นขั้นตอน และการทดสอบทุกครั้งในขั้นตอนถัดไปจะต้องถูกกำหนดไว้ล่วงหน้า โดยอาศัยเพียงความรู้เกี่ยวกับผลลัพธ์ของการทดสอบในขั้นตอนก่อนหน้า แม้ว่าอัลกอริทึมแบบปรับตัวจะให้ความอิสระในการออกแบบมากกว่า แต่ก็เป็นที่ทราบกันดีว่าอัลกอริทึมการทดสอบกลุ่มแบบปรับตัวนั้นไม่ได้ปรับปรุงประสิทธิภาพให้ดีขึ้นกว่าอัลกอริทึมแบบไม่ปรับตัวมากไปกว่าค่าคงที่ในจำนวนการทดสอบที่จำเป็นในการระบุชุดของรายการที่ชำรุด^{[ 4 ] [ 3 ]}นอกจากนี้ วิธีการที่ไม่ปรับตัวมักมีประโยชน์ในทางปฏิบัติ เนื่องจากสามารถดำเนินการทดสอบต่อเนื่องได้โดยไม่ต้องวิเคราะห์ผลลัพธ์ของการทดสอบก่อนหน้าทั้งหมดก่อน ทำให้สามารถกระจายกระบวนการทดสอบได้อย่างมีประสิทธิภาพ^{[ 5 ]}

มีหลายวิธีในการขยายปัญหาการทดสอบแบบกลุ่ม หนึ่งในวิธีที่สำคัญที่สุดเรียกว่า การทดสอบแบบกลุ่มที่มีสัญญาณ รบกวนซึ่งเกี่ยวข้องกับสมมติฐานสำคัญของปัญหาดั้งเดิม นั่นคือ การทดสอบนั้นปราศจากข้อผิดพลาด ปัญหาการทดสอบแบบกลุ่มเรียกว่ามีสัญญาณรบกวนเมื่อมีโอกาสบางอย่างที่ผลลัพธ์ของการทดสอบแบบกลุ่มนั้นผิดพลาด (เช่น ผลออกมาเป็นบวกทั้งที่การทดสอบนั้นไม่มีข้อบกพร่อง) แบบจำลองสัญญาณรบกวนของเบอร์นูลลีถือว่าความน่าจะเป็นนี้เป็นค่าคงที่ค่าหนึ่ง${\displaystyle q}$แต่โดยทั่วไปแล้วอาจขึ้นอยู่กับจำนวนข้อบกพร่องที่แท้จริงในการทดสอบและจำนวนรายการที่ทดสอบ^{[ 6 ]}ตัวอย่างเช่น ผลกระทบของการเจือจางสามารถจำลองได้โดยการบอกว่าผลลัพธ์ที่เป็นบวกมีแนวโน้มมากขึ้นเมื่อมีข้อบกพร่องมากขึ้น (หรือมีข้อบกพร่องมากขึ้นเป็นสัดส่วนของจำนวนที่ทดสอบ) อยู่ในการทดสอบ^{[ 7 ]}อัลกอริทึมที่มีสัญญาณรบกวนจะมีโอกาสเกิดข้อผิดพลาดที่ไม่เป็นศูนย์เสมอ (นั่นคือ การติดฉลากรายการผิด) ^{[ 6 ]}

การทดสอบแบบกลุ่มสามารถขยายขอบเขตได้โดยพิจารณาสถานการณ์ที่มีผลลัพธ์ที่เป็นไปได้มากกว่าสองอย่างของการทดสอบ ตัวอย่างเช่น การทดสอบอาจมีผลลัพธ์ดังนี้${\displaystyle 0,1}$และ${\displaystyle 2^{+}}$ซึ่งสอดคล้องกับกรณีที่ไม่มีของเสียเลย มีของเสียเพียงชิ้นเดียว หรือมีของเสียจำนวนหนึ่งที่ไม่ทราบจำนวนแต่มากกว่าหนึ่งชิ้น โดยทั่วไปแล้ว เราสามารถพิจารณาเซตผลลัพธ์ของการทดสอบได้ดังนี้${\displaystyle {0,1,\ldots ,k^{+}}}$สำหรับบางคน${\displaystyle k\in \mathbb {N} }$[ ^{8 ]​}

การขยายเพิ่มเติมอีกอย่างหนึ่งคือการพิจารณาข้อจำกัดทางเรขาคณิตเกี่ยวกับชุดที่สามารถทดสอบได้ ปัญหาหลอดไฟข้างต้นเป็นตัวอย่างของข้อจำกัดประเภทนี้: เฉพาะหลอดไฟที่ปรากฏต่อเนื่องกันเท่านั้นที่สามารถทดสอบได้ ในทำนองเดียวกัน รายการต่างๆ อาจถูกจัดเรียงเป็นวงกลม หรือโดยทั่วไปเป็นโครงข่าย โดยที่การทดสอบเป็นเส้นทางที่ใช้ได้บนกราฟ ข้อจำกัดทางเรขาคณิตอีกประเภทหนึ่งคือจำนวนรายการสูงสุดที่สามารถทดสอบได้ในกลุ่ม^{[ a ]}หรือขนาดของกลุ่มอาจต้องเป็นเลขคู่ เป็นต้น ในทำนองเดียวกัน อาจเป็นประโยชน์ที่จะพิจารณาข้อจำกัดที่ว่ารายการใดรายการหนึ่งสามารถปรากฏในการทดสอบได้เพียงจำนวนหนึ่งเท่านั้น^{[ 8 ]}

มีวิธีมากมายนับไม่ถ้วนในการปรับเปลี่ยนสูตรพื้นฐานของการทดสอบแบบกลุ่ม คำอธิบายต่อไปนี้จะให้แนวคิดเกี่ยวกับรูปแบบที่แปลกใหม่กว่าบางส่วน ในแบบจำลอง 'ดี-ปานกลาง-แย่' แต่ละรายการจะเป็น 'ดี' 'ปานกลาง' หรือ 'แย่' และผลการทดสอบจะเป็นประเภทของรายการที่ 'แย่ที่สุด' ในกลุ่ม ในการทดสอบแบบกลุ่มโดยใช้เกณฑ์ ผลการทดสอบจะเป็นบวกหากจำนวนรายการที่บกพร่องในกลุ่มมีมากกว่าค่าเกณฑ์หรือสัดส่วนที่กำหนด^{[ 9 ]}การทดสอบแบบกลุ่มที่มีสารยับยั้งเป็นรูปแบบหนึ่งที่มีการประยุกต์ใช้ในชีววิทยาโมเลกุล ในที่นี้จะมีรายการประเภทที่สามที่เรียกว่าสารยับยั้ง และผลการทดสอบจะเป็นบวกหากมีรายการที่บกพร่องอย่างน้อยหนึ่งรายการและไม่มีสารยับยั้ง^{[ 10 ]}

แนวคิดเรื่องการทดสอบแบบกลุ่มได้รับการแนะนำครั้งแรกโดย Robert Dorfman ในปี 1943 ในรายงานสั้นๆ^{[ 2 ]}ที่ตีพิมพ์ในส่วน Notes ของAnnals of Mathematical Statistics [ ^{8 ] [ b ] รายงาน}ของ Dorfman – เช่นเดียวกับงานในช่วงแรกๆ เกี่ยวกับการทดสอบแบบกลุ่ม – มุ่งเน้นไปที่ปัญหาความน่าจะเป็น และมุ่งที่จะใช้แนวคิดใหม่ของการทดสอบแบบกลุ่มเพื่อลดจำนวนการทดสอบที่คาดว่าจะต้องใช้เพื่อคัดกรองผู้ชายที่เป็นโรคซิฟิลิสทั้งหมดในกลุ่มทหารที่กำหนด วิธีการนั้นง่าย: แบ่งทหารออกเป็นกลุ่มที่มีขนาดที่กำหนด และใช้การทดสอบรายบุคคล (ทดสอบสิ่งของในกลุ่มที่มีขนาดหนึ่ง) ในกลุ่มที่เป็นบวกเพื่อค้นหาว่าใครติดเชื้อ Dorfman ได้จัดทำตารางขนาดกลุ่มที่เหมาะสมที่สุดสำหรับกลยุทธ์นี้เทียบกับอัตราความชุกของความบกพร่องในประชากร^{[ 2 ]} Stephen Samuels พบวิธีแก้ปัญหาแบบปิดสำหรับขนาดกลุ่มที่เหมาะสมที่สุดเป็นฟังก์ชันของอัตราความชุก^{[ 12 ]}

หลังจากปี 1943 การทดสอบแบบกลุ่มยังคงไม่เปลี่ยนแปลงเป็นเวลาหลายปี ต่อมาในปี 1957 สเตอร์เร็ตต์ได้ปรับปรุงขั้นตอนของดอร์ฟแมน กระบวนการใหม่นี้เริ่มต้นด้วยการทำการทดสอบแบบรายบุคคลกับกลุ่มที่เป็นบวกอีกครั้ง แต่จะหยุดทันทีที่พบข้อบกพร่อง จากนั้นจึงทำการทดสอบรายการที่เหลือในกลุ่มร่วมกัน เนื่องจากมีความเป็นไปได้สูงว่าไม่มีรายการใดมีข้อบกพร่อง^{[ 13 ]}

การวิเคราะห์การทดสอบกลุ่มอย่างละเอียดครั้งแรกเกิดขึ้นโดย Sobel และ Groll ในบทความสำคัญของพวกเขาในปี 1959 พวกเขาอธิบายขั้นตอนใหม่ห้าขั้นตอน – นอกเหนือจากการสรุปทั่วไปสำหรับกรณีที่อัตราความชุกไม่เป็นที่ทราบ – และสำหรับขั้นตอนที่เหมาะสมที่สุด พวกเขาได้ให้สูตรที่ชัดเจนสำหรับจำนวนการทดสอบที่คาดว่าจะใช้ บทความนี้ยังเชื่อมโยงการทดสอบกลุ่มกับทฤษฎีสารสนเทศเป็นครั้งแรก รวมถึงการอภิปรายถึงการสรุปทั่วไปหลายประการของปัญหาการทดสอบกลุ่มและให้การประยุกต์ใช้ทฤษฎีใหม่บางประการ^{[ 14 ]}

ผลการค้นพบที่สำคัญของปีเตอร์ อุงการ์ในปี 1960 แสดงให้เห็นว่า หากอัตราการแพร่ระบาด${\displaystyle p>p_{u}}$, ที่ไหน${\displaystyle p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$ดังนั้น การทดสอบรายบุคคลจึงเป็นวิธีการทดสอบกลุ่มที่เหมาะสมที่สุดเมื่อพิจารณาจากจำนวนการทดสอบที่คาดไว้ และหาก${\displaystyle p<p_{u}}$ดังนั้นจึงไม่ใช่ทางเลือกที่ดีที่สุด อย่างไรก็ตาม สิ่งสำคัญที่ควรทราบคือ แม้จะมีการวิจัยมานานกว่า 80 ปีแล้ว แต่ขั้นตอนที่เหมาะสมที่สุดก็ยังไม่เป็นที่ทราบแน่ชัดสำหรับ${\displaystyle p<p_{u}}$และขนาดประชากรโดยทั่วไป${\displaystyle n>2}$[ ^{15 ]​}

การทดสอบกลุ่มได้รับการศึกษาครั้งแรกในบริบทเชิงการจัดเรียงโดย Li ในปี พ.ศ. 2505 ^{[ 16 ]}โดยมีการแนะนำของLi${\displaystyle s}$-ขั้นตอนอัลกอริธึม [ ^{8 ] ห}ลี่เสนอการขยาย 'อัลกอริธึม 2 ขั้นตอน' ของดอร์ฟแมนไปยังจำนวนขั้นตอนตามอำเภอใจซึ่งไม่ต้องการมากกว่า${\textstyle t={\frac {e}{\log _{2}(e)}}d\log _{2}(n)}$การทดสอบที่รับประกันว่าจะพบ${\displaystyle d}$หรือมีข้อบกพร่องน้อยลงในหมู่${\displaystyle n}$รายการต่างๆ แนวคิดคือการนำรายการที่มีผลการทดสอบเป็นลบออกทั้งหมด และแบ่งรายการที่เหลือออกเป็นกลุ่มๆ เช่นเดียวกับที่ทำกับกลุ่มตัวอย่างเริ่มต้น จะต้องดำเนินการเช่นนี้${\displaystyle s-1}$ครั้งก่อนที่จะทำการทดสอบรายบุคคล^{[ 16 ]}

การทดสอบกลุ่มเชิงผสมโดยทั่วไปได้รับการศึกษาอย่างละเอียดมากขึ้นโดย Katona ในปี 1973 Katona ได้นำเสนอการแสดงเมทริกซ์ของการทดสอบกลุ่มที่ไม่ปรับตัว และสร้างขั้นตอนในการค้นหาข้อบกพร่องในกรณีข้อบกพร่อง 1 รายการที่ไม่ปรับตัวได้ภายในเวลาไม่เกิน${\displaystyle t=\lceil \log _{2}(n)\rceil }$การทดสอบ ซึ่งเขายังพิสูจน์แล้วว่าเหมาะสมที่สุด^{[ 17 ]}

โดยทั่วไป การค้นหาอัลกอริทึมที่เหมาะสมที่สุดสำหรับการทดสอบกลุ่มแบบผสมผสานที่ปรับตัวได้นั้นเป็นเรื่องยาก และถึงแม้ว่า จะยังไม่ได้กำหนด ความซับซ้อนในการคำนวณของการทดสอบกลุ่ม แต่ก็คาดว่าน่าจะยาก ใน ระดับความซับซ้อนบางระดับ[ ^{8 ] อย่างไรก็ตาม}ความก้าวหน้าครั้งสำคัญเกิดขึ้นในปี 1972 ด้วยการแนะนำอัลกอริทึมการแบ่งแบบไบนารีทั่วไป อัลกอริทึมการแบ่งแบบไบนารีทั่วไปทำงานโดยการค้นหาแบบไบนารีในกลุ่มที่ทดสอบแล้วได้ผลเป็นบวก และเป็นอัลกอริทึมที่เรียบง่ายซึ่งพบข้อบกพร่องเพียงรายการเดียวในจำนวนการทดสอบไม่เกินขีดจำกัดล่างของ ข้อมูล ^{[ 18 ]}

ในกรณีที่มีชิ้นส่วนชำรุดสองชิ้นขึ้นไป อัลกอริทึมการแบ่งแบบไบนารีทั่วไปยังคงให้ผลลัพธ์ที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด โดยต้องการเวลาอย่างมากที่สุด${\displaystyle d-1}$การทดสอบที่อยู่เหนือขีดจำกัดล่างของข้อมูลซึ่ง${\displaystyle d}$คือจำนวนของสินค้าที่ชำรุด^{[ 18 ]}ในปี 2013 Allemann ได้ทำการปรับปรุงอย่างมากในเรื่องนี้ โดยลดจำนวนการทดสอบที่จำเป็นให้เหลือน้อยกว่า${\displaystyle 0.187d+0.5\log _{2}(d)+5.5}$เหนือขีดจำกัดล่างของข้อมูลเมื่อ${\displaystyle n/d\geq 38}$และ${\displaystyle d\geq 10}$สิ่งนี้สำเร็จได้โดยการเปลี่ยนการค้นหาแบบไบนารีในอัลกอริธึมการแบ่งแบบไบนารีให้เป็นชุดย่อยของอัลกอริธึมที่ซับซ้อนซึ่งมีกลุ่มทดสอบที่ทับซ้อนกัน ด้วยเหตุนี้ ปัญหาของการทดสอบกลุ่มเชิงผสมแบบปรับตัวได้ – โดยมีจำนวนที่ทราบหรือขอบเขตบนของจำนวนข้อบกพร่อง – จึงได้รับการแก้ไขโดยพื้นฐานแล้ว โดยแทบไม่มีช่องว่างสำหรับการปรับปรุงเพิ่มเติม^{[ 19 ]}

ยังมีคำถามที่ยังไม่มีคำตอบว่าการทดสอบรายบุคคลจะเป็นแบบ minmax เมื่อใด Hu, Hwang และ Wang ได้แสดงให้เห็นในปี 1981 ว่าการทดสอบรายบุคคลจะเป็นแบบ minmax เมื่อใด${\displaystyle n\leq \lfloor (5d+1)/2\rfloor }$และไม่ใช่ค่า minmax เมื่อ${\displaystyle n>3d}$[ ^{20 ] ปัจจุบันมีการคาดการณ์ว่าขอบเขตนี้มีความ แม่นยำ}กล่าวคือ การทดสอบแต่ละรายการจะเป็น minmax ก็ต่อเมื่อ${\displaystyle n\leq 3d}$[ ^{21 ] [ c ] Riccio และ Colbourn ได้มีความคืบ หน้า}บ้างในปี 2000 โดยแสดงให้เห็นว่าสำหรับขนาดใหญ่${\displaystyle n}$การทดสอบรายบุคคลคือค่าต่ำสุด-สูงสุดเมื่อ${\displaystyle d\geq n/\log _{3/2}(3)\approx 0.369n}$[ ^{22 ]​}

หนึ่งในข้อมูลเชิงลึกที่สำคัญในการทดสอบกลุ่มแบบไม่ปรับตัวคือ สามารถสร้างผลกำไรอย่างมีนัยสำคัญได้โดยการขจัดข้อกำหนดที่ว่ากระบวนการทดสอบกลุ่มจะต้องประสบความสำเร็จอย่างแน่นอน (ปัญหา "เชิงการจัดเรียง") แต่ให้มีความน่าจะเป็นต่ำแต่ไม่เป็นศูนย์ในการติดฉลากผิดพลาดในแต่ละรายการ (ปัญหา "เชิงความน่าจะเป็น") เป็นที่ทราบกันดีว่าเมื่อจำนวนรายการที่บกพร่องเข้าใกล้จำนวนรายการทั้งหมด วิธีแก้ปัญหาเชิงการจัดเรียงที่แน่นอนจะต้องใช้การทดสอบมากกว่าวิธีแก้ปัญหาเชิงความน่าจะเป็นอย่างมีนัยสำคัญ แม้แต่วิธีแก้ปัญหาเชิงความน่าจะเป็นที่อนุญาตให้มี ความน่าจะเป็น ของข้อผิดพลาด เพียง เล็กน้อยในเชิง อะซิมโทติกก็ตาม ^{[ 4 ] [ d ]}

ในทำนองเดียวกัน Chan et al. (2011) ได้นำเสนอCOMPซึ่งเป็นอัลกอริธึมเชิงความน่าจะเป็นที่ไม่ต้องการอะไรมากไปกว่า${\displaystyle t=ed(1+\delta )\ln(n)}$การทดสอบเพื่อค้นหาจนถึง${\displaystyle d}$ข้อบกพร่องใน${\displaystyle n}$รายการที่มีโอกาสผิดพลาดไม่เกิน${\displaystyle n^{-\delta }}$[ ^{6 ] ซึ่งอยู่ภายในปัจจัยคง ที่}ของ${\displaystyle t=O(d\log _{2}n)}$ขอบล่าง^{[ 4 ]}

Chan et al. (2011) ยังได้นำเสนอการวางนัยทั่วไปของ COMP ไปยังแบบจำลองที่มีเสียงรบกวนแบบง่าย และในทำนองเดียวกันได้สร้างขอบเขตประสิทธิภาพที่ชัดเจน ซึ่งเป็นค่าคงที่ (ขึ้นอยู่กับความน่าจะเป็นของการทดสอบที่ล้มเหลว) เหนือขอบเขตล่างที่สอดคล้องกัน^{[ 4 ] [ 6 ]}โดยทั่วไป จำนวนการทดสอบที่จำเป็นในกรณีเสียงรบกวนแบบเบอร์นูลลีเป็นปัจจัยคงที่ที่มากกว่าในกรณีที่ไม่มีเสียงรบกวน^{[ 6 ]}

Aldridge, Baldassini และ Johnson (2014) ได้สร้างส่วนขยายของอัลกอริทึม COMP ที่เพิ่มขั้นตอนการประมวลผลเพิ่มเติม^{[ 23 ]}พวกเขาแสดงให้เห็นว่าประสิทธิภาพของอัลกอริทึมใหม่นี้ ซึ่งเรียกว่าDDนั้นเหนือกว่า COMP อย่างเห็นได้ชัด และ DD นั้น 'เหมาะสมที่สุด' ในสถานการณ์ที่${\displaystyle d^{2}\geq n}$โดยการเปรียบเทียบกับอัลกอริทึมสมมุติที่กำหนดค่าที่เหมาะสมอย่างสมเหตุสมผล ประสิทธิภาพของอัลกอริทึมสมมุตินี้ชี้ให้เห็นว่ายังมีโอกาสที่จะปรับปรุงได้อีกเมื่อ${\displaystyle d^{2}<n}$รวมถึงแนะนำว่าการปรับปรุงนี้อาจเกิดขึ้นได้มากเพียงใด^{[ 23 ]}

เนื่องจากสามารถทำการทดสอบรายบุคคลได้เสมอโดยการตั้งค่า${\displaystyle S_{j}=\{j\}}$สำหรับแต่ละคน${\displaystyle 1\leq j\leq n}$มันต้องเป็นเช่นนั้น${\displaystyle {\bar {t}}(d,n)\leq n}$นอกจากนี้ เนื่องจากขั้นตอนการทดสอบที่ไม่ปรับตัวใดๆ ก็สามารถเขียนเป็นอัลกอริธึมแบบปรับตัวได้โดยการทำการทดสอบทั้งหมดโดยไม่คำนึงถึงผลลัพธ์${\displaystyle t(d,n)\leq {\bar {t}}(d,n)}$สุดท้ายแล้ว เมื่อ${\displaystyle 0\neq d\neq n}$มีอย่างน้อยหนึ่งรายการที่ต้องตรวจสอบความบกพร่อง (โดยการทดสอบอย่างน้อยหนึ่งครั้ง) และดังนั้น${\displaystyle 1\leq t(d,n)}$.

โดยสรุป (เมื่อสมมติว่า${\displaystyle 0\neq d\neq n}$),${\displaystyle 1\leq t(d,n)\leq {\bar {t}}(d,n)\leq n}$[ ^{f ]​}

อัลกอริทึมสำหรับการทดสอบกลุ่มแบบไม่ปรับตัวประกอบด้วยสองขั้นตอนที่แตกต่างกัน ขั้นแรก จะมีการตัดสินใจว่าจะทำการทดสอบกี่ครั้งและจะรวมรายการใดบ้างในการทดสอบแต่ละครั้ง ในขั้นตอนที่สอง ซึ่งมักเรียกว่าขั้นตอนการถอดรหัส ผลลัพธ์ของการทดสอบกลุ่มแต่ละครั้งจะถูกวิเคราะห์เพื่อพิจารณาว่ารายการใดมีแนวโน้มที่จะมีข้อบกพร่อง ขั้นตอนแรกมักจะถูกเข้ารหัสในเมทริกซ์ดังต่อไปนี้^{[ 6 ]}

• สมมติว่ามีขั้นตอนการทดสอบกลุ่มแบบไม่ปรับตัวสำหรับ${\displaystyle n}$รายการต่างๆ ประกอบด้วยการทดสอบ${\displaystyle S_{1},S_{2},\dots ,S_{t}}$สำหรับบางคน${\displaystyle t\in \mathbb {N} _{\geq 0}}$เมทริกซ์การทดสอบสำหรับแผนการนี้คือ${\displaystyle t\times n}$เมทริกซ์ไบนารี${\displaystyle M}$, ที่ไหน${\displaystyle (M)_{ij}=1}$ก็ต่อเมื่อ${\displaystyle j\in S_{i}}$(และมีค่าเป็นศูนย์ในกรณีอื่น ๆ)

ดังนั้นแต่ละคอลัมน์ของ${\displaystyle M}$แต่ละแถวแทนการทดสอบ โดยมี${\displaystyle 1}$ใน${\displaystyle (i,j){\textrm {-th}}}$รายการที่ระบุว่า${\displaystyle i{\textrm {-th}}}$การทดสอบรวมถึง${\displaystyle j{\textrm {-th}}}$รายการและ${\displaystyle 0}$แสดงให้เห็นเป็นอย่างอื่น

รวมถึงเวกเตอร์ด้วย${\displaystyle \mathbf {x} }$(ความยาว)${\displaystyle n}$) ซึ่งอธิบายถึงชุดข้อบกพร่องที่ไม่ทราบที่มา โดยทั่วไปแล้วมักจะมีการนำเวกเตอร์ผลลัพธ์มาใช้ ซึ่งอธิบายถึงผลลัพธ์ของการทดสอบแต่ละครั้ง

• อนุญาต${\displaystyle t}$เป็นจำนวนการทดสอบที่ดำเนินการโดยอัลกอริทึมที่ไม่ปรับตัวเวกเตอร์ผลลัพธ์ ,${\displaystyle \mathbf {y} =(y_{1},y_{2},\dots ,y_{t})}$เป็นเวกเตอร์ไบนารีที่มีความยาว${\displaystyle t}$(นั่นคือ${\displaystyle \mathbf {y} \in \{0,1\}^{t}}$) โดยที่${\displaystyle y_{i}=1}$ก็ต่อเมื่อผลลัพธ์ของ${\displaystyle i{\textrm {-th}}}$ผลการทดสอบเป็นบวก (กล่าวคือ พบว่ามีข้อบกพร่องอย่างน้อยหนึ่งรายการ) ^{[ g ]}

ด้วยคำจำกัดความเหล่านี้ ปัญหาที่ไม่สามารถปรับตัวได้สามารถกำหนดกรอบใหม่ได้ดังนี้ ขั้นแรกต้องเลือกเมทริกซ์การทดสอบ${\displaystyle M}$หลังจากนั้นเวกเตอร์${\displaystyle \mathbf {y} }$ส่งคืนแล้ว ปัญหาคือการวิเคราะห์${\displaystyle \mathbf {y} }$เพื่อหาค่าประมาณบางอย่างสำหรับ${\displaystyle \mathbf {x} }$.

ในกรณีที่มีสัญญาณรบกวนน้อยที่สุด ซึ่งมีความน่าจะเป็นคงที่${\displaystyle q}$เนื่องจากการทดสอบแบบกลุ่มจะให้ผลลัพธ์ที่ผิดพลาด จึงพิจารณาเวกเตอร์ไบนารีแบบสุ่ม${\displaystyle \mathbf {v} }$โดยที่แต่ละรายการมีความน่าจะเป็น${\displaystyle q}$ของการเป็น${\displaystyle 1}$และเป็น${\displaystyle 0}$มิฉะนั้น เวกเตอร์ที่ส่งคืนจะเป็นดังนี้${\displaystyle {\hat {\mathbf {y} }}=\mathbf {y} +\mathbf {v} }$โดยมีการเพิ่มเติมตามปกติใน${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$(เทียบเท่ากับ การดำเนินการ XOR แบบทีละองค์ประกอบ ) อัลกอริทึมที่มีสัญญาณรบกวนจะต้องประมาณค่า${\displaystyle \mathbf {x} }$โดยใช้${\displaystyle {\hat {\mathbf {y} }}}$(นั่นคือ โดยปราศจากความรู้โดยตรงเกี่ยวกับ${\displaystyle \mathbf {y} }$). ^{[ 6 ]}

การนำเสนอในรูปแบบเมทริกซ์ทำให้สามารถพิสูจน์ขอบเขตบางประการของการทดสอบกลุ่มแบบไม่ปรับตัวได้ แนวทางนี้คล้ายคลึงกับการออกแบบเชิงกำหนดหลายรูปแบบ ซึ่ง${\displaystyle d}$เมทริกซ์ที่แยกได้จะถูกพิจารณาตามที่กำหนดไว้ด้านล่าง^{[ 8 ]}

• เมทริกซ์ไบนารี${\displaystyle M}$เรียกว่า${\displaystyle d}$-แยกได้หากผลรวมบูลีนทุกค่า (ตรรกะ OR) ของค่าใดๆ${\displaystyle d}$ลักษณะของคอลัมน์นั้นแตกต่างกัน นอกจากนี้ สัญลักษณ์ยัง...${\displaystyle {\bar {d}}}$-separableบ่งชี้ว่าผลรวมทุกค่าของจำนวนใดๆ ก็ตามไม่เกิน${\displaystyle d}$ของ${\displaystyle M}$คอลัมน์ของนั้นแตกต่างกัน (ซึ่งไม่เหมือนกับ)${\displaystyle M}$สิ่งมีชีวิต${\displaystyle k}$-แยกได้สำหรับทุกๆ${\displaystyle k\leq d}$.)

เมื่อไร${\displaystyle M}$เป็นเมทริกซ์การทดสอบ คุณสมบัติของการเป็น${\displaystyle d}$-แยกได้ (${\displaystyle {\bar {d}}}$(แยกได้) เทียบเท่ากับความสามารถในการแยกแยะระหว่าง (ไม่เกิน)${\displaystyle d}$ข้อบกพร่อง อย่างไรก็ตาม มันไม่ได้รับประกันว่าสิ่งนี้จะราบรื่น คุณสมบัติที่แข็งแกร่งกว่าที่เรียกว่าความไม่ต่อเนื่องจะรับประกันได้

• เมทริกซ์ไบนารี${\displaystyle M}$เรียกว่า${\displaystyle d}$-แยกส่วนหากผลรวมบูลีนของใดๆ${\displaystyle d}$คอลัมน์ A ไม่ประกอบด้วยคอลัมน์อื่นใด (ในบริบทนี้ คอลัมน์ A จะกล่าวได้ว่าประกอบด้วยคอลัมน์ B ถ้าสำหรับทุกดัชนีที่ B มีค่าเป็น 1 แล้ว A ก็มีค่าเป็น 1 ด้วย)

คุณสมบัติที่มีประโยชน์อย่างหนึ่งของ${\displaystyle d}$เมทริกซ์การทดสอบแบบแยกส่วน - คือเมทริกซ์ที่มีขนาดสูงสุดถึง${\displaystyle d}$สินค้าชำรุด ทุกชิ้นที่ไม่ชำรุดจะปรากฏในการทดสอบอย่างน้อยหนึ่งครั้งซึ่งผลลัพธ์เป็นลบ นั่นหมายความว่ามีขั้นตอนง่ายๆ ในการค้นหาสินค้าชำรุด นั่นคือ นำสินค้าทุกชิ้นที่ปรากฏในการทดสอบที่เป็นลบออกไป

โดยใช้คุณสมบัติของ${\displaystyle d}$-แยกได้และ${\displaystyle d}$สำหรับเมทริกซ์ที่ไม่ต่อเนื่องกัน สามารถแสดงได้ดังต่อไปนี้สำหรับปัญหาการระบุตัวตน${\displaystyle d}$ข้อบกพร่องในหมู่${\displaystyle n}$จำนวนรายการทั้งหมด^{[ 4 ]}

1. จำนวนการทดสอบที่จำเป็นเพื่อให้ได้ ความน่าจะ เป็นเฉลี่ยของข้อผิดพลาดที่น้อยมากในเชิงอะซิมโทติกจะแปรผันตาม${\displaystyle O(d\log _{2}n)}$.
2. จำนวนการทดสอบที่จำเป็นสำหรับ ความน่าจะ เป็นสูงสุดของข้อผิดพลาดที่น้อยมากในเชิงอะซิมโทติกจะแปรผันตาม${\displaystyle O(d^{2}\log _{2}n)}$.
3. จำนวนการทดสอบที่จำเป็นเพื่อให้มีโอกาสผิดพลาดเป็นศูนย์ นั้นแปรผันตาม${\displaystyle O\left({\frac {d^{2}\log _{2}n}{\log _{2}d}}\right)}$.

Combinatorial Orthogonal Matching Pursuitหรือ COMP เป็นอัลกอริธึมการทดสอบกลุ่มแบบไม่ปรับตัวที่เรียบง่าย ซึ่งเป็นพื้นฐานสำหรับอัลกอริธึมที่ซับซ้อนกว่าที่จะกล่าวถึงต่อไปในส่วนนี้

ขั้นแรก แต่ละรายการในเมทริกซ์การทดสอบจะถูกเลือกให้เป็นแบบ อิสระและมีการกระจายเหมือนกัน (iid)${\displaystyle 1}$ด้วยความน่าจะเป็น${\displaystyle 1/d}$และ${\displaystyle 0}$มิฉะนั้น.

ขั้นตอนการถอดรหัสจะดำเนินการตามคอลัมน์ (เช่น ตามรายการ) หากการทดสอบทุกครั้งที่รายการนั้นปรากฏให้ผลลัพธ์เป็นบวก รายการนั้นจะถูกประกาศว่าชำรุด มิเช่นนั้นจะถือว่ารายการนั้นไม่ชำรุด หรือกล่าวอีกนัยหนึ่ง หากรายการใดปรากฏในการทดสอบใดๆ ที่มีผลลัพธ์เป็นลบ รายการนั้นจะถูกประกาศว่าไม่ชำรุด มิเช่นนั้นจะถือว่ารายการนั้นชำรุด คุณสมบัติที่สำคัญของอัลกอริทึมนี้คือจะไม่เกิดผลลัพธ์ที่เป็นเท็จเชิงลบแม้ว่า จะเกิด ผลลัพธ์ที่เป็นเท็จเชิงบวกเมื่อตำแหน่งทั้งหมดที่มีค่าหนึ่งใน คอลัมน์ที่ jของรายการนั้นเป็น 1 ก็ตาม${\displaystyle M}$ค่า (ที่สอดคล้องกับสินค้าที่ไม่ชำรุดj ) จะถูก "ซ่อน" ด้วยค่าของคอลัมน์อื่นที่สอดคล้องกับสินค้าชำรุด

อัลกอริทึม COMP ต้องการเพียงเท่านี้${\displaystyle ed(1+\delta )\ln(n)}$การทดสอบเพื่อให้มีโอกาสเกิดข้อผิดพลาดน้อยกว่าหรือเท่ากับ${\displaystyle n^{-\delta }}$[ ^{6 ]}ซึ่งอยู่ภายในปัจจัยคงที่ของขอบล่างสำหรับความน่าจะเป็นเฉลี่ยของข้อผิดพลาดข้าง^ต้น

ในกรณีที่มีสัญญาณรบกวน เราจะผ่อนปรนข้อกำหนดในอัลกอริธึม COMP ดั้งเดิมที่ว่าเซตของตำแหน่งเลขหนึ่งในคอลัมน์ใดๆ ของ${\displaystyle M}$ค่าที่สอดคล้องกับรายการที่เป็นบวกจะต้องอยู่ภายในชุดตำแหน่งของค่าหนึ่งในเวกเตอร์ผลลัพธ์เท่านั้น แต่ในทางกลับกัน เราอนุญาตให้มี "ความไม่ตรงกัน" ได้จำนวนหนึ่ง ซึ่งจำนวนความไม่ตรงกันนี้ขึ้นอยู่กับทั้งจำนวนค่าหนึ่งในแต่ละคอลัมน์ และพารามิเตอร์ของสัญญาณรบกวนด้วย${\displaystyle q}$อัลกอริทึม COMP ที่มีเสียงรบกวนนี้ต้องการเพียงเท่านี้${\displaystyle 4.36({\sqrt {\delta }}+{\sqrt {1+\delta }})^{2}(1-2q)^{-2}d\log _{2}{n}}$การทดสอบเพื่อให้ได้ความน่าจะเป็นของข้อผิดพลาดสูงสุด${\displaystyle n^{-\delta }}$[ ^{6 ]​}

วิธีการตรวจสอบข้อบกพร่องที่แน่นอน (DD) เป็นส่วนขยายของอัลกอริธึม COMP ที่พยายามกำจัดผลบวกเท็จ การรับประกันประสิทธิภาพของ DD ได้รับการพิสูจน์แล้วว่าเหนือกว่า COMP อย่างชัดเจน^{[ 23 ]}

ขั้นตอนการถอดรหัสใช้คุณสมบัติที่มีประโยชน์ของอัลกอริธึม COMP คือ ทุกรายการที่ COMP ประกาศว่าไม่ชำรุดนั้น จะไม่ชำรุดอย่างแน่นอน (กล่าวคือ ไม่มีผลลัพธ์ที่เป็นเท็จเชิงลบ) โดยดำเนินการดังต่อไปนี้

1. ขั้นแรก ระบบจะเรียกใช้ขั้นตอนวิธี COMP และคัดชิ้นส่วนที่ไม่ชำรุดออก ชิ้นส่วนที่เหลือทั้งหมดจะถูกจัดอยู่ในสถานะ "อาจมีข้อบกพร่อง"
2. ขั้นตอนต่อไป อัลกอริทึมจะตรวจสอบผลการทดสอบที่เป็นบวกทั้งหมด หากพบว่ารายการใดปรากฏเป็น "รายการที่อาจมีข้อบกพร่อง" เพียงรายการเดียวในการทดสอบ แสดงว่ารายการนั้นมีข้อบกพร่อง ดังนั้นอัลกอริทึมจึงประกาศว่ารายการนั้นมีข้อบกพร่อง
3. สินค้าอื่นๆ ทั้งหมดถือว่าไม่มีข้อบกพร่อง เหตุผลสำหรับขั้นตอนสุดท้ายนี้มาจากการสมมติฐานที่ว่าจำนวนสินค้าที่มีข้อบกพร่องนั้นน้อยกว่าจำนวนสินค้าทั้งหมดมาก

โปรดทราบว่าขั้นตอนที่ 1 และ 2 จะไม่มีวันผิดพลาด ดังนั้นอัลกอริทึมจะผิดพลาดได้ก็ต่อเมื่อมันประกาศว่าสินค้าที่ชำรุดนั้นไม่ชำรุดเท่านั้น ดังนั้นอัลกอริทึม DD จึงสร้างผลลัพธ์ที่เป็นเท็จเชิงลบได้เท่านั้น

SCOMP (Sequential COMP) เป็นอัลกอริทึมที่ใช้ประโยชน์จากข้อเท็จจริงที่ว่า DD จะไม่เกิดข้อผิดพลาดจนกว่าจะถึงขั้นตอนสุดท้าย ซึ่งถือว่ารายการที่เหลืออยู่ไม่มีข้อบกพร่อง ให้เซตของรายการที่ประกาศว่ามีข้อบกพร่องเป็น${\displaystyle K}$ผลการทดสอบที่เป็นบวกเรียกว่าอธิบายโดย${\displaystyle K}$หากมีอย่างน้อยหนึ่งรายการอยู่ในนั้น${\displaystyle K}$ข้อสังเกตที่สำคัญของ SCOMP คือ ชุดของข้อบกพร่องที่พบโดย DD อาจไม่สามารถอธิบายผลการทดสอบที่เป็นบวกทุกกรณีได้ และการทดสอบที่ไม่สามารถอธิบายได้ทุกกรณีจะต้องมีข้อบกพร่องที่ซ่อนอยู่

ขั้นตอนวิธีดำเนินการดังต่อไปนี้

1. ดำเนินการตามขั้นตอนที่ 1 และ 2 ของอัลกอริทึม DD เพื่อให้ได้ผลลัพธ์${\displaystyle K}$ซึ่งเป็นการประมาณเบื้องต้นสำหรับจำนวนของชิ้นส่วนที่ชำรุด
2. ถ้า${\displaystyle K}$หากผลการทดสอบเป็นบวกทุกครั้ง ให้ยุติการทำงานของอัลกอริทึม:${\displaystyle K}$เป็นค่าประมาณสุดท้ายสำหรับชุดของสินค้าที่ชำรุด
3. หากมีผลการทดสอบใดที่ไม่สามารถอธิบายได้ ให้ค้นหา "ชิ้นส่วนที่อาจมีข้อบกพร่อง" ที่ปรากฏในจำนวนผลการทดสอบที่ไม่สามารถอธิบายได้มากที่สุด และประกาศว่าชิ้นส่วนนั้นมีข้อบกพร่อง (กล่าวคือ เพิ่มเข้าไปในชุดข้อมูล)${\displaystyle K}$). ไปที่ขั้นตอนที่ 2.

ในการจำลอง SCOMP ได้รับการพิสูจน์แล้วว่าทำงานได้ใกล้เคียงกับค่าที่เหมาะสมที่สุด^{[ 23 ]}

Polynomial Pools (PP) เป็นอัลกอริทึมเชิงกำหนดที่รับประกันว่าจะระบุได้อย่างแม่นยำถึง${\displaystyle d}$ข้อดี^{[ 26 ]}อัลกอริทึมนี้ใช้สำหรับการสร้างเมทริกซ์พูลลิ่ง${\displaystyle M}$ซึ่งสามารถนำมาใช้ถอดรหัสข้อมูลสังเกตการณ์ได้โดยตรง${\displaystyle y}$เช่นเดียวกับ COMP ตัวอย่างจะถูกถอดรหัสตามความสัมพันธ์ดังนี้: ${\displaystyle x_{i}=1~~{\text{ if }}~~M(:,i)~.*~y=M(:,i)}$, ที่ไหน${\displaystyle .*}$แสดงถึงการคูณแบบทีละองค์ประกอบและ${\displaystyle M(:,i)}$คือ${\displaystyle i}$คอลัมน์ที่ th ของ${\displaystyle M}$เนื่องจากขั้นตอนการถอดรหัสไม่ยาก PP จึงมีความเชี่ยวชาญในการสร้างข้อมูล${\displaystyle M}$.

การรวมกลุ่ม

กลุ่ม/สระว่ายน้ำ${\displaystyle \ell }$สร้างขึ้นโดยใช้ความสัมพันธ์พหุนามที่ระบุถึงดัชนีของตัวอย่างที่อยู่ในแต่ละกลุ่ม ชุดของพารามิเตอร์อินพุตจะกำหนดอัลกอริทึม สำหรับจำนวนเฉพาะ${\displaystyle p>1}$และจำนวนเต็ม${\displaystyle n\geq 1}$กำลังของจำนวนเฉพาะใดๆถูกกำหนดโดย${\displaystyle q=p^{n}}$สำหรับพารามิเตอร์มิติ${\displaystyle c\geq 2}$จำนวนตัวอย่างทั้งหมดคือ${\displaystyle n=q^{c}}$และจำนวนตัวอย่างต่อกลุ่มคือ${\displaystyle q^{c-1}}$นอกจากนี้ ฟิลด์จำกัดอันดับ${\displaystyle q}$ถูกกำหนดโดย${\displaystyle \mathbb {F} _{q}}$ (เช่น จำนวนเต็ม)${\displaystyle \{0,1,2,\ldots ,q-1\}}$กำหนดโดยการดำเนินการทางคณิตศาสตร์พิเศษที่รับประกันว่าการบวกและการคูณใน${\displaystyle \mathbb {F} _{q}}$ยังคงอยู่ใน${\displaystyle \mathbb {F} _{q}}$วิธีการนี้จะจัดเรียงตัวอย่างแต่ละชิ้นลงในตารางและแสดงผลด้วยพิกัด${\displaystyle x=(u,v)}$พิกัดจะถูกคำนวณตามความสัมพันธ์พหุนามโดยใช้จำนวนเต็ม ${\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}.}$

การรวมกันของการวนซ้ำผ่าน${\displaystyle u_{i_{l}}}$ค่าต่างๆ จะถูกแทนด้วยเซตที่มี${\displaystyle q^{c-1}}$องค์ประกอบของลำดับ${\displaystyle d-1}$จำนวนเต็ม เช่น ${\displaystyle u_{i_{1}}\times \cdots \times u_{i_{c-1}}=\{(i_{1},\ldots ,i_{c-1})\}}$, ที่ไหน ${\displaystyle 0\leq i_{l}\leq q-1}$โดยไม่เสียความเป็นทั่วไปการรวมกันนั้นเป็นดังนี้ ${\displaystyle i_{d-1}}$รอบทุกๆ${\displaystyle q}$ครั้ง${\displaystyle i_{d-2}}$รอบทุกๆ${\displaystyle q^{2}}$ครั้งจนถึง ${\displaystyle i_{1}}$รอบการทำงานเพียงครั้งเดียวเท่านั้น สูตรที่คำนวณดัชนีตัวอย่าง และกลุ่มที่เกี่ยวข้อง สำหรับค่าคงที่${\displaystyle a}$และ${\displaystyle b}$ได้รับจาก

${\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}}}$

การคำนวณใน${\displaystyle \mathbb {F} _{q}}$สามารถนำไปใช้งานได้โดยใช้ไลบรารีซอฟต์แวร์ที่เปิดเผยต่อสาธารณะสำหรับฟิลด์จำกัด เมื่อ${\displaystyle q}$เป็นกำลังหลัก เมื่อ${\displaystyle q}$ถ้าเป็นจำนวนเฉพาะ การคำนวณใน${\displaystyle \mathbb {F} _{q}}$ลดรูปเป็นการคำนวณค่าสัมบูรณ์ กล่าวคือ${\displaystyle v_{u_{i}}=(\sum _{l=1}^{c-1}a^{l}i_{l}+b)~{\text{mod}}~q}$ตัวอย่างวิธีการสร้างพูลหนึ่งพูล${\displaystyle \ell }$เมื่อไร ${\displaystyle a=1,b=0,c=2}$ข้อมูลแสดงอยู่ในตารางด้านล่าง ในขณะที่ตัวอย่างที่เลือกไว้ที่สอดคล้องกันแสดงอยู่ในรูปภาพด้านบน

การคำนวณพูลเดียว${\displaystyle \ell }$โดยใช้ PP กับ${\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}}$

วิธีการนี้ใช้${\displaystyle q(c-1)(d+1)}$การทดสอบเพื่อระบุได้อย่างแม่นยำถึง${\displaystyle d}$ข้อดีในหมู่${\displaystyle n=q^{c}}$ตัวอย่าง ด้วยเหตุนี้ PP จึงมีประสิทธิภาพเป็นพิเศษสำหรับตัวอย่างขนาดใหญ่ เนื่องจากจำนวนการทดสอบเพิ่มขึ้นเป็นเส้นตรงเท่านั้นเมื่อเทียบกับ${\displaystyle c}$ในขณะที่ตัวอย่างเติบโตแบบทวีคูณด้วยพารามิเตอร์นี้ อย่างไรก็ตาม PP ก็สามารถมีประสิทธิภาพสำหรับขนาดตัวอย่างเล็กได้เช่นกัน^{[ 26 ]}

ช่องสัญญาณมัลติแอ็กเซสคือช่องทางการสื่อสารที่เชื่อมต่อผู้ใช้หลายคนพร้อมกัน ผู้ใช้แต่ละคนสามารถรับฟังและส่งสัญญาณบนช่องสัญญาณได้ แต่หากมีผู้ใช้มากกว่าหนึ่งรายส่งสัญญาณในเวลาเดียวกัน สัญญาณจะชนกันและลดลงจนกลายเป็นสัญญาณรบกวนที่ไม่สามารถเข้าใจได้ ช่องสัญญาณมัลติแอ็กเซสมีความสำคัญต่อการใช้งานจริงต่างๆ โดยเฉพาะเครือข่ายคอมพิวเตอร์ไร้สายและเครือข่ายโทรศัพท์^{[ 32 ]}

ปัญหาสำคัญอย่างหนึ่งของช่องสัญญาณแบบหลายผู้ใช้คือวิธีการจัดสรรเวลาการส่งข้อมูลให้กับผู้ใช้เพื่อไม่ให้ข้อความของพวกเขาทับซ้อนกัน วิธีที่ง่ายคือการให้ผู้ใช้แต่ละคนมีช่วงเวลาของตนเองในการส่งข้อมูล ซึ่งต้องใช้...${\displaystyle n}$ช่องสัญญาณ (เรียกว่าการแบ่งเวลาการส่งข้อมูลหรือ TDM) อย่างไรก็ตาม วิธีนี้ไม่มีประสิทธิภาพมากนัก เนื่องจากจะจัดสรรช่องสัญญาณส่งข้อมูลให้กับผู้ใช้ที่อาจไม่มีข้อความ และโดยปกติแล้วจะสันนิษฐานว่าจะมีผู้ใช้เพียงไม่กี่รายเท่านั้นที่ต้องการส่งข้อมูลในเวลาใดเวลาหนึ่ง มิเช่นนั้นแล้วช่องสัญญาณแบบหลายผู้ใช้ก็จะไม่สามารถใช้งานได้จริงตั้งแต่แรก

ในบริบทของการทดสอบแบบกลุ่ม ปัญหานี้มักจะได้รับการแก้ไขโดยการแบ่งเวลาออกเป็น 'ยุค' ในลักษณะต่อไปนี้^{[ 8 ]}ผู้ใช้จะถูกเรียกว่า 'ใช้งาน' หากพวกเขามีข้อความเมื่อเริ่มต้นยุค (หากมีการสร้างข้อความในระหว่างยุค ผู้ใช้จะใช้งานได้ก็ต่อเมื่อเริ่มต้นยุคถัดไปเท่านั้น) ยุคจะสิ้นสุดลงเมื่อผู้ใช้ที่ใช้งานอยู่ทุกคนได้ส่งข้อความสำเร็จแล้ว ปัญหาคือการค้นหาผู้ใช้ที่ใช้งานอยู่ทั้งหมดในยุคที่กำหนด และกำหนดเวลาให้พวกเขาส่งข้อความ (หากพวกเขายังไม่ได้ส่งสำเร็จ) ในที่นี้ การทดสอบกับกลุ่มผู้ใช้จะสอดคล้องกับผู้ใช้ที่พยายามส่งข้อความ ผลลัพธ์ของการทดสอบคือจำนวนผู้ใช้ที่พยายามส่งข้อความ${\displaystyle 0,1,}$และ${\displaystyle 2^{+}}$ซึ่งสอดคล้องกับกรณีที่ไม่มีผู้ใช้งานเลย ผู้ใช้งานที่ใช้งานอยู่หนึ่งคน (ส่งข้อความสำเร็จ) หรือผู้ใช้งานที่ใช้งานอยู่มากกว่าหนึ่งคน (ข้อความชนกัน) ตามลำดับ ดังนั้น การใช้อัลกอริธึมการทดสอบกลุ่มแบบปรับตัวได้พร้อมผลลัพธ์${\displaystyle \{0,1,2^{+}\}}$สามารถระบุได้ว่าผู้ใช้รายใดต้องการส่งข้อมูลในช่วงเวลานั้น จากนั้น ผู้ใช้รายใดที่ยังไม่เคยส่งข้อมูลสำเร็จมาก่อน สามารถได้รับการจัดสรรช่วงเวลาในการส่งข้อมูล โดยไม่ต้องเสียเวลาให้กับผู้ใช้ที่ไม่ได้ใช้งาน

การเรียนรู้ของเครื่องเป็นสาขาหนึ่งของวิทยาศาสตร์คอมพิวเตอร์ที่มีแอปพลิเคชันซอฟต์แวร์มากมาย เช่น การจำแนกดีเอ็นเอ การตรวจจับการฉ้อโกง และการโฆษณาแบบกำหนดเป้าหมายหนึ่งในสาขาย่อยหลักของการเรียนรู้ของเครื่องคือปัญหา 'การเรียนรู้จากตัวอย่าง' ซึ่งงานคือการประมาณค่าฟังก์ชันที่ไม่รู้จักเมื่อได้รับค่าของฟังก์ชันนั้น ณ จุดเฉพาะจำนวนหนึ่ง^{[ 8 ]}ดังที่ได้กล่าวไว้ในส่วนนี้ ปัญหาการเรียนรู้ฟังก์ชันนี้สามารถแก้ไขได้ด้วยวิธีการทดสอบแบบกลุ่ม

ในเวอร์ชันที่ง่ายที่สุดของปัญหานี้ มีฟังก์ชันที่ไม่ทราบค่าอยู่ฟังก์ชันหนึ่ง${\displaystyle f:\{0,1\}^{N}\to \{0,1\}}$ที่ไหน${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$, และ${\displaystyle {\textbf {a}}\in \{0,1\}^{N}}$(โดยใช้หลักตรรกะทางคณิตศาสตร์: การบวกคือการดำเนินการทางตรรกะแบบ OR และการคูณคือการดำเนินการทางตรรกะแบบ AND) ตรงนี้${\displaystyle {\textbf {a}}}$เป็น '${\displaystyle d}$'เบาบาง' ซึ่งหมายความว่าอย่างมากที่สุด${\displaystyle d\ll N}$ของรายการต่างๆ คือ${\displaystyle 1}$จุดมุ่งหมายคือการสร้างค่าประมาณของ${\displaystyle f}$โดยใช้${\displaystyle t}$การประเมินคะแนน โดยที่${\displaystyle t}$มีขนาดเล็กที่สุดเท่าที่จะเป็นไปได้^{[ 4 ]} (การกู้คืนอย่างแม่นยำ)${\displaystyle f}$สอดคล้องกับอัลกอริธึมที่ไม่มีข้อผิดพลาด ในขณะที่${\displaystyle f}$(ประมาณค่าโดยใช้อัลกอริธึมที่มีโอกาสเกิดข้อผิดพลาดไม่เป็นศูนย์)

ในปัญหานี้ การกู้คืน${\displaystyle f}$เทียบเท่ากับการค้นหา${\displaystyle {\textbf {a}}}$. นอกจากนี้,${\displaystyle f({\textbf {p}})=1}$ก็ต่อเมื่อมีดัชนีบางอย่างเท่านั้น${\displaystyle n}$, ที่ไหน${\displaystyle {\textbf {a}}_{n}={\textbf {p}}_{n}=1}$ดังนั้น ปัญหานี้จึงคล้ายคลึงกับปัญหาการทดสอบแบบกลุ่มที่มี${\displaystyle d}$ของชำรุดและ${\displaystyle n}$จำนวนรายการทั้งหมด รายการของ${\displaystyle {\textbf {a}}}$คือสินค้าที่ถือว่ามีข้อบกพร่องหากเป็นดังนี้${\displaystyle 1}$,${\displaystyle {\textbf {p}}}$ระบุการทดสอบ และการทดสอบจะเป็นผลบวกก็ต่อเมื่อ${\displaystyle f({\textbf {p}})=1}$[ ^{4 ]​}

ในความเป็นจริงแล้ว ผู้คนมักจะสนใจฟังก์ชันที่ซับซ้อนกว่า เช่น${\displaystyle f:\mathbb {C} ^{N}\to \mathbb {C} }$อีกครั้งที่ไหน${\displaystyle f({\textbf {x}})={\textbf {a}}\cdot {\textbf {x}}}$การตรวจจับแบบบีบอัดซึ่งมีความเกี่ยวข้องอย่างใกล้ชิดกับการทดสอบแบบกลุ่ม สามารถนำมาใช้แก้ปัญหานี้ได้^{[ 4 ]}

ในการตรวจจับแบบบีบอัด เป้าหมายคือการสร้างสัญญาณขึ้นมาใหม่${\displaystyle {\textbf {v}}\in \mathbb {C} ^{N}}$โดยการวัดค่าหลายๆ ค่า การวัดเหล่านี้จำลองได้โดยการหาผลคูณดอทของค่าต่างๆ${\displaystyle {\textbf {v}}}$ด้วยเวกเตอร์ที่เลือก^{[ h ]}จุดมุ่งหมายคือการใช้การวัดจำนวนน้อย แม้ว่าโดยทั่วไปแล้วจะไม่สามารถทำได้เว้นแต่จะมีการสมมติบางอย่างเกี่ยวกับสัญญาณ สมมติฐานหนึ่งดังกล่าว (ซึ่งเป็นเรื่องปกติ^{[ 35 ] [ 36 ]} ) คือมีเพียงรายการจำนวนเล็กน้อยของ${\displaystyle {\textbf {v}}}$มีความสำคัญหมายความว่ามีขนาดใหญ่ เนื่องจากค่าที่วัดได้เป็นผลคูณดอทของ${\displaystyle {\textbf {v}}}$สมการ${\displaystyle M{\textbf {v}}={\textbf {q}}}$ถือครองที่${\displaystyle M}$เป็น${\displaystyle t\times N}$เมทริกซ์ที่อธิบายชุดของการวัดที่ได้รับการเลือกและ${\displaystyle \mathbf {q} }$คือชุดของผลการวัด โครงสร้างนี้แสดงให้เห็นว่าการตรวจจับแบบบีบอัด (compressed sensing) เป็นการทดสอบกลุ่มแบบ 'ต่อเนื่อง' ประเภทหนึ่ง

ความยากลำบากหลักในการตรวจจับแบบบีบอัดคือการระบุว่ารายการใดมีความสำคัญ^{[ 35 ]}เมื่อทำเช่นนั้นแล้ว ก็มีวิธีการต่างๆ มากมายในการประมาณค่าจริงของรายการ^{[ 37 ]}งานการระบุนี้สามารถทำได้ด้วยการประยุกต์ใช้การทดสอบแบบกลุ่มอย่างง่าย การทดสอบแบบกลุ่มจะสร้างจำนวนเชิงซ้อน : ผลรวมของรายการที่ได้รับการทดสอบ ผลลัพธ์ของการทดสอบเรียกว่าเป็นบวกหากสร้างจำนวนเชิงซ้อนที่มีขนาดใหญ่ ซึ่งเมื่อพิจารณาจากสมมติฐานที่ว่ารายการที่มีนัยสำคัญนั้นกระจัดกระจาย แสดงว่าอย่างน้อยหนึ่งรายการที่มีนัยสำคัญนั้นมีอยู่ในการทดสอบ

มีโครงสร้างเชิงกำหนดที่ชัดเจนสำหรับอัลกอริธึมการค้นหาเชิง การจัดเรียงประเภทนี้ ซึ่งต้องใช้${\displaystyle d2^{(\log _{2}\log _{2}N)^{O(1)}}}$การวัด^{[ 38 ]}อย่างไรก็ตาม เช่นเดียวกับการทดสอบกลุ่ม สิ่งเหล่านี้ไม่เหมาะสม และโครงสร้างแบบสุ่ม (เช่น COMP) มักจะสามารถกู้คืนได้${\displaystyle f}$น้อยกว่าเชิงเส้นใน${\displaystyle N}$[ ^{37 ]​}

ในช่วงการระบาดใหญ่ เช่น การระบาดของ COVID-19 ในปี 2020 บางครั้งการทดสอบการตรวจจับไวรัสจะดำเนินการโดยใช้การออกแบบการทดสอบกลุ่มแบบไม่ปรับตัว^{[ 39 ] [ 40 ] [ 41 ]} ตัวอย่างหนึ่งคือโครงการ Origami Assays ซึ่งเผยแพร่การออกแบบการทดสอบกลุ่มแบบโอเพนซอร์สเพื่อใช้งานบนแผ่น 96 หลุมมาตรฐานของห้องปฏิบัติการ^{[ 42 ]}

ในการตั้งค่าห้องปฏิบัติการ ความท้าทายอย่างหนึ่งของการทดสอบแบบกลุ่มคือการสร้างส่วนผสมอาจใช้เวลานานและยากที่จะทำได้อย่างแม่นยำด้วยมือ การทดสอบแบบโอริกามิได้ให้วิธีแก้ปัญหาสำหรับปัญหาการสร้างนี้โดยการจัดเตรียมแม่แบบกระดาษเพื่อแนะนำช่างเทคนิคเกี่ยวกับวิธีการจัดสรรตัวอย่างของผู้ป่วยลงในหลุมทดสอบ^{[ 43 ]}

เมื่อใช้การออกแบบการทดสอบกลุ่มที่ใหญ่ที่สุด (XL3) สามารถทดสอบตัวอย่างผู้ป่วยได้ 1120 รายในหลุมทดสอบ 94 หลุม หากอัตราการตรวจพบผลบวกที่แท้จริงต่ำเพียงพอ ก็ไม่ต้องทำการทดสอบเพิ่มเติม

นิติวิทยาศาสตร์ข้อมูลเป็นสาขาที่มุ่งเน้นการค้นหาวิธีการรวบรวมหลักฐานดิจิทัลของอาชญากรรม อาชญากรรมดังกล่าวโดยทั่วไปเกี่ยวข้องกับการที่ฝ่ายตรงข้ามแก้ไขข้อมูล เอกสาร หรือฐานข้อมูลของเหยื่อ ตัวอย่างเช่น การเปลี่ยนแปลงบันทึกภาษี ไวรัสที่ซ่อนตัว หรือการที่ผู้ขโมยข้อมูลส่วนบุคคลแก้ไขข้อมูลส่วนบุคคล^{[ 31 ]}

เครื่องมือที่ใช้กันทั่วไปในการวิเคราะห์ข้อมูลคือแฮชเข้ารหัสแบบทางเดียวนี่คือฟังก์ชันที่รับข้อมูล และผ่านกระบวนการที่ยากต่อการย้อนกลับ จะสร้างหมายเลขที่ไม่ซ้ำกันเรียกว่าแฮช^{[ i ]}แฮชซึ่งมักจะสั้นกว่าข้อมูลมาก ช่วยให้เราตรวจสอบได้ว่าข้อมูลมีการเปลี่ยนแปลงหรือไม่โดยไม่ต้องจัดเก็บสำเนาข้อมูลทั้งหมดอย่างสิ้นเปลือง: สามารถเปรียบเทียบแฮชของข้อมูลปัจจุบันกับแฮชในอดีตเพื่อพิจารณาว่ามีการเปลี่ยนแปลงใดเกิดขึ้นหรือไม่ คุณสมบัติที่ไม่พึงประสงค์ของวิธีนี้คือ แม้ว่าจะบอกได้ง่ายว่าข้อมูลได้รับการแก้ไขหรือไม่ แต่ก็ไม่มีวิธีใดที่จะระบุได้ว่าแก้ไขอย่างไร นั่นคือ เป็นไปไม่ได้ที่จะกู้คืนว่าส่วนใดของข้อมูลมีการเปลี่ยนแปลง^{[ 31 ]}

วิธีหนึ่งที่จะหลีกเลี่ยงข้อจำกัดนี้คือการจัดเก็บแฮชเพิ่มเติม – โดยตอนนี้เป็นชุดย่อยของโครงสร้างข้อมูล – เพื่อจำกัดขอบเขตของการโจมตีให้แคบลง อย่างไรก็ตาม หากต้องการค้นหาตำแหน่งที่แน่นอนของการโจมตีด้วยวิธีการแบบง่ายๆ จะต้องจัดเก็บแฮชสำหรับข้อมูลทุกรายการในโครงสร้าง ซึ่งจะทำให้จุดประสงค์ของการใช้แฮชนั้นไร้ประโยชน์ (อาจจะจัดเก็บสำเนาข้อมูลปกติไปเลยก็ได้) การทดสอบแบบกลุ่มสามารถใช้เพื่อลดจำนวนแฮชที่ต้องจัดเก็บลงได้อย่างมาก การทดสอบจะเป็นการเปรียบเทียบระหว่างแฮชที่จัดเก็บไว้กับแฮชปัจจุบัน ซึ่งจะให้ผลเป็นบวกเมื่อไม่ตรงกัน ซึ่งบ่งชี้ว่ามีข้อมูลที่แก้ไขอย่างน้อยหนึ่งรายการ (ซึ่งถือว่าเป็นข้อบกพร่องในแบบจำลองนี้) อยู่ในกลุ่มที่สร้างแฮชปัจจุบัน^{[ 31 ]}

ในความเป็นจริง จำนวนแฮชที่ต้องการนั้นต่ำมากจนสามารถจัดเก็บไว้ภายในโครงสร้างองค์กรของข้อมูลเองได้ พร้อมกับเมทริกซ์การทดสอบที่อ้างถึง ซึ่งหมายความว่าการทดสอบสามารถดำเนินการได้ 'ฟรี' ในแง่ของหน่วยความจำ (ซึ่งเป็นความจริง ยกเว้นคีย์หลัก/รหัสผ่านที่ใช้ในการกำหนดฟังก์ชันแฮชอย่างลับๆ) ^{[ 31 ]}