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.