ในสถิติและคณิตศาสตร์เชิงการจัดเรียงการทดสอบแบบกลุ่มคือกระบวนการใดๆ ที่แบ่งงานการระบุวัตถุออกเป็นการทดสอบกับกลุ่มของรายการ แทนที่จะทดสอบแต่ละรายการทีละรายการ การทดสอบแบบกลุ่มได้รับการศึกษาครั้งแรกโดยโรเบิร์ต ดอร์ฟแมนในปี 1943 เป็นสาขาใหม่ของคณิตศาสตร์ที่สามารถนำไปประยุกต์ใช้ในทางปฏิบัติได้หลากหลาย และเป็นหัวข้อการวิจัยที่กำลังได้รับความสนใจอย่างมากในปัจจุบัน

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

แผนการทดสอบแบบกลุ่มอาจมีความเรียบง่ายหรือซับซ้อน และการทดสอบที่เกี่ยวข้องในแต่ละขั้นตอนอาจแตกต่างกัน แผนการที่การทดสอบในขั้นตอนต่อไปขึ้นอยู่กับผลลัพธ์ของขั้นตอนก่อนหน้าเรียกว่าขั้นตอนแบบปรับเปลี่ยนได้ (adaptive procedures ) ในขณะที่แผนการที่ออกแบบมาเพื่อให้ทราบการทดสอบทั้งหมดล่วงหน้าเรียกว่า ขั้นตอนแบบ ไม่ปรับเปลี่ยนได้ (non-adaptive procedures ) โครงสร้างของแผนการทดสอบที่เกี่ยวข้องในขั้นตอนแบบไม่ปรับเปลี่ยนได้เรียกว่าการออกแบบแบบรวมกลุ่ม (pooling design )

การทดสอบแบบกลุ่มมีการใช้งานมากมาย รวมถึงสถิติ ชีววิทยา วิทยาการคอมพิวเตอร์ การแพทย์ วิศวกรรม และความปลอดภัยทางไซเบอร์ ความสนใจสมัยใหม่ในแผนการทดสอบเหล่านี้ได้รับการจุดประกายขึ้นอีกครั้งโดย^{โครงการ}จีโนมมนุษย์ [ ^{1 ]}

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

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

โดยทั่วไปแล้ว รายการที่ทำให้กลุ่มมีผลการทดสอบเป็นบวกจะเรียกว่ารายการที่ชำรุด (เช่น หลอดไฟแตก ผู้ชายที่เป็นโรคซิฟิลิส เป็นต้น) บ่อยครั้งที่จำนวนรายการทั้งหมดจะถูกระบุเป็นและแสดงถึงจำนวนรายการที่ชำรุดหากถือว่าทราบแล้ว^{[ 3 ]}${\displaystyle n}$${\displaystyle d}$

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

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

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

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

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

การขยายเพิ่มเติมอีกอย่างหนึ่งคือการพิจารณาข้อจำกัดทางเรขาคณิตเกี่ยวกับชุดที่สามารถทดสอบได้ ปัญหาหลอดไฟข้างต้นเป็นตัวอย่างของข้อจำกัดประเภทนี้: เฉพาะหลอดไฟที่ปรากฏต่อเนื่องกันเท่านั้นที่สามารถทดสอบได้ ในทำนองเดียวกัน รายการต่างๆ อาจถูกจัดเรียงเป็นวงกลม หรือโดยทั่วไปเป็นโครงข่าย โดยที่การทดสอบเป็นเส้นทางที่ใช้ได้บนกราฟ ข้อจำกัดทางเรขาคณิตอีกประเภทหนึ่งคือจำนวนรายการสูงสุดที่สามารถทดสอบได้ในกลุ่ม^{[ 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 แสดงให้เห็นว่าหากอัตราความชุกโดยที่การทดสอบรายบุคคลจะเป็นขั้นตอนการทดสอบกลุ่มที่เหมาะสมที่สุดเมื่อพิจารณาจากจำนวนการทดสอบที่คาดไว้ และหาก การทดสอบรายบุคคล จะไม่ใช่ขั้นตอนที่เหมาะสมที่สุด อย่างไรก็ตาม สิ่งสำคัญที่ควรทราบคือ แม้จะมีการวิจัยมายาวนานถึง 80 ปี ขั้นตอนที่เหมาะสมที่สุดสำหรับ และขนาดประชากรทั่วไปก็ยังไม่เป็นที่ทราบ^{[ 15 ]}${\displaystyle p>p_{u}}$${\displaystyle p_{u}=(3-{\sqrt {5}})/2\approx 0.38}$${\displaystyle p<p_{u}}$${\displaystyle p<p_{u}}$${\displaystyle n>2}$

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

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

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

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

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

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

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

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

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

ส่วนนี้จะให้คำจำกัดความอย่างเป็นทางการเกี่ยวกับแนวคิดและคำศัพท์ที่เกี่ยวข้องกับการทดสอบแบบกลุ่ม

• เวกเตอร์อินพุต , , ถูกกำหนดให้เป็นเวกเตอร์ไบนารีที่มีความยาว(นั่นคือ) โดยที่ รายการที่ jจะถูกเรียกว่าชำรุดก็ต่อเมื่อนอกจากนี้ รายการที่ไม่ชำรุดใดๆ จะถูกเรียกว่ารายการ 'ดี'${\displaystyle \mathbf {x} =(x_{1},x_{2},\dots ,x_{n})}$${\displaystyle n}$${\displaystyle \mathbf {x} \in \{0,1\}^{n}}$${\displaystyle x_{j}=1}$

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

• ให้เป็นเวกเตอร์อินพุต เซตเรียกว่าการทดสอบเมื่อการทดสอบปราศจากสัญญาณรบกวนผลลัพธ์ของการทดสอบจะเป็นบวกเมื่อ อยู่จริงที่ทำให้และผลลัพธ์จะเป็นลบในกรณีอื่น ๆ${\displaystyle \mathbf {x} }$${\displaystyle S\subseteq \{1,2,\dots ,n\}}$${\displaystyle j\in S}$${\displaystyle x_{j}=1}$

ดังนั้น เป้าหมายของการทดสอบแบบกลุ่มคือการคิดค้นวิธีการเลือกชุดการทดสอบที่ 'สั้น' ซึ่งจะช่วยให้สามารถระบุได้อย่างแม่นยำหรือด้วยความแน่นอนสูง ${\displaystyle \mathbf {x} }$

• กล่าวกันว่าอัลกอริทึมการทดสอบแบบกลุ่มเกิดข้อผิดพลาดหากติดป้ายกำกับรายการไม่ถูกต้อง (กล่าวคือ ติดป้ายกำกับรายการที่ชำรุดว่าเป็นรายการที่ไม่ชำรุด หรือในทางกลับกัน) นี่ไม่ใช่สิ่งเดียวกับผลลัพธ์ของการทดสอบแบบกลุ่มที่ไม่ถูกต้อง อัลกอริทึมเรียกว่ามีข้อผิดพลาดเป็นศูนย์หากความน่าจะเป็นที่มันจะเกิดข้อผิดพลาดเป็นศูนย์^{[ e ]}
• ${\displaystyle t(d,n)}$หมายถึงจำนวนการทดสอบขั้นต่ำที่จำเป็นในการค้นหาข้อบกพร่องในกลุ่ม สินค้าที่มีโอกาสผิดพลาดเป็นศูนย์เสมอ โดยใช้อัลกอริทึมการทดสอบแบบกลุ่มใดๆ สำหรับปริมาณเดียวกัน แต่มีข้อจำกัดว่าอัลกอริทึมนั้นไม่สามารถปรับเปลี่ยนได้ จะใช้สัญลักษณ์${\displaystyle d}$${\displaystyle n}$${\displaystyle {\bar {t}}(d,n)}$

เนื่องจากสามารถทำการทดสอบรายบุคคลได้เสมอโดยการกำหนดค่าสำหรับแต่ละรายการจึงต้องเป็นเช่นนั้นนอกจากนี้ เนื่องจากขั้นตอนการทดสอบที่ไม่ปรับตัวใดๆ ก็สามารถเขียนเป็นอัลกอริธึมแบบปรับตัวได้โดยการทำการทดสอบทั้งหมดโดยไม่คำนึงถึงผลลัพธ์สุดท้าย เมื่อ จะมีอย่างน้อยหนึ่งรายการที่ต้องตรวจสอบความบกพร่อง (โดยการทดสอบอย่างน้อยหนึ่งครั้ง) ดังนั้น ${\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)}$

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

ขอบล่างของจำนวนการทดสอบที่จำเป็นสามารถอธิบายได้โดยใช้แนวคิดของปริภูมิของตัวอย่าง ซึ่ง แสดงด้วยซึ่งก็คือเซตของตำแหน่งที่เป็นไปได้ของข้อบกพร่อง สำหรับปัญหาการทดสอบกลุ่มใดๆ ที่มีปริภูมิของตัวอย่างและอัลกอริทึมการทดสอบกลุ่มใดๆ ก็สามารถแสดงได้ว่าโดยที่คือจำนวนการทดสอบขั้นต่ำที่จำเป็นในการระบุข้อบกพร่องทั้งหมดด้วยความน่าจะเป็นของข้อผิดพลาดเป็นศูนย์ นี่เรียกว่าขอบล่างของข้อมูล^{[ 8 ]}ขอบนี้ได้มาจากข้อเท็จจริงที่ว่าหลังจากการทดสอบแต่ละครั้ง จะ ถูกแบ่งออกเป็นสองเซตย่อยที่ไม่ซ้ำกัน โดยแต่ละเซตย่อยสอดคล้องกับผลลัพธ์ที่เป็นไปได้หนึ่งในสองอย่างของการทดสอบ ${\displaystyle {\mathcal {S}}}$${\displaystyle {\mathcal {S}}}$${\displaystyle t\geq \lceil \log _{2}{|{\mathcal {S}}|}\rceil }$${\displaystyle t}$${\displaystyle {\mathcal {S}}}$

อย่างไรก็ตาม ขอบเขตล่างของข้อมูลนั้นมักจะไม่สามารถบรรลุได้ แม้แต่สำหรับปัญหาเล็กๆ^{[ 8 ]}ทั้งนี้เนื่องจากการแบ่งแยกนั้นไม่ได้เป็นไปโดยพลการ เนื่องจากจะต้องสามารถรับรู้ได้ด้วยการทดสอบบางอย่าง ${\displaystyle {\mathcal {S}}}$

ในความเป็นจริง ขอบเขตล่างของข้อมูลสามารถขยายไปสู่กรณีที่มีความน่าจะเป็นที่ไม่เป็นศูนย์ที่อัลกอริทึมจะทำผิดพลาด ในรูปแบบนี้ ทฤษฎีบทจะให้ขอบเขตบนของความน่าจะเป็นของความสำเร็จโดยอิงจากจำนวนการทดสอบ สำหรับอัลกอริทึมการทดสอบกลุ่มใดๆ ที่ทำการทดสอบ ความน่าจะเป็นของความสำเร็จ จะเป็นไป ตามเงื่อนไข นี้ ซึ่งสามารถเสริมความแข็งแกร่งได้ดังนี้: ^{[ 6 ] [ 24 ]}${\displaystyle t}$${\displaystyle \mathbb {P} ({\textrm {success}})}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq t/\log _{2}{n \choose d}}$${\displaystyle \mathbb {P} ({\textrm {success}})\leq {\frac {2^{t}}{n \choose d}}}$

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

• ให้เป็นจำนวนการทดสอบที่ดำเนินการโดยอัลกอริทึมที่ไม่ปรับตัวเวกเตอร์ผลลัพธ์ , , เป็นเวกเตอร์ไบนารีที่มีความยาว(นั่นคือ) โดยที่ก็ต่อเมื่อผลการทดสอบเป็นบวก (กล่าวคือ มีข้อบกพร่องอย่างน้อยหนึ่งรายการ) ^{[ g ]}${\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}}}$

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

ในกรณีที่มีสัญญาณรบกวนน้อยที่สุด ซึ่งมีความน่าจะเป็นคงที่ที่การทดสอบกลุ่มจะมีผลลัพธ์ที่ผิดพลาด เราจะพิจารณาเวกเตอร์ไบนารีแบบสุ่มโดยที่แต่ละรายการมีความน่าจะเป็นที่จะเป็นและเป็นอย่างอื่น เวกเตอร์ที่ส่งคืนคือโดยมีการบวกตามปกติบน (เทียบเท่ากับการดำเนินการ XORแบบรายองค์ประกอบ) อัลกอริทึมที่มีสัญญาณรบกวนต้องประมาณค่าโดยใช้(นั่นคือ โดยไม่มีความรู้โดยตรงเกี่ยวกับ) ^{[ 6 ]}${\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}}$${\displaystyle \mathbf {x} }$${\displaystyle {\hat {\mathbf {y} }}}$${\displaystyle \mathbf {y} }$

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

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

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

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

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

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

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)}$

อัลกอริทึมการแบ่งไบนารีทั่วไปเป็นอัลกอริทึมการทดสอบกลุ่มแบบปรับตัวที่เหมาะสมที่สุดโดยพื้นฐาน ซึ่งค้นหาข้อบกพร่องจำนวนหนึ่งหรือน้อยกว่าในบรรดารายการดังต่อไปนี้: ^{[ 8 ] [ 18 ]}${\displaystyle d}$${\displaystyle n}$

1. ถ้าใช่ให้ทดสอบแต่ละรายการทีละรายการ มิฉะนั้น ให้ตั้งค่าและ${\displaystyle n\leq 2d-2}$${\displaystyle n}$${\displaystyle l=n-d+1}$${\displaystyle \alpha =\lfloor \log _{2}{l/d}\rfloor }$
2. ทดสอบกลุ่มที่มีขนาดถ้าผลลัพธ์เป็นลบ แสดงว่าสินค้าทุกชิ้นในกลุ่มนั้นไม่มีข้อบกพร่อง ตั้งค่าและไปที่ขั้นตอนที่ 1 มิฉะนั้น ให้ใช้การค้นหาแบบไบนารีเพื่อระบุสินค้าที่มีข้อบกพร่องหนึ่งชิ้นและสินค้าที่ไม่มีข้อบกพร่องจำนวนหนึ่งซึ่งเรียกว่าตั้งค่าและไปที่ขั้นตอนที่ 1${\displaystyle 2^{\alpha }}$${\displaystyle n:=n-2^{\alpha }}$${\displaystyle x}$${\displaystyle n:=n-1-x}$${\displaystyle d:=d-1}$

อัลกอริทึมการแบ่งไบนารีทั่วไปไม่ต้องการ การทดสอบ เพิ่มเติม ใด ๆ^{[ 8 ]}${\displaystyle T}$${\displaystyle T={\begin{cases}n&n\leq 2d-2\\(\alpha +2)d+p-1&n\geq 2d-1\end{cases}}}$

สำหรับค่าขนาดใหญ่ สามารถแสดงได้ว่า[ ^{8 ] ซึ่ง}เปรียบเทียบได้ดีกับการทดสอบที่จำเป็นสำหรับอัลกอริทึมขั้นตอนของ Li ในความเป็นจริง อัลกอริทึมการแบ่งไบนารีทั่วไปใกล้เคียงกับค่าที่เหมาะสมที่สุดในแง่ต่อไปนี้ เมื่อสามารถแสดงได้ว่าโดยที่คือขอบเขตล่างของข้อมูล^{[ 8 ] [ 18 ]}${\displaystyle n/d}$${\displaystyle T\rightarrow d\log _{2}(n/d)}$${\displaystyle t={\frac {e}{\log _{2}e}}d\log _{2}\left({\frac {n}{d}}\right)}$${\displaystyle s}$${\displaystyle d\geq 2}$${\displaystyle T-B_{I}(d,n)\leq (d-1)}$${\displaystyle B_{I}(d,n)=\left\lceil \log _{2}\sum _{i=0}^{d}{n \choose i}\right\rceil }$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ความทั่วไปของทฤษฎีการทดสอบแบบกลุ่มทำให้สามารถนำไปประยุกต์ใช้ได้หลากหลาย รวมถึงการคัดกรองโคลน การค้นหาจุดลัดวงจรไฟฟ้า^{[ 8 ]}เครือข่ายคอมพิวเตอร์ความเร็วสูง^{[ 27 ]}การตรวจทางการแพทย์ การค้นหาปริมาณ สถิติ^{[ 20 ]}การเรียนรู้ของเครื่อง การจัดลำดับดีเอ็นเอ^{[ 28 ]}การเข้ารหัส^{[ 29 ] [ 30 ]}และนิติวิทยาศาสตร์ข้อมูล^{[ 31 ]}ส่วนนี้จะให้ภาพรวมโดยย่อของการประยุกต์ใช้งานเหล่านี้บางส่วน

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

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

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

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

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

ในปัญหานี้ การกู้คืนเทียบเท่ากับการค้นหายิ่งไปกว่านั้นก็ต่อเมื่อมีดัชนีบางตัวโดยที่ดังนั้น ปัญหานี้จึงคล้ายคลึงกับปัญหาการทดสอบกลุ่มที่มีรายการชำรุดและรายการทั้งหมด รายการของคือรายการ ซึ่งชำรุดหากระบุการทดสอบ และการทดสอบเป็นบวกก็ต่อเมื่อ^{[ 4 ]}${\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}}}$

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

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

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

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

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

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

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

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

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

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

• ปริศนาสมดุล