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?

  • $\begingroup$ There is a similar question. See mathoverflow.net/questions/168619/… $\endgroup$ Jun 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$ Jun 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$ Jun 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$ Jun 27 '14 at 21:14
  • $\begingroup$ Emil, it's right! I edited my question. Thanks! $\endgroup$ 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.

  • 2
    $\begingroup$ This is very interesting. Can you give a reference? $\endgroup$
    – Noah Stein
    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, 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.