# Converse to natural proofs theorem?

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?

• 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. – Sasho Nikolov Mar 18 '17 at 14:16
• @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. – Turbo Mar 18 '17 at 17:56
• @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$. – Turbo Mar 18 '17 at 18:32
• You did not answer my question. When you say "natural proof", natural proof of what statement?! – Sasho Nikolov Mar 19 '17 at 4:00
• 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 – Ryan Williams Mar 19 '17 at 18:15