tag:blogger.com,1999:blog-3722233.post8104865479297089951..comments2019-10-14T12:11:35.608-04:00Comments on Computational Complexity: Godel Prize: Natural Proofs. My 2 centsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-43626871686493917102007-05-30T11:43:00.000-04:002007-05-30T11:43:00.000-04:00Wow, this post got linked to as an authority on de...Wow, this post got linked to as an authority on describing the contribution of the [Razborov, Rudich] paper by the MAA (http://mathgateway.maa.org/do/ViewMathNews?id=92 -- which can be reached in 2 clicks from http://maa.org).Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35321496952352217982007-05-18T00:51:00.000-04:002007-05-18T00:51:00.000-04:00Typo: "g(n) >> exp(poly(n))" was meant to be "h(n)...Typo: "g(n) >> exp(poly(n))" was meant to be "h(n) >> exp(poly(n))", and the "second attraction" ends with a "]" after "output."KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55338686718221574062007-05-18T00:16:00.000-04:002007-05-18T00:16:00.000-04:00Cris and all,:: But how could one prove that a sep...Cris and all,<BR/><BR/>:: But how could one prove that a separation result, or technique, does not naturalize?<BR/><BR/>The brief germ of my idea was to focus on properties whose associated decision problems are EXPSPACE-hard, and/or involve double-exponential counting. For Boolean or algebraic functions f(x_1,...,x_n), the quest is to find a complexity measure M(f) such that log(M(f)) is a lower bound on circuit/formula size for f, and then show for particular f that M(f) grows faster than exp(poly(n)). In the algebraic case this is most meaningful when f has "low" degree d = poly(n).<BR/><BR/>For example, given a polynomial p(x_1,...,x_n) over C, define a monomial m to be "minimal" if m can be written in the form<BR/><BR/>m = g_1 p'_1 + g_2 p'_2 + ... + g_n p'_n<BR/><BR/>but no proper divisor of m can be written that way. Here p'_i is short for the partial derivative dp/dx_i, and g_1,...,g_n are arbitrary polynomials---the above says that m belongs to the Jacobian ideal Jac(p) of p. <BR/><BR/>Finally define M(p) to be the number of minimal monomials for p. There are low-degree p for which M(p) grows as 2^{2^n}, but alas they include ones with linear-sized formulas, thus foreclosing a log(M(p)) circuit lower bound relation. Nevertheless, a hardness predicate H(p) = "M(p) >= h(n)" may have no better decision procedure than brute-force counting M(p), which is "super-natural" when g(n) >> exp(poly(n)). [The second attraction of M(p) was that whenever the ideal (p,q) has no monomials, as happens "generically", M(p*q) = 0, so many *-gates would be "monomial killers"---and you'd have the sharper goal of showing that circuits/formulas for p must have exponential-size sum-gates at the output.<BR/><BR/>I've hunted for subtler measures M'(p) for which a log-circuit-size relation might hold. , but...I think nothing like counting connected components of varieties and other "low-level" stuff will work. Anyway, this seems to be a strategy to avoid "naturalizers". My <A HREF="http://www.cse.buffalo.edu/~regan/papers/pdf/Reg02MSFD.pdf" REL="nofollow">survey</A> of the Mulmuley-Sohoni approach ends with 2 pages on how that may also avoid naturalization.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3322192976081826812007-05-17T11:31:00.000-04:002007-05-17T11:31:00.000-04:00Bill,Why would 16 be better than 14? Its significa...Bill,<BR/><BR/>Why would 16 be better than 14? Its significance in base 2?Davenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7551815819160166422007-05-17T07:02:00.000-04:002007-05-17T07:02:00.000-04:00Both results seemed to hint at independence result...<I>Both results seemed to hint at independence results. Neither one has lead to any such results. </I><BR/><BR/>I do not think it's true. Razborov used similar reasoning to show that certain weak theories of arithmetic cannot prove that SAT has no polynomial-size circuits (and hence, cannot provide proofs that "non-uniform NP != P").<BR/><BR/>See <BR/><I>Unprovability of Lower Bounds on the Circuit Size in Certain Fragments of Bounded Arithmetic</I>, in Izvestiya of the Russian Academy of Science, mathematics, Vol. 59, No 1, 1995, pages 201-224.<BR/><BR/>http://www.mi.ras.ru/~razborov/ind.psAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11008653873428084642007-05-17T06:45:00.000-04:002007-05-17T06:45:00.000-04:00Then eventually someone should prove that the lang...<I>Then eventually someone should prove that the language of all proofs that resolve the P vs. NP question is undecidable.</I><BR/><BR/>That sounds pretty good, since undecidable are nonempty!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1702904438518184902007-05-17T03:55:00.000-04:002007-05-17T03:55:00.000-04:00We are going in circles. Someday in the near futur...We are going in circles. Someday in the near future we shall see another paper stating that Finite Model Theory can't solve the P vs. NP dilemma, too.<BR/><BR/>Then eventually someone should prove that the language of all proofs that resolve the P vs. NP question is undecidable.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28674160350704283162007-05-16T23:57:00.000-04:002007-05-16T23:57:00.000-04:00"There has not been a mass movement away from circ..."There has not been a mass movement away from circuits towards something else."<BR/><BR/>That's absolutely accurate - what there has been, more or less, is stasis.<BR/><BR/>But as far as independence results are concerned, weren't there some due to Razborov, following on the Natural Proofs work?<BR/><BR/>I think Razborov-Rudich is less interesting for what it says about proof techniques than for what it says about estimating the circuit complexity of a function. See this <A HREF="http://in-theory.blogspot.com/2006_07_30_archive.html" REL="nofollow"> post </A> by Luca Trevisan.Rahulnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63994789922429565282007-05-16T21:56:00.000-04:002007-05-16T21:56:00.000-04:00It seems the most likely way to avoid R-R is to ma...It seems the most likely way to avoid R-R is to make sure that the "largeness" condition is violated. That is, the useful property of Boolean functions that you're studying doesn't hold for a 1/2^{O(n)}-fraction of all Boolean functions, but it does happen to hold for the special family of Boolean functions you're proving lower bounds against (e.g. the family of functions that output "yes" iff the input encodes a satisfiable formula). <BR/><BR/>To me, the primary strength of natural proofs is that they indicate the limitations of the probabilistic method for proving circuit lower bounds (the analysis of random choices can allow "largeness" to creep in). <BR/><BR/>-ryan williamsRyanhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57988788143753472802007-05-16T21:13:00.000-04:002007-05-16T21:13:00.000-04:00One can prove that a separation result does not re...One can prove that a separation result does not relativize by constructing oracles in the presence of which it does not hold. <BR/><BR/>But how could one prove that a separation result, or technique, does not naturalize? As I read it, the R&R paper allows the "naturalizer" to make the separating property more specific to make it constructive, or more general to make it large. This gives the naturalizer an enormous advantage. So how will we ever know that a technique is capable of avoiding R&R? <BR/><BR/>- Cris MooreAnonymousnoreply@blogger.com