  We study an exactly solvable version of the famous random Boolean
satisfiability problem, the so called random XOR-SAT problem. Rare events are
shown to affect the combinatorial ``phase diagram'' leading to a coexistence of
solvable and unsolvable instances of the combinatorial problem in a certain
region of the parameters characterizing the model. Such instances differ by a
non-extensive quantity in the ground state energy of the associated diluted
spin-glass model. We also show that the critical exponent $\nu$, controlling
the size of the critical window where the probability of having solutions
vanishes, depends on the model parameters, shedding light on the link between
random hyper-graph topology and universality classes. In the case of random
satisfiability, a similar behavior was conjectured to be connected to the onset
of computational intractability.
