6
$\begingroup$

This site contains various discussions of one-way functions and their relation to P versus NP.

Some of these discussions use a language $L=\{(x',y) ~\mid~ x'\le x \text{ and } f(x)=y \}$, where $f:\Sigma^*\to\Sigma^*$ is the one-way function and $x'\le x$ is the prefix relation. Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)\in L$.

I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?

Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?

Improve this question
$\endgroup$
1
  • $\begingroup$ It is likely that a proof that P=NP is not an effective proof. Crypto works about the same if the effort to crack n bit keys is 2^n or n^65536. $\endgroup$
    – Joshua
    Commented Dec 17, 2018 at 19:56

1 Answer 1

Reset to default
8
$\begingroup$

Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).

However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P \neq NP$. Intuitively, to fix this, modify your language as follows:

$L=\{(1^n, x',y) ~\mid~ \exists x, |x| = n, x'\le x, \text{ and } f(x)=y \}$,

where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'\le x$ means $x'$ is a prefix of $x$).

Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry, but with your modification it is not clear anymore how to invert function $f$ in polynomial time, in case $L$ is in $P$. For exploting $L$, it seems that now I need some a priori bound on $n$, but this might be exponentially large in the length of $y$. $\endgroup$
    – Alexis
    Commented Dec 17, 2018 at 15:04
  • $\begingroup$ Inverting $f$ needs not be polynomial in the output size $y$, but still in the input size $x$, which is the case if $L$ is in $P$. You should check the detailed solution given on page 2-3 of the exercise sheet I link to (courses.cs.ut.ee/all/MTAT.07.004/2016_fall/uploads/solution/…). $\endgroup$
    – Geoffroy Couteau
    Commented Dec 17, 2018 at 15:29
  • $\begingroup$ With polynomial runtime for f you can not generate an output f(x) with superpolynonial size - so actually any limitation on x also translates to y implicitly. $\endgroup$
    – tylo
    Commented Dec 18, 2018 at 11:56

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.