A significant part of the algorithmic complexity theory
does in fact deal with problems with random input and here
an impressive random-case to worst-case
reductions are achievable for some of the problems.
These problems enjoy wide range applications in cryptography, where the
average case hardness property
is paramount for designing secure cryptographic protocols.
For example, if there exists a polynomial time
algorithm for computing the permanent of a matrix with i.i.d.
random inputs, then, rather surprisingly, one can use it to design a polynomial time algorithm
for all matrices [1]}.
The latter problem is known to be in the \(\#P\)  complexity class which subsumes \(NP\) .
A similar reduction exists [2]} for the problem of computing the
partition function of a Sherrington-Kirkpatrick model described below,
thus implying
that computing partition functions for spin glass models is not possible by polynomial time algorithms unless \(P=\#P\) .
Another problem admitting average-case to worst-case reduction
is the problem of finding a shortest vector in a lattice [3]}.
The random to worst case types of reduction described above would be ideal for
our setting, as they would provide the most compelling
evidence of hardness of these problems. For example, it would be ideal to
show that finding a clique of size at least say \((3/2)\log _2 N\)  in \(\mathbb {G}(N,1/2)\) 
implies a polynomial time algorithm with the same approximation
guarantee for all graphs. Unfortunately, such a result appears out of reach for
the existing proof techniques.
