The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

Question

enter image description here

In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource limited by some amount and whoever will verify that this problem is in the given complexity class that either will take more time and or space to solve. Is this a novel problem?

@Kaveh: Maybe the way to formalize this is that the problem is fixed and the task is to generate hard instances in polynomial time? E.g., the problem depicted in the picture is a search problem, the input is a solvable maze, and the output is a valid path through the maze. — Robin Kothari, Mar 07 '15 at 15:15
Sorry, I do not understand the question: "design a maze that takes twice as much time to design" still doesn't make sense. Do you mean "design a maze that takes twice as much time to solve as it does to design", or "design a maze that takes twice as much time to design as it does to solve"? — András Salamon, Mar 16 '15 at 09:54

score 15 · Accepted Answer · answered Mar 08 '15 at 06:31

This situation comes up frequently in crypto, where you want to generate hard problem instances along with their solutions. For example, there is the work of Eric Bach (and later, Adam Kalai) on efficiently generating random integers with their prime factorizations.

One of many interesting observations of Impagliazzo and Wigderson (Randomness vs time: derandomization under a uniform assumption. J. Comput. Syst. Sci., 63:672–688, 2001) is that one can efficiently generate uniform random matrices modulo p along with their permanents. (Think about it... use self-reducibility of permanent....) Moreover, we know that the permanent is random self-reducible. So this is an example of a very hard problem for which we can efficiently generate solved instances.

Another classical reference along these lines: Generating hard instances of lattice problems — Daniel Apon, Mar 15 '15 at 16:43

score 4 · Answer 2 · edited Apr 13 '17 at 12:32

First, I don't think the Arthur-Merlin protocol has to enter the model -- it sounds from the motivation like you just want to produce problem instances quickly so that any algorithm for solving them is slow. In other words, if we could prove that Arthur can produce a hard problem, then there seems to be no need for Merlin to verify that the problem produced is hard.

Very related is this question: Can we generate in polynomial time a language that is not decidable in polynomial time? The answer turns out to be yes iff unary P is not equal to unary NP.

That was for deterministically generating an instance. For randomly generating one, if one-way functions $f$ exist, then we can just pick a uniformly random $x$ and present the problem "here is $f$ and $f(x)$, find $x$".

Hmm, actually, if we are not constrained, we can generate very hard problems: For a problem of size $n$, we ask whether the $n$th Turing Machine halts on a blank input. Or if we have randomness, we pick a number $i$ in $\{1,\dots,n\}$ uniformly at random and ask whether the $i$th Turing Machine halts. So perhaps it makes sense to limit the kinds of problems we want to generate to only be so hard, e.g. in NP.

I think you mean "unary P not equal to unary NP" – Ryan Williams Mar 08 '15 at 05:28 — Ryan Williams, Mar 08 '15 at 05:28

The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

2 Answers2