tag:blogger.com,1999:blog-3722233.post6731884769203026022..comments2020-08-03T03:34:35.967-04:00Comments on Computational Complexity: GCT Workshop (Guest Post by Josh Grochow)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-67178586789371259762010-07-15T15:19:00.773-04:002010-07-15T15:19:00.773-04:00@Josh: the problem about E and H is yet another al...@Josh: the problem about E and H is yet another algebraic version of P versus NP, but not the BSS one.<br />The BSS problem asks whether the satisfiability of a system of polynomial equations (over say the field of complex numbers) can be decided in a polynomial number of arithmetic operations and equality tests.<br />Note in particular that this is about decision problems, whereas the GCT program is about evaluation of polynomials (perm versus det, E versus H).<br />There are actually some connections between the complexity of decision and evaluation problems, but maybe not quite as tight as your post seemed to imply.Pascal Koirannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3154670564928683012010-07-15T12:00:31.178-04:002010-07-15T12:00:31.178-04:00@Pascal: Although Ketan only talked about permanen...@Pascal: Although Ketan only talked about permanent vs determinant at the workshop, even in GCT I & II (the original Mulmuley-Sohoni GCT papers) they construct two polynomials H(X) and E(X) such that the GCT conjectures regarding H vs E (instead of det vs perm) imply that NP over the complex numbers does not have polynomial-size arithmetic circuits.<br /><br />(In my previous response to Raplh, I meant that GCT *also* applies to det vs perm, in addition to NP vs P/poly, not that it only applies to det vs perm.)<br /><br />The definitions of the functions H and E are entirely elementary, and I recommend anyone who is interested in GCT to go lookup their definitions in GCT I.Josh Grochownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75829432724379936152010-07-15T09:56:15.305-04:002010-07-15T09:56:15.305-04:00@Josh: as you said the GCT program (or at least th...@Josh: as you said the GCT program (or at least the part of it that Ketan talked about at the workshop) is about permanent versus determinant.<br /><br />If it succeeds it will be of course a huge achievement, but as far as I can see it will not directly imply that P is not NP in the BSS model over the complex numbers.Pascal Koirannoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-27781914403207521382010-07-15T00:21:36.278-04:002010-07-15T00:21:36.278-04:00@Ralph: First, the GCT approach applies to the det...@Ralph: First, the GCT approach applies to the determinant vs permanent problem, which is essentially NC vs #P, which should be easier to resolve than P vs NP (as you point out with P vs PSPACE). Presumably there is a GCT approach to P vs PSPACE, but it hasn't been explored yet as far as I know.<br /><br />Second, it's important to know that the conjectures in GCT are not known to be *equivalent* to P neq NP, but only imply that P neq NP. The most developed part of GCT at the moment is aimed at proving P neq NP in the algebraic model (essentially the "real RAM" model or "Blum-Shub-Smale model over the complex numbers"). I believe that the GCT approach to P neq NP in the classical model will be fleshed out in a forthcoming paper (I think that's GCT IX).<br /><br />@Kurt: "verify P neq NP up to length n" should be read as: "verify that there are not circuits of size n^c for SAT up to length n".Josh Grochownoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52578356579125994832010-07-14T23:51:56.694-04:002010-07-14T23:51:56.694-04:00ryanw (Ryan Williams), your IBM Almaden colleagues...ryanw (Ryan Williams), your IBM Almaden colleagues Dan Rugar and John Mamin are here in France giving well-received lectures on spin microscopy. To the extent that there is a natural connection between IBM's quantum spin imaging experiments—which by consensus are among the most sophisticated in the world—and your own theoretical work on complexity complexity, that connection seems to arise pretty naturally via the geometric complexity aspects of simulating IBM's experiments <i>ab initio</i>. <br /><br />So you might consider having lunch together some afternoon, and brainstorming about new multidisciplinary uses for that Blue Gene that sits down the hallway at Almaden. Whether anything concrete came of your lunch or not, the struggle to speak each other's language, and understand each other's problems, would itself be a lot of fun.John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26718652501448007042010-07-14T22:51:41.844-04:002010-07-14T22:51:41.844-04:00Somehow LOGSPACE vs NP looks as if it may be easie...<em>Somehow LOGSPACE vs NP looks as if it may be easier. (There has been some "real" lower bound progress on that question, but still very little.)</em><br /><br />What progress has there been?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52803580389645591872010-07-14T21:15:24.266-04:002010-07-14T21:15:24.266-04:00Thanks for this nice summary. I really wanted to a...Thanks for this nice summary. I really wanted to attend the workshop but simply couldn't make time for it. <br /><br />@Ralph: Much work has gone into P vs PSPACE, and currently there's about the same amount of progress on it as P vs NP. (Very, very little.) Can Quantified CNF Satisfiability be solved in linear time on a multitape Turing machine?... of course not, but why?<br /><br />Somehow LOGSPACE vs NP looks as if it may be easier. (There has been some "real" lower bound progress on that question, but still very little.)ryanwhttp://www.cs.cmu.edu/~ryanw/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83920223376421724602010-07-14T19:59:37.807-04:002010-07-14T19:59:37.807-04:00"verify P neq NP up to length n" for lar...<em>"verify P neq NP up to length n" for larger and larger n</em><br /><br />Please forgive a dumb question, but just what is <strong>n</strong> in this context?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-954373724806234982010-07-14T14:28:46.870-04:002010-07-14T14:28:46.870-04:00Intractability center is doing great job organizin...Intractability center is doing great job organizing frequent workshops (at the intersection of complexity and mathematics) and also offering financial aid to students. I learnt a lot of concepts (that textbooks/courses cannot cover) through these workshops. I hope the videos of the talks of this GCT workshop will be uploaded soon.<br /><br />On a technical note, I was wondering how difficult it is to give a GCT-based proof of a 'parity \notin AC^0". Does it require a generalization of RH ?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23669597577840216532010-07-14T13:17:29.761-04:002010-07-14T13:17:29.761-04:00I've always wondered why so much effort is exp...I've always wondered why so much effort is expended on P vs NP. Why not P vs PSPACE?<br /><br />P!=PSPACE <b>can't</b> be harder to prove than P!=NP, and <b>ought</b> to be much easier. There are <b>lots</b> complexity classes between P and PSPACE, any you can't prove <b>any</b> of them are different without proving P!=PSPACE.<br /><br />Are there algebraic conjectures equivalent to P!=PSPACE?<br /><br />On the "equals" side, there are implications of P=NP like NP=coNP, but there isn't such a clear "easiest" question.Ralph Hartleynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46231577774477222142010-07-14T13:00:27.183-04:002010-07-14T13:00:27.183-04:00As it turns out, the rank of a tensor has consider...As it turns out, the rank of a tensor has considerable practical importance in quantum systems engineering, where it arises in a geometrically natural way in the context of computing the musical isomorphism between dynamical one-forms (specified by Hamiltonians and Lindbladians) and tangents to quantum trajectories (computed as the output of quantum simulation codes).<br /><br />For better or worse, an audience of <a href="http://iramis.cea.fr/meetings/nMRI/" rel="nofollow">quantum spin microscopists</a> is scheduled to hear me lecture on this subject this coming Friday. <br /><br />Since I *don't* presently know how to explain the relation of geometry to computational complexity in any natural way—especially to an audience whose interest is almost wholly focussed upon practical experiments—comments in this regard *definitely* would be welcome.<br /><br />The simpler, the better ... and uhhh ... quickly, please! :)John Sidleshttp://www.mrfm.orgnoreply@blogger.com