7
$\begingroup$

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?

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

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ This is very interesting. Can you give a reference? $\endgroup$
    – Noah Stein
    Jun 26, 2014 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, 2014 at 17:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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