Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue
in theoretical computer science.
In this work, we prove that the Succinct Permanent \bmod \; p is NEXP
time hard in the worst case (via randomized polynomial time reduction).

We find hard instances for any given heuristic, either by running the
heuristic or using
auxiliary provers to gain a more efficient procedure for generating a hard
instance. We provide a technique for building an exponential set (in the
number of additional bits added to the found instance)
of hard instances of the problem.