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$
$\endgroup$
5
-
$\begingroup$ There is a similar question. See mathoverflow.net/questions/168619/… $\endgroup$– Ali DehghanCommented 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$– Emil JeřábekCommented 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$– Arash AhadiCommented 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$– Emil JeřábekCommented Jun 27, 2014 at 21:14
-
$\begingroup$ Emil, it's right! I edited my question. Thanks! $\endgroup$– Arash AhadiCommented Jun 29, 2014 at 21:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Jun 26, 2014 at 17:16
-
2$\begingroup$ This is very interesting. Can you give a reference? $\endgroup$ Commented 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$ Commented Jun 27, 2014 at 17:59
$\begingroup$
$\endgroup$
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.