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

We find hard instances for any given heuristic, either by running theheuristic or usingauxiliary provers to gain a more efficient procedure for generating a hardinstance. 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.