Phase Transition and the Computational Complexity of Generating r-contiguous Detectors

The problem of generating r-contiguous detectors in negative selection can be transformed in the problem of finding assignment sets for a Boolean formula in k-CNF. Knowing this crucial fact enables us to explore the computational complexity and the feasibility of finding detectors with respect to the number of self bit strings $|\mathcalS|$, the bit string length l and matching length r. It turns out that finding detectors is hardest in the phase transition region, which is characterized by certain combinations of parameters $|\mathcalS|,l$ and r. This insight is derived by investigating the r-contiguous matching probability in a random search approach and by using the equivalent k-CNF problem formulation.