Saturday, October 26, 2013

Sunday Morning Insight: Watching P vs NP

Last year, I somehow argued that it would be difficult for Quantum Computing to compete with the Steamrollers even if it meant they could solve NP problems (which we don't really know if they can [6]). This time, it is a little different. See, if you recall, sharp phase transitions are now part of our landscape. By landscape, I do not only mean their discovery [3], but also their use starting with [1] in 2010 and as recently as last week [4]. We collectively yearn for those limits to move (see The Wall in Sunday Morning Insight: Game of Thrones and the History of Compressive Sensing [5]

And like we said last week [2]

or like in the case of Manjhi, move a mountain.

Go read Tim Gowers' What I did in my summer holidays on TiddlySpace and his proposal for Polymath9 and Terry Tao's G+ post on Gilles Pisier's paper on Grothendieck's Theorem, past and present [7] (a more recent version of that paper is here) set up on the SelectedPapers network

It might happen right in front of our eyes.

[7] Grothendieck's Theorem, past and present by Gilles Pisier
Probably the most famous of Grothendieck's contributions to Banach space theory is the result that he himself described as "the fundamental theorem in the metric theory of tensor products". That is now commonly referred to as "Grothendieck's theorem" (GT in short), or sometimes as "Grothendieck's inequality". This had a major impact first in Banach space theory (roughly after 1968), then, later on, in $C^*$-algebra theory, (roughly after 1978). More recently, in this millennium, a new version of GT has been successfully developed in the framework of "operator spaces" or non-commutative Banach spaces. In addition, GT independently surfaced in several quite unrelated fields:\ in connection with Bell's inequality in quantum mechanics, in graph theory where the Grothendieck constant of a graph has been introduced and in computer science where the Grothendieck inequality is invoked to replace certain NP hard problems by others that can be treated by "semidefinite programming" and hence solved in polynomial time. In this expository paper, we present a review of all these topics, starting from the original GT. We concentrate on the more recent developments and merely outline those of the first Banach space period since detailed accounts of that are already available, for instance the author's 1986 CBMS notes.

No comments: