ในความซับซ้อนของการสื่อสาร ปัญหา ช่องว่าง-แฮมมิง (gap-Hamming problem)ถามว่า ถ้าอลิซและบ็อบได้รับสตริง (ที่อาจแตกต่างกัน) คนละสตริง จำนวนบิตขั้นต่ำที่พวกเขาต้องแลกเปลี่ยนเพื่อให้อลิซสามารถคำนวณระยะทางแฮมมิงระหว่างสตริงของพวกเขาได้อย่างแม่นยำคือเท่าใด คำตอบของปัญหานี้โดยคร่าวๆ ระบุว่า ถ้าอลิซและบ็อบได้รับสตริงคนละสตริงโปรโตคอลการสื่อสาร ใดๆ ที่ใช้ในการคำนวณระยะทางแฮมมิงระหว่างสตริงของพวกเขาจะไม่มีประสิทธิภาพดีไปกว่าการที่บ็อบส่งสตริงทั้งหมดของเขาให้กับอลิซ (ในเชิงอะซิมโทติก) โดยเฉพาะอย่างยิ่ง ถ้าอลิซและบ็อบได้รับสตริงขนาด -บิต จะไม่มีโปรโตคอลการสื่อสารใดที่ทำให้อลิซสามารถคำนวณระยะทางแฮมมิงระหว่างสตริงของพวกเขาได้อย่างแม่นยำโดยใช้บิตน้อยกว่า- บิต${\displaystyle n}$${\displaystyle \pm {\sqrt {n}}}$${\displaystyle \Omega (n)}$

ปัญหาช่องว่าง-แฮมมิงมีการประยุกต์ใช้ในการพิสูจน์ขอบเขตล่างสำหรับอัลกอริธึมสตรีมมิ่งหลายตัว รวมถึงการประมาณความถี่โมเมนต์^{[ 1 ]}และการประมาณเอนโทรปี^{[ 2 ]}

ในโจทย์ข้อนี้ อลิซและบ็อบต่างได้รับสตริงและตามลำดับ โดยอลิซจะต้องคำนวณฟังก์ชัน (บางส่วน)${\displaystyle x\in \{\pm 1\}^{n}}$${\displaystyle y\in \{\pm 1\}^{n}}$

${\displaystyle \operatorname {GHD} (x,y)={\begin{cases}+1&D_{H}(x,y)\geq {\frac {n}{2}}+{\sqrt {n}}\\-1&D_{H}(x,y)\leq {\frac {n}{2}}-{\sqrt {n}}\\*&{\text{otherwise}},\end{cases}}}$

โดยใช้การสื่อสารให้น้อยที่สุดเท่าที่จะเป็นไปได้ ในที่นี้แสดงว่าอลิซสามารถส่งคืนค่าใดค่าหนึ่ง ระหว่าง และโดยที่ คือระยะทางแฮมมิงระหว่างและกล่าวอีกนัยหนึ่ง อลิซจำเป็นต้องส่งคืนว่าสตริงของบ็อบมีความคล้ายคลึงหรือแตกต่างจากสตริงของเธออย่างมีนัยสำคัญหรือไม่ ในขณะที่ลดจำนวนบิตที่เธอแลกเปลี่ยนกับบ็อบให้น้อยที่สุด${\displaystyle *}$${\displaystyle \pm 1}$${\displaystyle D_{H}(x,y)}$${\displaystyle x}$${\displaystyle y}$

วิธีแก้ปัญหาดังกล่าวระบุว่า การคำนวณต้องอาศัยการสื่อสารอย่างน้อยที่สุดโดยเฉพาะอย่างยิ่ง การคำนวณต้องอาศัยการสื่อสารแม้ว่าและจะถูกเลือกแบบสุ่มอย่างสม่ำเสมอจากก็ตาม${\displaystyle \operatorname {GHD} }$${\displaystyle \Omega (n)}$${\displaystyle \Omega (n)}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \{\pm 1\}^{n}}$

ปัญหาช่องว่าง-แฮมมิง (Gap-Hamming problem) เดิมทีถูกเสนอโดย Indyk และ Woodruff ในช่วงต้นทศวรรษ 2000 ซึ่งในตอนแรกพิสูจน์ขอบเขตล่างเชิงเส้นของ ความซับซ้อนของการสื่อสาร ทางเดียวของปัญหา (โดยที่อลิซได้รับอนุญาตให้รับข้อมูลจากบ็อบเท่านั้น) และคาดการณ์ขอบเขตล่างเชิงเส้นในกรณีทั่วไป^{[ 3 ]}คำถามเกี่ยวกับกรณีรอบอนันต์ (ซึ่งอลิซและบ็อบได้รับอนุญาตให้แลกเปลี่ยนข้อความได้มากเท่าที่ต้องการ) ยังคงเปิดอยู่จนกระทั่ง Chakrabarti และ Regev พิสูจน์ผ่าน การโต้แย้ง แบบต่อต้านความเข้มข้นว่าปัญหาทั่วไปมีความซับซ้อนของขอบเขตล่างเชิงเส้นเช่นกัน จึงยุติคำถามเดิมได้อย่างสมบูรณ์^{[ 4 ]}ผลลัพธ์นี้ตามมาด้วยเอกสารอื่นๆ อีกหลายฉบับที่พยายามทำให้ง่ายขึ้นหรือค้นหาวิธีการใหม่ในการพิสูจน์ขอบเขตล่างที่ต้องการ โดยเฉพาะอย่างยิ่งโดย Vidick ^{[ 5 ]}และต่อมาโดย Sherstov ^{[ 6 ]}และเมื่อเร็วๆ นี้ ด้วยวิธีการทางทฤษฎีสารสนเทศโดย Hadar, Liu, Polyanskiy และ Shayevitz ^{[ 7 ]}