Relation between problem hardness and solution space structure is an important research aspect. Model d-k-CSP generates very hard instances when $r=1$ and $r$ is near 1, where $r$ represents normalized constraint density. We find that when $r$ is below and close to 1, the solution space contains many widely distributed well-separated small cluster-regions (a cluster-region is a union of some clusters), which should the reason that the generated instances are hard to solve.
Paper
References (8)
01as k increasesIn summary the biggest diameter is Θ( n/k
02Similarly to Case C, for arbitrarily small positive number ǫ , when x ∈ (( a 1 + ǫ ) /n, b 2 − ǫ ), there exists δ = max ( 12 g 3 ( a 1 + ǫ ) , g 2 ( b 2 − ǫ )) such that sup n →∞ g 0 ( x ) < − δ
03Condensation phase does not exist
04As the same as Case C, if x is a positive constant, g 0 ( x ) → g 2 ( x )
05The smallest distances among cluster-regions are Θ( n ) (of the same order of n ), so the cluster-regions are well-separated
06From the above observations (1-3), when r is below and close to 1, the solution space contains many well-separated small cluster-regions
07With r approaching 1, the diameter of a cluster-region decreases to a small value
08r approaching 1