# Generating Hard Instances

Assume NP$\neq$P and let $L$ be an NP-complete language. Is there a polynomial time computable function $f:\{0\}^*\longrightarrow\{0,1\}^*$ with $|f(0^n)|=n$ for every $n$; such that L $=\{0^n: f(0^n)\in L\}\notin$ P?

• There is a similar question. See mathoverflow.net/questions/168619/… Jun 26 '14 at 18:23
• Do you mean $\mathbf L$ to consist of the $n$’s written in binary (as suggested by your notation), or in unary (as would seem more natural, and apparently as Scott Aaronson interpreted it)? That is, does your $\mathbf L\in\mathrm P$ mean that $f(0^n)\in L$ is decidable in time polynomial in $\log n$, or in time polynomial in $n$? Jun 27 '14 at 16:20
• $0^n$ has $n$ bits; so I mean polynomial in $n$.If one means polynomial in $\log n$, he/she can use $f(n)$ instead of $f(0^n)$. Jun 27 '14 at 18:21
• All right, this clarifies what you mean. However, note that while $0^n$ has $n$ bits, $n$ has only $\log n$ bits, so if you want polynomial in $n$, you need to define the language as $\mathbf L=\{0^n:f(0^n)\in L\}$. Jun 27 '14 at 21:14
• Emil, it's right! I edited my question. Thanks! Jun 29 '14 at 21:12

No, it's not known how to get that purely from the assumption $P\ne NP$. You can get it from the stronger assumption $EXP\ne NEXP$, which implies $P\ne NP$ but is not known to be implied by it.
• Noah: It's often given as an exercise, in complexity textbooks, to prove that $EXP=NEXP$ iff every unary $NP$-language (i.e., every $NP$-language containing only strings of the form $0^n$) is also in $P$. So, if $EXP\ne NEXP$, then you have a unary $NP$-language not in $P$, and from there you can get the $f$ that the OP wants, by applying an $NP$-completeness reduction to reduce your unary language to $L$. Conversely, the OP's $\mathsf{L}$ would itself be a unary $NP$-language not in $P$, so its existence would imply $EXP\ne NEXP$, believed to be stronger than what you can get from $P\ne NP$. Jun 27 '14 at 17:59