7

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?

Jack
  • 3
Arash Ahadi
  • 191
  • There is a similar question. See http://mathoverflow.net/questions/168619/is-it-easy-to-produce-hard-to-color-graphs – Ali Dehghan 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$? – Emil Jeřábek 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)$. – Arash Ahadi 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}$. – Emil Jeřábek Jun 27 '14 at 21:14
  • Emil, it's right! I edited my question. Thanks! – Arash Ahadi Jun 29 '14 at 21:12

2 Answers2

11

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.

Scott Aaronson
  • 9,743
  • 2
    This is very interesting. Can you give a reference? – Noah Stein Jun 26 '14 at 17:35
  • 2
    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$. – Scott Aaronson Jun 27 '14 at 17:59
1

Today, I find this papers: 1) Finding hard instances of the satisfiability problem: a survey, Cook and Mitchell, 1996-7. 2) IF NP LANGUAGES ARE HARD ON THE WORST-CASE, THEN IT IS EASY TO FIND THEIR HARD INSTANCES, Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma, Journal of Computational Complexity, 2007.

Also there are some other papers that use "randomness" to generate hard instances.

Arash Ahadi
  • 191