Timeline for P/poly vs NP separation based on circuit trees instead of DAGs
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 2, 2013 at 19:27 | comment | added | vzn | thx for ref, Rossman has now archived his paper at ECCC. Formulas vs. Circuits for Small Distance Connectivity | |
| Nov 4, 2013 at 1:47 | comment | added | vzn | was thinking along those lines & thought you might say that! yes, have heard of that paper yet strangely, there is almost/nearly no reaction to it or further analysis/commentary on it by anyone [incl your own highly/deeply comprehensive book!], eg in stark contrast to Natural Proofs [which also does not mention it]. so if it really is a significant "barrier" its an extremely low-profile one... & yet it has been proven that superpoly monotone lower bounds on slice functions are sufficient to separate P/poly from NP (and razborov has apparently never written anything on slice fns...?) | |
| Nov 3, 2013 at 19:49 | comment | added | Stasys | @vzn: The answer is "most probably - NO, unless we extend the arguments to work under the presence of "auxiliary variables". The thms you mentioned are just Razborov's approximation argument "in disguise" (a "symmetric version"). And he has proved here what we need to get it work in non-monotone case. People trying to extend his argument to non-monotone circuits should carefully read this paper to avoid disappointments. | |
| Nov 3, 2013 at 16:31 | comment | added | vzn | thx! reviewing your notes, monotone circuits; do you think thm9.17, 9.18, or 9.25 (which are close to an answer to the question) could be strong enough for any P/poly$\stackrel{?}{=}$NP result, or not? | |
| Nov 2, 2013 at 17:45 | vote | accept | vzn | ||
| Nov 2, 2013 at 15:00 | history | answered | Stasys | CC BY-SA 3.0 |