  Using powerful Multicanonical Ensemble Monte Carlo methods from statistical
physics we explore the realization space of random K satisfiability (KSAT) in
search for computational hard problems, most likely the 'hardest problems'. We
search for realizations with unique satisfying assignments (USA) at ratio of
clause to spin number $\alpha=M/N$ that is minimal. USA realizations are found
for $\alpha$-values that approach $\alpha=1$ from above with increasing number
of spins $N$. We consider small spin numbers in $2 \le N \le 18$. The ensemble
mean exhibits very special properties. We find that the density of states of
the first excited state with energy one $\Omega_1=g(E=1)$ is consistent with an
exponential divergence in $N$: $\Omega_1 \propto {\rm exp} [+rN]$. The rate
constants for $K=2,3,4,5$ and $K=6$ of KSAT with USA realizations at $\alpha=1$
are determined numerically to be in the interval $r=0.348$ at $K=2$ and
$r=0.680$ at $K=6$. These approach the unstructured search value ${\rm ln}2$
with increasing $K$. Our ensemble of hard problems is expected to provide a
test bed for studies of quantum searches with Hamiltonians that have the form
of general Ising models.

Statistical Mechanics