Gap-Hamming problem

The Gap-Hamming problem is a well-known problem in the field of computational complexity and has connections to problems in coding theory and cryptography. It is a generalization of the classical Hamming problem. In the Hamming problem, one typically seeks to decide whether there exist two strings of a given length that differ in a certain number of positions (the Hamming distance).