<p>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.</p>

<p>Very related is <a href="https://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers">this question</a>: 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.</p>

<p>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$".</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-08T05:28:28.880Z
I think you mean "unary P not equal to unary NP"
Ryan Williams
CC BY-SA 3.0
2015-03-07T14:31:18.097Z
2015-03-08T05:41:14.310Z
2017-04-13T12:32:28.077Z
usul
<p>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. </p>

<p>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 <em>random</em> self-reducible. So this is an example of a very hard problem for which we can efficiently generate solved instances.</p>

CC BY-SA 3.0
2015-03-15T16:43:02.513Z
Another classical reference along these lines: [Generating hard instances of lattice problems](http://eccc.hpi-web.de/eccc-reports/1996/TR96-007/)
Daniel Apon
CC BY-SA 3.0
2015-03-08T06:31:50.217Z
2015-03-08T06:31:50.217Z
Ryan Williams
<p><img src="https://i.sstatic.net/BAVjL.jpg" alt="enter image description here"></p>

<p>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?</p>

CC BY-SA 3.0
2015-03-07T10:06:54.550Z
how do you represent the problems?
Kaveh
CC BY-SA 3.0
2015-03-07T15:15:50.787Z
@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
CC BY-SA 3.0
2015-03-10T04:27:15.683Z
1. "takes twice as much time as it is to design" - what does that mean?  "as it is"?  Is there a typo or some missing words somewhere in that sentence?  I'm having a hard time parsing it. 2. "whoever will verify that this problem is in the given complexity class that either will take more time and or space to solve." - I'm having difficulty parsing this, too.  What is the verb in that phrase? "(whoever will verify that this problem is in the given complexity class)" will what?
D.W.
CC BY-SA 3.0
2015-03-16T09:54:01.277Z
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
<cc.complexity-theory><reference-request><time-complexity><space-complexity>
The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
Joshua Herman
# The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem

(Asked by: username_0 on 2015-03-07)

![enter image description here](https://i.sstatic.net/BAVjL.jpg)

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?

**Tags:** cc.complexity-theory, reference-request, time-complexity, space-complexity

> **Comments:**
> **username_1**: how do you represent the problems?  
> **username_2**: @username_1: 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.  
> **username_3**: 1. "takes twice as much time as it is to design" - what does that mean?  "as it is"?  Is there a typo or some missing words somewhere in that sentence?  I'm having a hard time parsing it. 2. "whoever will verify that this problem is in the given complexity class that either will take more time and or space to solve." - I'm having difficulty parsing this, too.  What is the verb in that phrase? "(whoever will verify that this problem is in the given complexity class)" will what?  
> **username_4**: 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"?  

---

## 2 answers

### Answer by username_6 on 2015-03-08. Score: 15 | Accepted answer

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.

> **Comments:**
> **username_7**: Another classical reference along these lines: [Generating hard instances of lattice problems](http://eccc.hpi-web.de/eccc-reports/1996/TR96-007/)  

---

### Answer by username_5 on 2015-03-07. Score: 4

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](https://cstheory.stackexchange.com/questions/17456/the-examiners-problem-uniform-generation-of-sat-decision-instances-answers): 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.

> **Comments:**
> **username_6**: I think you mean "unary P not equal to unary NP"  

---

