Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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.
