Super Solutions of the Model RB
This work addresses a theoretical problem in constraint satisfaction for researchers in computational complexity, but it appears incremental as it extends known methods to a specific type of generalized solution.
The paper tackles the problem of establishing a threshold for the existence of (1,1)-super solutions in the model RB, using the first moment method to show that the expected number of such solutions transitions from 0 to infinity as constraint density crosses this threshold.
The concept of super solution is a special type of generalized solutions with certain degree of robustness and stability. In this paper we consider the $(1,1)$-super solutions of the model RB. Using the first moment method, we establish a "threshold" such that as the constraint density crosses this value, the expected number of $(1,1)$-super solutions goes from $0$ to infinity.