Assume NP$\neq$P and let $L$ be an NPcomplete 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?

$\begingroup$ There is a similar question. See mathoverflow.net/questions/168619/… $\endgroup$– Ali DehghanJun 26 '14 at 18:23

$\begingroup$ 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$? $\endgroup$– Emil JeřábekJun 27 '14 at 16:20

$\begingroup$ $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)$. $\endgroup$– Arash AhadiJun 27 '14 at 18:21

$\begingroup$ 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\}$. $\endgroup$– Emil JeřábekJun 27 '14 at 21:14

$\begingroup$ Emil, it's right! I edited my question. Thanks! $\endgroup$– Arash AhadiJun 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.

2$\begingroup$ This is very interesting. Can you give a reference? $\endgroup$ Jun 26 '14 at 17:35

2$\begingroup$ 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$. $\endgroup$ Jun 27 '14 at 17:59
Today, I find this papers: 1) Finding hard instances of the satisfiability problem: a survey, Cook and Mitchell, 19967. 2) IF NP LANGUAGES ARE HARD ON THE WORSTCASE, THEN IT IS EASY TO FIND THEIR HARD INSTANCES, Dan Gutfreund, Ronen Shaltiel, and Amnon TaShma, Journal of Computational Complexity, 2007.
Also there are some other papers that use "randomness" to generate hard instances.