Bola de jamón

En combinatoria , una bola de Hamming es una bola métrica para la distancia de Hamming . La bola de Hamming de radio${\displaystyle r}$centrado en una cuerda${\displaystyle x}$sobre algún alfabeto (a menudo el alfabeto {0,1}) es el conjunto de todas las cadenas de la misma longitud que difieren de${\displaystyle x}$como máximo${\displaystyle r}$posiciones. Esto puede denotarse utilizando la notación estándar para bolas métricas,${\displaystyle B(x,r)}$. Para un alfabeto${\displaystyle X}$y una cuerda${\displaystyle x}$La bola de Hamming es un subconjunto del espacio de Hamming.${\displaystyle X^{|x|}}$de cuerdas de la misma longitud que${\displaystyle x}$y es un subconjunto propio siempre que${\displaystyle r<|x|}$El nombre bola de Hamming proviene de la teoría de la codificación , donde los códigos de corrección de errores se pueden definir como aquellos que tienen bolas de Hamming disjuntas alrededor de sus palabras clave, ^{[ 1 ]} y los códigos de cobertura se pueden definir como aquellos que tienen bolas de Hamming alrededor de la palabra clave cuya unión es todo el espacio de Hamming. ^{[ 2 ]}

Algunos algoritmos de búsqueda local para solucionadores SAT , como WalkSAT, operan utilizando códigos de adivinación aleatoria o de cobertura para encontrar una bola de Hamming que contenga la solución deseada, y luego buscan dentro de esta bola de Hamming para encontrar la solución. ^{[ 2 ]}

Se conoce una versión del teorema de Helly para bolas de Hamming: Para bolas de Hamming de radio${\displaystyle r}$(en espacios de Hamming de dimensión mayor que${\displaystyle r}$), si una familia de bolas tiene la propiedad de que cada subfamilia de como máximo${\displaystyle 2^{r+1}}$Si las bolas tienen una intersección común, entonces toda la familia tiene una intersección común. ^{[ 3 ]}