The main motivation of this work is to study the average case hardness of the problems which belong to high complexity classes. In more detail, we are interested in provable hard problems which have a big set of hard instances. Moreover, we consider efficient generators of these hard instances of the problems. Our investigation has possible applications in cryptography. As a first step, we consider computational problems from the NEXP class. We extend techniques presented in [7] in order to develop efficient generation of hard instances of exponentially hard problems. Particularly, for any given polynomial time (deterministic/probabilistic) heuristic claiming to solve NEXP hard problem our procedure finds instances on which the heuristic errs. Then we present techniques for generating hard instances for (super polynomial but) sub exponential time heuristics. As a concrete example the Succinct Permanent mod p problem is chosen. First, we prove the NEXP hardness of this problem (via randomized polynomial time reduction). Next, for any given polynomial time heuristic we construct hard instance. Finally, an efficient technique which expands one hard instance to exponential set (in the number of additional bits added to the found instance) of hard instances of the Succinct Permanent mod p problem is provided.
展开▼
