The evaluation of the hardness of the instances can be roughly divided into three parts. In the first two parts, we mainly study how the hardness difficulty scales with \(\lbrace n,f,\rho \rbrace \)  with instances generated with the random-loop algorithm. In the first part, we study how the hardness varies with the loop density, and observe the expected easy-hard-easy transitions, or hardness peaks [1]}, with the peak amplitudes and locations dependent on \(n\) . In the second part, we study how the hardness scales with \(n\)  for different frustration indexes \(f\) , and find that we can realize drastically different scaling behaviors for small changes in the frustration index, which may be related to the characteristic phase transition of the corresponding spin-glass model [2]}. In the third part, we perform a comparative analysis between the random- and structured-loop algorithms in their abilities to generate hard instances at high-loop density. For the structured-loop algorithm, we observe a second easy-hard transition beyond the first hardness peak, and also find a doubly-exponentially scaling difficulty improvement factor (over the random loop algorithm) with respect to the frustration index. All of the testing results can be easily reproduced by using the MATLAB script main.m which includes the functionality of generating instances with both the random and structured loop algorithm with user-defined parameters \(\lbrace n,f,\rho \rbrace \) .
