<p>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'.</p>

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

<p>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 <em>there is no $2^{n^\epsilon}$-hard PRG</em> at any $\epsilon&gt;0$. Then in this situation would it be possible to prove NP is not in P/poly by a natural proof?</p>

CC BY-SA 3.0
2017-03-18T14:16:02.470Z
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
CC BY-SA 3.0
2017-03-18T17:56:36.467Z
@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
CC BY-SA 3.0
2017-03-18T18:32:42.300Z
@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
CC BY-SA 3.0
2017-03-18T19:19:51.360Z
Maybe I misunderstand your question, because I definitely do not understand your response. I assume that by "natural property" you mean one that some NP problem has. You do not?
Sasho Nikolov
CC BY-SA 3.0
2017-03-19T02:18:48.783Z
@SashoNikolov  I think there are two queries here (1) Does SAT/#SAT having $2^{O(2^{\sqrt{\log n}})}$ algorithm imply no $2^{n^\epsilon}$ hard PRG? (2) Does no $2^{n^\epsilon}$ hard PRG imply natural proof is possible? Note SAT/#SAT could still have an $O(n)$ algorithm meaning P=NP in which case no such PRG exists or SAT/#SAT needs $2^{\omega(\log n)}$ algorithm in which case such $2^{n^\epsilon}$ hard PRGs may exist. However $2^{O(2^{\sqrt{\log n}})}$ algorithm prohibits $2^{n^\epsilon}$ hard PRGs if **(1)** is true. On **(2)** I assume no $2^{n^\epsilon}$ PRG could still P vs NP open.
Turbo
CC BY-SA 3.0
2017-03-19T04:00:13.203Z
You did not answer my question. When you say "natural proof", natural proof of what statement?!
Sasho Nikolov
CC BY-SA 3.0
2017-03-19T18:15:26.663Z
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
CC BY-SA 3.0
2017-03-21T05:52:46.440Z
@SashoNikolov I looked into the $90$s paper again. I am thinking similar to Williams' comment. It will esentially be a loop hole that makes functions not to be in P/poly.I am asking distinguishing P/poly particularly from NP. But isn;t that what the natural proofs paper tries to mark out?
Turbo
<circuit-complexity><lower-bounds><big-picture><p-vs-np><natural-proofs>
Converse to natural proofs theorem?
Turbo
# Converse to natural proofs theorem?

(Asked by: username_0 on 2017-03-18)

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?

**Tags:** circuit-complexity, lower-bounds, big-picture, p-vs-np, natural-proofs
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_0**: @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$.  
> **username_1**: Maybe I misunderstand your question, because I definitely do not understand your response. I assume that by "natural property" you mean one that some NP problem has. You do not?  
> **username_0**: @SashoNikolov  I think there are two queries here (1) Does SAT/#SAT having $2^{O(2^{\sqrt{\log n}})}$ algorithm imply no $2^{n^\epsilon}$ hard PRG? (2) Does no $2^{n^\epsilon}$ hard PRG imply natural proof is possible? Note SAT/#SAT could still have an $O(n)$ algorithm meaning P=NP in which case no such PRG exists or SAT/#SAT needs $2^{\omega(\log n)}$ algorithm in which case such $2^{n^\epsilon}$ hard PRGs may exist. However $2^{O(2^{\sqrt{\log n}})}$ algorithm prohibits $2^{n^\epsilon}$ hard PRGs if **(1)** is true. On **(2)** I assume no $2^{n^\epsilon}$ PRG could still P vs NP open.  
> **username_1**: You did not answer my question. When you say "natural proof", natural proof of what statement?!  
> **username_2**: 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  
> **username_0**: @SashoNikolov I looked into the $90$s paper again. I am thinking similar to Williams' comment. It will esentially be a loop hole that makes functions not to be in P/poly.I am asking distinguishing P/poly particularly from NP. But isn;t that what the natural proofs paper tries to mark out?  

---

## 0 answers

