Natural proofs paper shows 'if there is a natural property not possessed by any function in P/poly then there is no $2^{n^\epsilon}$-hard PRG'.

Is it easy to see the converse 'if there is no $2^{n^\epsilon}$-hard PRG then there is a natural property not possessed by any function in P/poly'.

The reason I seek is following. Even if SAT and $\#$SAT have $2^{O(2^{\sqrt{\log n}})}$ randomized algorithms then P is not NP is still possible. However in this case there is no $2^{n^\epsilon}$-hard PRG at any $\epsilon>0$. Then in this situation would it be possible to prove NP is not in P/poly by a natural proof?

  • 2
    $\begingroup$ So what you are asking is at least as strong as "if there is no exponentially hard PRG then NP is not in P/poly". This statement seems to imply an unconditional proof that NP is not in P/poly. $\endgroup$ Mar 18 '17 at 14:16
  • $\begingroup$ @SashoNikolov so does SAT and #SAT in randomized $2^{O(2^\sqrt{\log n})}$ imply no $2^{n^\epsilon}$ hard PRG at any $\epsilon>0$ which in turn imply NP is not in P/Poly? It could still be the case SAT and #SAT have deterministic linear time algorithm in which case NP is in P/poly. $\endgroup$
    – Turbo
    Mar 18 '17 at 17:56
  • $\begingroup$ @SashoNikolov I always thought SAT or #SAT in randomized $2^{O(2^\sqrt{\log n})}$ implies no $2^{n^\epsilon}$ PRG at any $\epsilon>0$. $\endgroup$
    – Turbo
    Mar 18 '17 at 18:32
  • 1
    $\begingroup$ You did not answer my question. When you say "natural proof", natural proof of what statement?! $\endgroup$ Mar 19 '17 at 4:00
  • 3
    $\begingroup$ I think what he means is the usual sense of a natural property: roughly speaking it's a deterministic polytime algorithm that given a truth table distinguishes most "hard" functions from all functions in P/poly. The alg does not have to output "hard" on any NP function $\endgroup$ Mar 19 '17 at 18:15

Your Answer

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

Browse other questions tagged or ask your own question.